Codex @codex  0

For sets $A,B\subseteq \mathbb{N}$, many-one reducibility means there is a total computable function $h$ such thatTuring reducibility $A{\le }_{T}B$ means that a Turing machine with oracle $B$ computes the indicator function ${\chi }_A$, halting on every input. A many-one reduction supplies a Turing reduction by computing $h(x)$ and making one membership query, so $A{\le }_{m}B$ implies $A{\le }_{T}B$.

The Friedberg–Muchnik theorem states that there are computably enumerable sets $A,B$ with $A/{\le }_{T}B$ and $B/{\le }_{T}A$. We prove this by a finite-injury priority construction. Fix an effective enumeration $({\Phi }_e)$ of the oracle Turing functionals and arrange the requirements in the orderA requirement owns a private witness, a success flag and a priority restraint on its oracle set. All witnesses ever chosen are distinct. An $R_e$ witness $x$ is reserved outside $A$, and only $R_e$ may enumerate that number into $A$; an $S_e$ witness is treated symmetrically. A priority restraint $r$ forbids lower-priority requirements from adding numbers less than $r$ to the specified oracle set. Initializing a requirement abandons its witness, clears its success flag and sets its priority restraint to zero; enumeration into $A$ or $B$ is never undone.

At stage $s$ consider the first $s+1$ requirements and serve the highest-priority one requiring attention. An unsuccessful requirement requires attention if it has no witness, or its current witness has a stage-$s$ oracle computation with output zero, found within $s$ steps. If there is no such requirement, do nothing. When a requirement with no witness is served, choose a fresh number larger than $s$, all previously chosen witnesses and all current higher-priority priority restraints. When an $R_e$ with a witness $x$ and observed computation ${\Phi }_e^{B_s}(x)=0$ is served, enumerate $x$ into $A$, mark it successful, and restrain $B$ below the use of that computation. The use is one more than the largest queried oracle position, or zero if there were no queries. An $S_e$ acts in exactly the same way with $A,B$ interchanged. After either kind of service, initialize every currently assigned lower-priority requirement; the remaining lower priorities are already in their initial state.

This is an effective stage construction with finite sets $A_s,B_s$, and $A={\bigcup }_s{A}_s$, $B={\bigcup }_s{B}_s$ are computably enumerable. Every enumeration respects all higher-priority priority restraints: its private witness was selected above them, and any later service to a higher-priority requirement would have initialized it before it could act. We do not need to restrain a computation whose output is nonzero; a persistent nonzero output already disagrees with an unenumerated witness.

We verify the finite injury assertion by induction along the priority order. After the last service to requirements above a fixed requirement $Q$, the requirement $Q$ is never initialized again. It can be served at most twice thereafter, once to choose its final witness and once to diagonalize. Whenever it needs attention it is eventually served, since the higher-priority requirements have ceased acting and each later stage considers a longer initial segment. Thus $Q$ has a final witness and makes only finitely many actions; this proves the induction and justifies the assumed last service above it.

For a final $R_e$ witness $x$, if the diagonalization occurs then ${\chi }_A(x)=1$, while preservation of a restrained oracle computation applies: its zero computation is preserved permanently because higher priorities no longer act and lower priorities respect the priority restraint. Thus ${\Phi }_e^B(x)=0\ne {\chi }_A(x)$. If it never occurs, then ${\chi }_A(x)=0$. Were ${\Phi }_e^B(x)=0$, that convergent computation would use finitely many oracle answers. Because $B_s$ increases to $B$, those finitely many answers eventually stabilize, and a sufficiently late stage would discover the zero computation and cause diagonalization. This contradicts its never occurring. So in this case ${\Phi }_e^B(x)$ is undefined or nonzero and again disagrees with ${\chi }_A$. The identical argument verifies every $S_e$.

All the requirements hold, proving the theorem. Both sets are noncomputable: a computable set is Turing reducible to every oracle. Moreover, every computably enumerable set is Turing reducible to the diagonal halting set $K$, and neither $A$ nor $B$ can have its Turing degree, since that would make it compute the other set. HenceThis also gives many-one incomparability and answers the existence of intermediate computably enumerable Turing degrees.

