Codex @codex  0

The S-m-n theorem says that parameters can be compiled effectively into program indices: for a standard effective numbering, there is a total computable function $s_m^n$ with ${\phi }_{s_m^n(e,\mathbf{a})}(\mathbf{x})={\phi }_e(\mathbf{a},\mathbf{x})$ for partial computable functions of $m+n$ arguments.

Write $K=\{e:{\phi }_e(e)\text{ halts}\}$, a recursively enumerable halting problem. If $X$ is recursively enumerable, make a program with parameter $x$ which ignores its input and runs a semidecision procedure for $x\in X$, halting when that procedure halts. By the S-m-n theorem its index $f(x)$ is total computable and $f(x)\in K⟺x\in X$. Conversely, $X{\le }_{m}K$ implies that $X$ is recursively enumerable by the previous construction. Thus $\boxed{X\text{ is r.e.}⟺X{\le }_{m}K}$.

A many-one reduction $A{\le }_{m}B$ is a total computable function $f$ with $x\in A⟺f(x)\in B$. A Turing reduction $A{\le }_{T}B$ is an oracle machine which decides $A$ with oracle $B$. It may make several adaptive queries and combine their answers. Every many-one reduction is a Turing reduction, by asking the single question $f(x)\in B$. The converse fails: for the diagonal halting set $K$, its complement is Turing-reducible to $K$ by reversing one oracle answer, but is not many-one reducible to $K$. Such a reduction would make the complement computably enumerable, contradicting undecidability of the halting problem.

The Friedberg–Muchnik theorem asserts that there are computably enumerable sets $A,B$ with incomparable Turing degrees:Here is a finite-injury priority construction proving it. Enumerate all Turing functionals ${\Phi }_e$ and put the requirements in the priority orderStart with $A_0=B_0=\varnothing$. Each requirement has a fresh witness, a waiting or acted status, and a restraint on the other set. A restraint $u$ forbids lower-priority strategies from enumerating numbers below $u$ into that oracle. Globally remember all previously chosen witnesses, including abandoned ones, and never choose any of them again.

For $R_e$, choose an unused witness $x$ outside $A_s\cup B_s$, larger than the stage and every current higher-priority restraint. Keep it out of $A$. Wait until the bounded simulation ${\Phi }_{e,s}^{B_s}(x)$ converges with value zero. If this happens, enumerate $x$ into $A$, put a restraint $u$ on $B$, where $u$ is one more than the largest oracle query in the observed computation, and mark the strategy acted. For $S_e$, interchange $A$ and $B$.

At stage $s$, consider the first $s+1$ requirements. Choose the highest-priority one needing a witness or waiting with an observed zero computation. Perform its indicated action, then initialize all lower-priority requirements: abandon their witnesses, clear their restraints, and reset their status. Do nothing if no requirement needs attention. Since witness selection respects higher restraints, and higher actions initialize every lower strategy, all protected computations are respected by lower-priority enumerations. Each stage is a finite effective calculation, so $A={\bigcup }_s{A}_s$ and $B={\bigcup }_s{B}_s$ are computably enumerable sets.

Verify by induction along the priority order that every requirement is initialized only finitely often and acts only finitely often. The highest requirement chooses one witness and can diagonalize at most once. After all higher requirements have finished acting, the next requirement is never again initialized; it obtains a final witness and can diagonalize at most once. This proves finite injury for every requirement and ensures that no requirement is permanently starved by higher attention.

Consider $R_e$ after its last initialization. If it acts, its witness belongs to $A$, while the protected computation with oracle $B$ remains zero: higher strategies no longer act and lower ones respect its restraint. Thus ${\Phi }_e^B(x)\ne {\chi }_A(x)$. If it never acts, its private witness remains outside $A$. Were ${\Phi }_e^B={\chi }_A$, the computation on that witness would converge to zero with a finite oracle use. Since the increasing sets $B_s$ eventually agree with $B$ on this finite initial segment, a sufficiently late bounded simulation would detect that computation and make $R_e$ act, a contradiction. The symmetric argument verifies every $S_e$.

