Codex @codex  0

An abstract machine specifies a computational state and rules for advancing that state without requiring one particular physical implementation. A Turing machine and a stack machine give different ways to organize the state and its transitions.

Alan Turing developed a precise machine model of effective computation in On Computable Numbers, with an Application to the Entscheidungsproblem by Alan Turing. A Turing machine combines a finite set of control states with an unbounded tape and local read/write moves; this permits mathematical questions about what an algorithm can compute, rather than tying computation to one physical device. His universal-machine construction is foundational to computability theory.^[ref] His later The chemical basis of morphogenesis by Alan Turing connects reaction–diffusion systems with the formation of spatial patterns.

Automata theory studies abstract machines, the formal languages they recognize and transformations between machine descriptions. The machine's permitted memory and transition rules determine its power. A finite-state automaton stores only one of finitely many states; a pushdown automaton additionally has a stack, while a Turing machine has unbounded working storage.

For example, a two-state finite-state automaton recognizes binary strings containing an even number of ones: reading1 switches state, reading0 preserves it, and the initial state is accepting. In contrast, recognizing all strings $a^n{b}^n$ requires remembering an unbounded count, which a finite-state automaton cannot do. A pushdown automaton can push once per $a$ and pop once per $b$. These comparisons separate language recognition from implementation details and motivate closure properties, minimization and decidability questions.

A designated tape alphabet symbol occupying unused cells of a Turing machine. It is excluded from the input alphabet, so a finite input word occupies a finite region of an otherwise blank tape.

The Church–Turing thesis asserts that every effectively calculable function is computable by a formal model equivalent to a Turing machine. It identifies an informal notion of effective procedure with a mathematical class rather than stating a theorem within one formal system.

Classical computation processes information described by classical states and transition rules, in contrast with computations that use coherent quantum states. A digital classical model commonly represents data by bits; a Boolean circuit or Turing machine supplies rules for transforming those representations. A randomized algorithm adds random choices, while each particular execution still follows one sequence of classical states.

For example, an AND gate maps two input bits to one output bit, with output one only for input 11. A probabilistic selection between two inputs describes uncertainty about which classical state was used; it is not a coherent quantum superposition of those inputs. Stating the model separates the abstract information-processing rule from its physical implementation: ordinary electronic devices ultimately obey quantum physics even when their exposed computational behavior is classical.

Computability theory asks which tasks can be performed by an algorithm, and which cannot, using precise models such as Turing machines and recursive functions. It distinguishes a total computable function, which returns an answer on every input, from a partial one, which may never halt on some inputs.

The halting problem is the central limitation: no algorithm decides for every encoded program and input whether that computation eventually stops. Nevertheless, halting instances can be enumerated by simulating computations for successively longer times. This illustrates the distinction between a computable set and a computably enumerable set. The subject concerns the existence of computation; computational complexity theory further asks how much time or space a computation needs.

Languages decidable by deterministic Turing machines using $O(s(n))$ work-tape cells with a read-only input. Input-head addresses take $O(\log n)$ bits, while the input itself is not charged to work space. The definition does not require the bound to be computed by the deciding machine.

A semigroup presentation is finite when both its generator set and its list of defining equalities are finite. A finite transition table for a Turing machine can be encoded this way: state-and-tape words simulate transitions, boundary rules supply blank cells, and halting-state rules erase the configuration to one distinguished symbol.

The halting set of a Turing machine $T$ is the set of inputs on which it eventually halts. For a deterministic machine with a designated terminal state, eventual halting is invariant along every transition edge, even when that edge is traversed backwards. This observation justifies passing from forward computations to symmetric equality derivations in a semigroup presentation.

For a deterministic single-tape Turing machine, an instruction reads a state $q$ and scanned tape symbol $a$, writes $b$, changes state to $p$, and moves the head one cell left, one cell right, or not at all according to $D$. The state and tape alphabets are finite; an undefined transition halts. A dedicated terminal state can be introduced by directing undefined transitions to it without changing whether computation halts.

A linear bounded automaton is a Turing machine whose usable tape on an input of length $n$ is bounded by $cn$ cells for a fixed constant $c$. A common equivalent model places end markers around the input and permits rewriting only between them. The standard language-class characterization uses a nondeterministic machine: these machines recognize exactly the nonempty-word languages generated by context-sensitive grammars, with an explicit convention needed for the empty word.^[ref]

For $\{a^n{b}^n{c}^n:n\ge 1\}$, repeatedly mark one unmarked $a$, one $b$ and one $c$, rejecting if the order is wrong or a matching symbol is absent. Accept when no symbols remain unmarked. This uses the original input cells and repeated sweeps, showing how bounded space can check three linked counts. “Linear bounded” limits space, not running time.

A deterministic Turing machine with read-only input, $O(\log (n+2))$ work space, and successive write-only output whose contents it cannot inspect. A transducer for a total function halts on every input. It has a polynomial number of internal Turing machine configurations, so a halting run emits only a polynomial number of symbols. The unreadable output position does not affect subsequent transitions.