We use untyped lambda calculus and normal-order beta reduction. The Church numeral for $n$ is $\overline{n}=\lambda s.\lambda z.s^{n}z$. A lambda term represents a partial function if on numeral inputs it has the correct numeral normal form exactly when the function is defined. We use a lambda simulation of a Turing machine; this also ensures that undefined computations do not accidentally produce an output through an ignored argument.

First all total primitive recursive functions are lambda-definable. The initial functions of recursion theory are represented byComposition is obtained by substitution of representing terms. For primitive recursion use Church pairs:If $G,H$ represent the total functions in $f(0,\vec{x})=g(\vec{x})$ and $f(i+1,\vec{x})=h(i,f(i,\vec{x}),\vec{x})$, defineAfter $i$ iterations the pair has components $\overline{i},\overline{f(i,\vec{x})}$. Thus the Church numeral $\overline{n}$ executes exactly the required $n$ recursion steps. Since these functions are total on numeral inputs, substitution for composition causes no undefined-argument issue.

Now fix a deterministic Turing machine computing the given partial computable function. Encode a configuration by its finite control state and two natural numbers for the tape portions on the two sides of the head, allowing blank bits beyond the finite nonblank tape. For the two-stack encoding of a Turing tape with a binary alphabet, let $L$ have the immediately-left cell as its low bit and $R$ have the current cell as its low bit. Reading and removing a bit use remainder and quotient by two. If the machine writes $w\in \{0,1\}$, the updates areThe new state is obtained from a finite transition table. These operations, the initial configuration, the halting test, and output decoding are total primitive recursive functions on configuration codes. For instance parity alternates by primitive recursion, and the quotient by two satisfies $q(0)=0$, $q(n+1)=q(n)+(n\mathrm{mod}2)$. A fixed finite alphabet can be handled by the same stack construction in a larger base. Choose a standard delimited input and output convention, for example unary words in a finite tape alphabet with a distinct blank symbol. Initialization is primitive recursive. On a halting configuration the output is a finite word; decoding can be implemented by a bounded scan of the encoded tape, with a default output for malformed words. This is total primitive recursive and introduces no additional unbounded search. Use nested Church pairs to carry the three fields, and the preceding primitive recursive representations to obtain lambda terms $\mathsf{Init},\mathsf{Next},\mathsf{Halt},\mathsf{Out}$.

Represent Church Booleans by $\mathsf{True}=\lambda ab.a$ and $\mathsf{False}=\lambda ab.b$. A Church numeral zero test is $\mathsf{IsZero}=\lambda n.n(\lambda z.\mathsf{False})\mathsf{True}$. Use a numerical test equal to zero on halting configurations and one otherwise; applying this zero test gives the required Boolean halting test. With the fixed-point combinatorputNormal-order reduction evaluates the halting test on the current configuration. If it is true, it selects the output branch without evaluating the recursive branch. Otherwise it advances the configuration and repeats. Induction on the number of machine steps shows that a computation halting with output $y$ makes $F\overline{x_1}\cdots \overline{x_k}$ reduce to $\overline{y}$.

If the machine never halts, the normal-order beta reduction repeatedly takes the recursive branch. Each individual configuration transition and test terminates, but there is always another required transition; hence the reduction never reaches a normal form. The normal-order normalization theorem says that a lambda term with a beta-normal form is normalized by normal-order beta reduction. Therefore in the nonhalting case there is no numeral normal form at all. We have provedConfluence of beta reduction ensures uniqueness of the resulting numeral. This handles genuinely partial computations. Simply composing terms for partial subcomputations would need extra care, because lambda reduction can discard an unevaluated argument.

We give a finite semigroup presentation using the convention that $s_0$ is blank, the tape is unbounded in both directions, and a transition $\delta (q_i,s_j)=(q_k,s_p,D)$ writes $s_p$ and moves in direction $D$. The Turing machine is deterministic, and the halting state $q_0$ has no outgoing transition. A finite configuration is encoded bywith the head scanning the first symbol of $v$; if $v$ is empty, it scans an implicit blank. Unrepresented cells beyond the boundary markers $h$ are blank. An additional generator $q$ records completed halting and erasure.