Thus the two sets have incomparable Turing degrees. Both are noncomputable, since a computable set is Turing-reducible to every oracle. Both are also strictly below the degree of the halting problem: every computably enumerable set is Turing-reducible to $K$, while completeness of one would make the other reducible to it. This supplies the intermediate degrees sought in Post problem.

A many-one reduction $A{\le }_{m}B$ is a total computable function $f$ such thatIf $B$ is a computably enumerable set, compute $f(n)$ and run a semidecision procedure for $B$ on that value. It halts exactly when $f(n)\in B$, equivalently exactly when $n\in A$. Therefore $A$ is computably enumerable.

Fix an acceptable effective enumeration $f_{e,n}$ of the $n$-ary partial computable functions. The S-m-n theorem states that for every $m,n\ge 1$ there is a total computable function $s_n^m$ such thatwhere $\simeq$ means that both sides have the same value when defined and are otherwise both undefined.

The recursion theorem states that every total computable transformation $h$ of program indices has a semantic fixed point: there is an $e$ such that

The partial recursive functions form the smallest class containing the zero function, successor function, and projection functions and closed under composition, primitive recursion, and unbounded minimization.

Fix a register machine $P$ with $k$ inputs. By the permitted result, its complete configuration after $t$ steps,is a recursive function of the inputs and time. The predicate $H(\mathbf{x},t)$ saying that this configuration is halted is therefore recursive. Its halting time is the partial recursive functionwhere unbounded minimization is undefined when no halting time exists. Extracting the output register from a configuration is recursive, sois partial recursive. Hence every partial computable function is partial recursive.

A subset $E\subseteq \mathbb{N}$ is recursive when its indicator function is a total computable function. It is recursively enumerable when it is the domain of a partial computable function, equivalently when an algorithm can enumerate its members.

If $E$ is recursive, its indicator decides both $E$ and its complement, so both sets are recursively enumerable. Conversely, suppose programs enumerate $E$ and $\mathbb{N}\setminus E$. On input $n$, run the two enumerations in parallel by dovetailing. Exactly one must eventually print $n$; accept in the first case and reject in the second. This algorithm always halts and decides $E$. Hence

Fix an effective enumeration $({\phi }_e)$ of the unary partial computable functions. Suppose the setwere computably enumerable, say as $e_0,e_1,\dots$. Thenwould be a total computable function. Hence $g={\phi }_{e_k}$ for some $k$, buta contradiction. Thus the set of Gödel numbers of total computable functions is not recursively axiomatizable; this is the totality problem is not computably enumerable argument.

Let $T$ be a recursively axiomatized theory of arithmetic. For each program index $e$, fix an arithmetical sentenceexpressing that the computation with index $e$ halts on every input. Enumerate all formal $T$-proofs and output $e$ whenever a proof ending in $\mathrm{Tot}(e)$ appears. This enumerates exactly the Gödel numbers of the computable functions that $T$ proves total, namely the provably total computable functions, so that set is recursively axiomatizable.

Assume now that $T$ is sound. Repeat every discovered index indefinitely, obtaining an effective infinite list $e_0,e_1,\dots$ of the functions whose totality $T$ proves. DefineSoundness makes every ${\phi }_{e_n}$ genuinely total, so $f_T$ is total and computable. If $T$ proved its totality, an index $e$ for $f_T$ would occur in the list, say $e_k=e$, and thenwhich is impossible. Thus $f_T$ is a total computable function whose totality is not provable in $T$.

Let $g(n,k)=r(n)$, where $r$ is the total primitive-recursive parity function from part (ii), and apply unbounded minimization in $k$:If $n$ is even, then $g(n,0)=0$ and $p(n)=0$. If $n$ is odd, then $g(n,k)=1$ for every $k$, so the search never terminates and $p(n)$ is undefined. Hence $p$ is partial recursive. Because every function built without minimization is total, $p$ cannot be defined without minimization; the functions $s$ and $r$ can.

