Transformers are Stateless Differentiable Neural Computers

An operation's input-output function does not, by itself, determine its computational role within a represented process. That role also depends on the processes producing its inputs and receiving its outputs, a philosophical stance termed deep learning externalism (DLE). We develop a mathematical account of represented computation that distinguishes functional equivalence, retained predecessor distinctions, restricted receiver capability, and context-dependent effective architectures. The resulting equivalences depend on which computational relations a scientific description must preserve. We prove that two injective producer contexts can preserve every predecessor distinction while changing whether fixed local and attention receiver families are equivalent. We investigate these relations in a dimension-labelled PreNorm Transformer and their evolution under training. Residual bypasses restrict complete-state information identifications to two merges per block, while finer branches can change receiver accessibility. Exact gradient-descent models yield covariance-dependent geometric attenuation under learned producer routing and algebraic $(t^{-1/2})$ attenuation under Q/K-softmax training, with optimal bounded-receiver recovery errors derived in both cases. Coupled producer-attention dynamics establish how learning jointly reorganizes the presented features and receiver allocation. Finally, present functional or receiver-profile equivalence need not determine future behavior under an optimizer. In an input-conditioned attention model, two accessibility measurements form an exact reduced predictive state, whereas one alone does not.

Transformers encode structure in sequences via an expanding contextual history. However, their purely feedforward architecture fundamentally limits dynamic state tracking. State tracking -- the iterative updating of latent variables reflecting an evolving environment -- involves inherently sequential dependencies that feedforward networks struggle to maintain. Consequently, feedforward models push evolving state representations deeper into their layer stack with each new input step, rendering information inaccessible in shallow layers and ultimately exhausting the model's depth. While this depth limit can be bypassed by dynamic depth models and by explicit or latent thinking that externalizes state representations, these solutions are computationally and memory inefficient. In this article, we argue that temporally extended cognition requires refocusing from explicit thought traces to implicit activation dynamics via recurrent architectures. We introduce a taxonomy of recurrent and continuous-thought transformer architectures, categorizing them by their recurrence axis (depth versus step) and their ratio of input tokens to recurrence steps. Finally, we outline promising research directions, including enhanced state-space models and coarse-grained recurrence, to better integrate state tracking into modern foundation models.

What types of decision problems can a causally masked, finite-precision transformer solve for inputs of arbitrary length? Existing answers often rely on idealized arithmetic, but under finite precision, rounding and evaluation order can change what information attention retains and therefore what the model can compute. We develop an algebraic formalization that derives expressivity directly from the model's implemented dynamics. Its central object is its memory; the finite internal state computed by attention that summarizes the information from the prefix available to all future queries. Each attention head updates its own state independently within a layer, while layers compose hierarchically, providing a uniform route from model assumptions to expressivity bounds. Applying this method to transformers without positional embeddings, we obtain an expressivity hierarchy governed by the attention type under specific numerical semantics. Width-one sliding-window attention supports bounded-suffix memory, while a modified form of soft attention supports irreversible, checklist-like state, and combining the two mechanisms provides an interplay of both. Ordinary left-to-right floating-point soft attention can realize more expressive memory operations than any of the above. Algebraically, the four cases correspond to definite, R-trivial, locally R-trivial, and aperiodic semigroups. Under an explicit free-wiring assumption, all four bounds are tight.