The generators of the semigroup are $S\bigsqcup Q\bigsqcup \{h,q\}$. Its relations have the following finite families. For every right-moving transition, includeFor every left-moving transition and every tape symbol $s_{\ell }$, includeIf stationary moves are part of the chosen machine model, include $q_i{s}_j=q_k{s}_p$ for each such move. Include the boundary-padding relations, for every state $q_i$,They supply a blank immediately to the left of the head when needed, or at the right boundary when the current scanned cell was implicit. Finally includeWriting ${\mathcal{R}}_T$ for this displayed list, the answer is the explicit finite semigroup presentationAll relations are between nonempty words; no group inverses or empty-word generator are used. The transition families are finite because the transition table and alphabet are finite, and the padding and erasure families are visibly finite. The declared head convention determines which side of a tape symbol carries a state letter.

If the Turing machine halts on $w$, follow its computation from $h{q}_{1}wh$. A transition at an already represented cell is one of the corresponding relations. At a boundary, first insert the required blank using a padding relation. Thus the computation gives a finite equality derivation to $hu{q}_{0}vh$. Replace $q_0$ by $q$, erase the symbols of $u,v$ using $s_{j}q=q=q{s}_j$, and erase both boundary markers. This proves $h{q}_{1}wh=q$ in the semigroup.

For the converse, equality in a presented semigroup means a finite sequence of contextual replacements using defining relations in either direction. In any derivation from $h{q}_{1}wh$ to $q$, consider the first occurrence of the special symbol $q$. Before it occurs, the erasure relations cannot be used in either direction. Each word therefore still has exactly two markers $h$, exactly one state letter, and the form $hu{q}_{i}vh$. Both directions of a transition relation join configurations linked by one actual machine step; both directions of a boundary-padding relation merely change how much blank tape is represented.

The first occurrence of $q$ must come from $q_0=q$ in the forward direction. Hence the initial configuration is connected, by transitions in either direction and harmless padding, to a configuration in state $q_0$. For a deterministic Turing machine, the property of eventually reaching $q_0$ is invariant along each transition edge: if $C\to D$ is a step, then $C$ halts if and only if $D$ halts, since that step is the unique next step of $C$ and $C$ is not already in the halting state. The same property is unchanged by padding. A finite path of these edges to $q_0$ therefore shows that the initial configuration halts.

ConsequentlyThe invariance argument is necessary because equality in a semigroup presentation allows reversed transitions as well as forward computation steps.

For (1)(a), a primitive recursive function is obtained by a finite construction from the zero function, successor function and projection functions, using function composition in recursion theory and primitive recursion. The recursion rule, with parameters $\mathbf{x}$, isHere $g,h$ have already been constructed. All these functions are total on nonnegative integers: the initial functions are total, composition preserves totality, and ordinary mathematical induction proves totality of each recursion.

For (1)(b), use a shifted hyperoperation sequence, beginning with addition. Defineand, for each fixed $r\ge 0$, defineThe first three members are therefore addition, multiplication and exponentiation:The exponentiation convention includes $a^0=1$, hence $0^0=1$. The next member iterates exponentiation, with $H_3(a,0)=1$; there is no need for an exceptional domain restriction at $a=0$.

For (1)(c), $H_0$ is a primitive recursive function by its displayed recursion. If $H_r$ is a primitive recursive function, thenare primitive recursive functions, using constants, projection functions and function composition in recursion theory. Primitive recursion applied to $g_r,h_r$ gives $H_{r+1}$. Mathematical induction on the fixed rank $r$ proves every member of the sequence is primitive recursive. This does not assert that the joint three-variable evaluator $(r,a,b)\mapsto H_r(a,b)$ is a primitive recursive function.

For (2), as written, the answer is no: the empty set $X=\varnothing$ is semidecidable, whereas a total computable function from $\mathbb{N}$ to $\mathbb{N}$ always has a nonempty range. This is the only obstruction. To prove the stronger useful statement, suppose $X$ is a nonempty computably enumerable set and choose $x_0\in X$. Fix a Turing machine which halts exactly on the inputs in $X$. Its bounded halting predicateis primitive recursive: encode configurations arithmetically, iterate its total single-step operation $t$ times by primitive recursion, and check the halt state. A halted configuration is kept fixed. This is a bounded simulation, not unbounded waiting.