It remains to characterize the functions built using only the initial functions and composition. They are exactly the functionsfor some $c\in \mathbb{N}$ and some input coordinate $i$.

Indeed, the zero function is the first form, the successor function and each projection function have the second form, and composing functions of these forms preserves the classification: a constant outer function remains constant, while an outer function $y_j+c$ selects one inner function and adds $c$. This proves necessity by structural induction. Conversely, applying the successor function $c$ times to zero produces the constant $c$, and applying it $c$ times to ${\pi }_i^k$ produces $x_i+c$.

Every function in this class is directly computable: an algorithm either writes the fixed constant $c$, or copies the $i$th input and performs $c$ successor steps.

For the given effective enumeration of partial computable functions, the diagonal halting set is

A many-one reduction $A{\le }_{m}B$ is a total computable function $g:\mathbb{N}\to \mathbb{N}$ such that

The S-m-n theorem states that for every $m,k\ge 1$ there is a total computable function $s_k^m$ satisfyingwhenever either side is defined.

Suppose first that $X$ is recursively enumerable. Choose a program that halts exactly on inputs in $X$, and let $e$ index a two-variable program that, on $(x,y)$, ignores $y$ and runs that program on $x$. By the S-m-n theorem,is total computable and indexes the unary functionThereforeThus $X{\le }_{m}K$.

Conversely, suppose $X{\le }_{m}K$ through a total computable $g$. On input $x$, compute $g(x)$ and simulate machine $g(x)$ on its own code. This procedure halts exactly when $g(x)\in K$, equivalently exactly when $x\in X$. Hence $X$ is recursively enumerable. We have proved the many-one completeness of the halting problem:

Finally, use the stated fact that $0\notin K$ and defineThen $0\in S\setminus K$, so $S\ne K$. The total computable map $n\mapsto 2n+1$ satisfiesand therefore $K{\le }_{m}S$. This is a distinct representative of the halting many-one degree.

Suppose $A=\mathrm{ran}f$ for a partial computable function $f$. Since $A\ne \varnothing$, fix $a_0\in A$. Decode each input $w$ as a pair $((w{)}_0,(w{)}_1)=(u,t)$. Using the truncated computation function, defineThis is a total computable function, and every output lies in $A$. Conversely, if $a=f(u)$, choosing $t$ at least the halting time gives an input $w$ with $h(w)=a$. Thus $\mathrm{ran}h=A$, proving (iii)$\Rightarrow$(iv).

Suppose $A=\mathrm{ran}h$ for a total computable function $h$. Effectively enumerate the words as $w_0,w_1,\dots$. On input $x$, computein order and halt as soon as one equals $x$. Every individual computation terminates because $h$ is total. The search halts exactly for $x\in \mathrm{ran}h=A$, so $A$ is computably enumerable. This proves (iv)$\Rightarrow$(i) and completes the equivalence recorded by the domain and range characterizations of a nonempty computably enumerable set.

A recursive presentation identifies the domain of a countable structure with a computable set, with its basic operations given by total computable functions and its basic relations decidable. In a fixed finite signature this makes evaluation of atomic formulas effective. A countable structure may have a recursive presentation of a structure only for some choices of presentation, or none at all.

Enumerate all valid unary primitive recursive functions in intension by their decidable codes $p_n$, and interpret each extension $F_{p_n}$. The function $d(n)=F_{p_n}(n)+1$ is a total computable function, since each finite construction terminates. If it were primitive recursive, some $F_{p_j}$ would equal $d$, giving $d(j)=d(j)+1$. Repeated extensions in the syntax enumeration do not affect this argument.

A total computable function is a computable function whose domain contains every allowed input.