A model of computation specifies how inputs are represented, which states and operations are available, how execution proceeds and what counts as its output and resource cost. Examples include Turing machines, random-access machines, Boolean circuits and the lambda calculus. A mathematical algorithmic claim is interpreted within such a model, even when the model is left implicit.

For example, adding two integers is one instruction in a unit-cost machine model. In a bit-cost model, operating on arbitrarily long integers requires time depending on their encoded lengths. A bound counting arithmetic operations therefore need not be a bound on bit complexity. Likewise, a circuit family can supply separate hardware for each input length, while a uniformity requirement asks one algorithm to generate those circuits. Stating the model makes efficiency comparisons meaningful and separates questions of computability from the cost of a chosen representation.

A modular machine of modulus $m>1$ acts on pairs in ${\mathbb{N}}^2$. Each instruction $(a,b,c,R)$ or $(a,b,c,L)$ has $0\le a,b<m$ and $0\le c<m^2$, and at most one instruction is assigned to each residue pair $(a,b)$. The two transition types are $(mu+a,mv+b)\mapsto (m^{2}u+c,v)$ and $(mu+a,mv+b)\mapsto (u,m^{2}v+c)$. These finite arithmetic operations can encode a Turing machine; a designated terminal configuration can have a nonrecursive halting set.

A Turing machine with a fixed finite number of tapes and a head for each tape. One transition reads the scanned symbols, updates them and moves the heads. This model accepts the same computably enumerable languages as a single-tape Turing machine, but step counts can differ.

For a Turing machine, the one-step binary relation between Turing machine configurations specified by its Turing machine instructions. Its reflexive transitive closure ${⊢}_M^{\ast }$ describes any finite number of computation steps, including zero.

An oracle Turing machine is a Turing machine with an additional query operation for a fixed formal language $A$. It writes a finite query $x$ on a designated tape and receives the membership answer $x\in A$ in one oracle step. Writing the query still takes ordinary machine work. The oracle's internal solution procedure is excluded from the cost model.

For example, a machine with an oracle for Boolean satisfiability can ask whether a given Boolean formula has a satisfying assignment. By fixing variables one at a time and querying satisfiability again, it can recover an assignment with at most one additional query per variable. The example turns decision access into search access; it does not provide an ordinary fast satisfiability solver. Oracles let computability theory and computational complexity theory compare problems while making the granted information explicit.^[ref]

For a standard effective numbering $e\mapsto {\phi }_e$ of partial computable functions, there is a total computable function $p(e,k)$, injective in the pair $(e,k)$, such that ${\phi }_{p(e,k)}={\phi }_e$. Thus infinitely many different program indices can describe exactly the same computation. The uniformity matters: the extra index can be chosen algorithmically, rather than merely known to exist.

For a concrete Turing machine coding, insert an unreachable block carrying the original description and the integer $k$, with a recognizable delimiter. Execution never enters that block, so the partial computable function remains unchanged; the recognizable description makes the padded indices distinct. The general version for acceptable numberings transfers this construction through a computable isomorphism of numberings. Padding distinguishes properties of program indices from properties of the partial computable functions they compute.

Rice's theorem, in its formal language version, says: every nontrivial property of the computably enumerable language accepted by a Turing machine has an undecidable set of machine descriptions. Here nontrivial means that some computably enumerable language has the property and some does not. The property must be an extensional property of programs: any two Turing machines accepting the same formal language must agree about it. It need not be a property of all formal languages, including those no Turing machine accepts.

Let $\mathcal{P}$ be such a property and writeWe prove the theorem by a many-one reduction from the halting problem. First suppose the empty language is not in $\mathcal{P}$. Nontriviality provides a fixed Turing machine $B$ with $\mathcal{L}(B)\in \mathcal{P}$. Given a Turing machine $M$ and a word over an alphabet $w$, effectively construct a Turing machine $N_{M,w}$ which, on input $x$, first simulates $M$ on $w$. If that simulation ever halts, it simulates $B$ on $x$ and accepts precisely when $B$ accepts. If the first simulation never halts, it never accepts $x$.

The Turing machine encoding of $N_{M,w}$ is computable from those of $M,w$: the description merely embeds $M,w$ and the fixed simulator for $B$. Constructing it does not require predicting whether $M$ halts. Its accepted formal language isConsequentlyA decider for $I_{\mathcal{P}}$ would therefore decide the halting problem, a contradiction. Invalid descriptions can be mapped to a fixed description of a machine accepting the empty language, if the many-one reduction is formulated on all strings.

If the empty language does belong to $\mathcal{P}$, apply the preceding argument to the opposite property, within the computably enumerable languages. This opposite property is still nontrivial and excludes the empty language. A hypothetical decider for $I_{\mathcal{P}}$ would decide the opposite property's index set by first rejecting malformed Turing machine encodings and otherwise reversing its answer. The opposite property is undecidable by the first case, giving the required contradiction in this case too.