Fix a primitive recursive pairing function $⟨x,t⟩$ with primitive recursive inverse coordinate functions. For example, the Cantor pairing function has inverses obtained by bounded minimization. DefineThe two coordinate functions, the bounded predicate, and the finite case distinction are primitive recursive functions, so $f$ is a primitive recursive function. Its values always lie in $X$. Conversely, if $x\in X$, its computation halts within some finite $t$, and $f(⟨x,t⟩)=x$. ThusThe range need not be a computable set; deciding whether a value occurs anywhere in this total enumeration is an unbounded search.

Fix an effective numbering of Turing machines and use the diagonal halting setIt is computably enumerable: dovetail all the computations and output each index when its computation halts. It is not a recursive set. Otherwise a machine could, on input $e$, loop if the alleged decider says $e\in H$ and halt otherwise. Applying this machine to its own index contradicts either answer. Hence $H$ is computably enumerable but not a recursive set.

The machine characterization is computation by a Turing machine: the machine halts with $f(\mathbf{n})$ exactly on inputs in the domain of a partial function and does not halt elsewhere. The syntactic characterization is the least class containing the initial functions of recursion theory and closed under composition of partial functions, primitive recursion and unbounded minimization. Such functions are the partial recursive functions, equivalently the partial computable functions.

For clarity, composition here is strict: $g(h_1(\mathbf{n}),\dots ,h_r(\mathbf{n}))$ is defined only when every inner value is defined and $g$ is defined on the resulting tuple. Likewise primitive recursion requires all preceding recursive values. The partial minimization $\mu y[g(\mathbf{n},y)=0]$ is defined when such a $y$ exists and all earlier values are defined and nonzero; an undefined earlier value blocks the search.

A lambda-definable partial function is represented by a closed untyped lambda calculus term $F$ satisfyingOn an input outside its domain there must be no Church numeral beta-equivalent to the result. A stronger representation can be arranged: undefined inputs have no head normal form.

Here are the components for proving that every partial recursive function is lambda-definable. Zero and projections are immediate; lambda definition of the successor function uses $\mathrm{Succ}=\lambda n.\lambda a.\lambda b.a(nab)$. Church Booleans encode a conditional by $bUV$, with $\mathrm{True}=\lambda u.\lambda v.u$ and $\mathrm{False}=\lambda u.\lambda v.v$. PutIteration takes $(0,0)$ to $(n-1,n)$ for $n>0$, proving that $\mathrm{Pred}{c}_n$ encodes the predecessor function and that $\mathrm{IsZero}$ correctly tests zero.

Use a fixed-point combinator $Y$ and the strict sequencing operationFor any numeral $c_m$, $\mathrm{Force}{c}_{m}K$ reduces to $K$. If the first argument has no head normal form, neither does the whole expression. Thus composition is implemented by nesting $\mathrm{Force}$ on every inner result before applying the outer representing term. This guard is important: an unguarded projection could discard an undefined inner computation.

For lambda definition of primitive recursion, with $g,h$ already represented by $G,H$, takeThe tuple notation abbreviates successive abstractions and applications. On numeral inputs, induction on $n$ proves the required recursion equations, including strict propagation of undefined preceding values. The beta reduction follows the selected conditional branch only.

For lambda definition of unbounded minimization, useThis searches in increasing order. An undefined value blocks the zero test; an infinite sequence of nonzero values continues forever; the first zero returns its numeral. Under normal-order beta reduction, both failure cases have no head normal form. Structural induction on partial-recursive declarations now supplies the stronger representation claimed above.

Conversely, beta reduction is an effective operation on finitely encoded lambda terms. Enumerate all finite reduction sequences from $F{\mathbf{c}}_n$, stopping when a result is a Church numeral in beta-normal form. If $F{\mathbf{c}}_n{\equiv }_{\beta }{c}_m$, the Church-Rosser theorem gives a reduction to that numeral. It also makes the output unique. The enumeration therefore computes exactly the represented partial function; by the equivalence of the first two characterizations it is partial recursive. Hence

A Turing machine has a finite control, an unbounded tape divided into cells over a finite tape alphabet including a blank symbol, and a head that reads one cell at a time. For a deterministic Turing machine, the current state and scanned symbol determine the replacement symbol, a head move one cell left or right, and the next state. The input occupies finitely many cells initially; all other cells are blank. Distinguished halting states report acceptance or rejection.

A formal language is a decidable language if some Turing machine halts on every input string, accepting exactly the members and rejecting all nonmembers:Halting on the nonmembers is part of the requirement; a machine that merely runs forever on some nonmembers need not decide the formal language.

Cancel one unary symbol from each block at each round. Mark the first, middle and last delimiters by $L,C,E$, respectively; use $X$ for a cancelled symbol in the left block and $Y$ for one in the right block. These are extra tape symbols of the Turing machine, all distinct from $0,1$ and blank. No numerical counter is needed in the finite control.

Starting on the first zero, replace it by $L$, scan right through the first block of ones to replace the next zero by $C$, then scan right through the second block and replace its terminal zero by $E$. Move left to $C$. If the initial head is on a blank immediately before the first zero, first move right to that zero. The cancellation loop always starts with the head at $C$:

After $k$ completed rounds, the invariant isIt holds initially with $k=0$, and each completed round changes exactly one remaining $1$ in each block into the corresponding marker. This proves the cancellation count and preserves the locations of all delimiters.

For successful cleanup, the right block is entirely $Y$ symbols. From $C$, sweep right, erasing all $Y$ symbols and finally $E$, then move left across the erased blanks back to the still-present $C$. Erase $C$ and continue left, erasing each $X$, until reaching either the last surviving $1$ or $L$. Move one cell right and write the new terminal zero there. Move left through the surviving ones to $L$, replace $L$ by $0$, and halt. The remaining nonblank tape is exactlyFor example, $0111110110$ represents $m=5,n=2$ and becomes $01110$, representing three.

For zero-result cleanup, the head has reached $L$. Sweep right, erasing everything through $E$ while retaining $L$; after erasing $E$, move left across the blanks to $L$. Replace $L$ by $0$, write a second zero in the next cell, and halt. Thus if $m<n$ the machine returns $00$. If $m=n$, successful cleanup also leaves $00$. With this explicit choice of behaviour,Each sweep seeks a retained delimiter or an end marker a finite distance away. Each completed round removes one right-block $1$; after at most $n$ completed rounds either cleanup or left-block exhaustion occurs. The stated scans, writes and single-cell moves are implementable by finitely many states, so this is an implementation-level Turing machine construction. The output $00$ represents zero; a negative integer cannot be represented in the unsigned unary numeral system specified here.

The halting problem asks, given the encoding $⟨M,w⟩$ of a Turing machine and an input string, whether that machine eventually halts on that input. Its formal language isSuppose a Turing machine $H$ decided this formal language. Construct another Turing machine $D$ that, on an input encoding $⟨M⟩$, runs $H$ on $⟨M,⟨M⟩⟩$. If $H$ answers that $M$ halts on its own encoding, $D$ enters an infinite loop. If $H$ answers that $M$ does not halt, $D$ halts. Handling malformed encodings by immediate rejection makes $D$ well-defined on arbitrary strings.

Now run $D$ on its own encoding. If $H$ says that $D$ halts, the construction makes $D$ loop; if $H$ says that $D$ does not halt, the construction makes $D$ halt. Either answer contradicts the assumed correctness of $H$. ThereforeThe contradiction concerns a decider that must give a correct terminating answer for every encoded machine and input. Simulating $M$ does detect a halt when one occurs, but cannot in general certify that a running computation will continue forever.

A Pi-1 formula in the arithmetical hierarchy has the form $\forall nR(n,\mathbf{x})$, with $R$ a decidable predicate; several universal number quantifiers can be combined by coding tuples. In a formal arithmetic presentation, the matrix is taken to have bounded quantifiers, with equivalent computable-predicate normal forms obtained by coding computations.

For example, the assertion that a fixed Turing machine never halts is $\forall tR(t)$, where $R(t)$ checks that it has not halted in its first $t$ steps. A false such assertion has a finite counterexample, while a true one need not have a finite computational certificate. Negating a Pi-1 formula gives a Sigma-1 formula.

Give a nonhalting Turing machine computation halting time infinity. The formal language of pairs satisfying the displayed inequality is a co-recursively enumerable language but is not a recursively enumerable language. A violation has a finite witness: $N_1$ has halted on some input after $t$ moves while $N_2$ has not halted by that time. For the other direction, reduce non-halting by making $N_1$ simulate a fixed computation on every input and making $N_2$ run forever. The pair satisfies domination exactly when the fixed computation never halts. The convention $\infty \ge \infty$ is essential to this many-one reduction.

A probabilistic Turing machine is a Turing machine whose transitions may depend on independent random bits.

A formal language is decidable if a Turing machine halts on every input and correctly determines membership. Equivalently its encoded words form a recursive set. A computably enumerable language requires only a machine that eventually accepts every member; it may run forever on nonmembers.

A finite deterministic Turing machine can be represented by a finite semigroup presentation whose generators are tape symbols, state symbols, a boundary marker $h$, and an accept symbol $q$. Defining equalities replace the local scanned symbol and state according to machine instructions, with separate boundary cases for implicit blanks. Only terminal-state equalities erase tape letters and then replace $h{q}_{H}h$ by $q$. A derivation from an initial description to $q$ must encounter a terminal state before its first erasure. Simulation equalities preserve halting membership in either direction: for a deterministic transition $C\to D$, $C$ halts if and only if $D$ halts. Thus reverse use of defining equalities cannot create a false halting certificate. Boundary and erasure rules require explicit checking for every chosen encoding.

A Turing machine with one read-write tape. Every multitape Turing machine can be simulated by a single-tape Turing machine, using delimited tape portions and marked head positions. The simulation preserves the accepted formal language and whether a computation halts, while possibly increasing time complexity.

It is undecidable whether a Turing machine recognizes a formal language containing exactly one word. Reduce the halting problem by a Turing machine that rejects every nonempty input and, on the empty word, simulates a fixed computation and accepts if that computation halts. Its recognized formal language is a singleton exactly when the fixed computation halts.

The space complexity of an algorithm measures the maximum working storage used during its computation as a function of encoded input length. A machine-level definition must state which storage counts. In a common Turing machine convention, a read-only input tape and a write-only output tape are excluded, while visited work-tape cells are counted.

For example, count the ones in a binary string of length $n$ by scanning once and retaining a binary counter. Its value ranges from zero to $n$, requiring $\lceil {\log }_2(n+1)\rceil$ bits for the counter. Keeping a separate copy of the full input would instead require $n$ bits. The computation can therefore use much less working storage than the amount of data it examines.

The maximum concerns simultaneously retained storage, not the total amount allocated and later reused over time. Bit complexity and a unit-cost model also need care here: treating an arbitrarily large integer as one storage cell can hide its growing representation size.

Theoretical computer science studies computation through mathematical models, algorithms and proofs. Computability theory asks which problems admit algorithms at all; computational complexity theory asks what resources solving them requires. Automata theory, mathematical logic and formal languages describe machines and representations. For example, a finite-state automaton recognizes a language using finitely many states, while a Turing machine provides a more general model with unbounded working storage. Separating a problem's specification from a particular implementation makes it possible to prove both algorithmic upper bounds and impossibility results.

A Turing machine is a model of computation with finite control, a tape of cells and a head scanning one cell at a time. An instruction of a Turing machine uses the current state and scanned symbol to determine a new state, a written symbol and a head movement. The finite transition rules form the machine's description; the tape supplies storage without a fixed global bound.

In a standard input convention, a finite word occupies part of an otherwise blank tape. A Turing machine configuration records the state, head position and tape contents, so the next-configuration relation determines each computation step. A machine can accept, reject or continue indefinitely. Recognizing a formal language permits nontermination on some nonmembers; deciding it requires an answer on every input.

The separation between a finite rule table and unbounded reusable storage makes the model useful for proving general statements about algorithms. Alan Turing's 1936 paper introduced this style of machine to analyze effective calculation; its original examples produce successive digits of numbers.^[ref] Multitape Turing machines change the storage organization and possible step counts while retaining the same computability power.