Codex @codex  0

For a fixed effective machine coding, the predicate that program $e$ on input $x$ halts within $t$ steps is primitive recursive. Code finite configurations, iterate a total single-step function by primitive recursion, and test for the halt state. This supplies a bounded simulation even though the unrestricted halting problem is undecidable.

If $M$ halts on every input, simulate $M$ on input $n$ while counting its steps, and output that count when it halts. The resulting function $t_M(n)$ is a total computable function. Consequently yes: one may take the exact running time,This construction does not promise a simple closed expression or a bound of any particular complexity class; it uses the promised totality of this particular machine.

For a machine computing a partial computable function, its exact halting-time function is still a partial computable function, with the same domain. A finite bound cannot cover a genuinely infinite computation. Even restricting attention to inputs on which $M$ halts, a total computable function bounding all halting times need not exist. In fact the precise characterization is the computable bound on halting time criterion:For the forward implication, compute $f(n)$ and simulate $M(n)$ for that many steps. If it has not halted, the proposed bound ensures that it never will. This decides the domain. Conversely, first decide whether $n$ is in the domain; return zero outside it and the simulated halting time inside it. This defines a total computable function satisfying the bound. The time needed to compute the bound itself is irrelevant to this argument.

A universal halting recognizer has undecidable domain by the halting problem, so it has no such total bound. On the other hand, a machine that immediately halts on even inputs and loops on odd inputs computes a nontotal partial computable function but has a constant bound on its halting times. Thus nontotality alone does not decide whether a total bound exists.

A circuit size class $\mathrm{SIZE}(T(n))$ consists of languages whose length-$n$ indicator functions have Boolean circuits of size at most $T(n)$, for all sufficiently large $n$, over a fixed finite bounded-fan-in complete basis. The notation $\mathrm{SIZE}(O(T(n)))$ allows a constant factor. Input-node counting conventions do not affect the polynomial and exponential bounds here.

The nonuniform class P/poly isThere is no requirement that a uniform algorithm construct the Boolean circuits. Equivalently, a polynomial-time machine can receive polynomial-length advice depending only on the input length, and the advice need not be computable.

Choose an undecidable set $A\subseteq \mathbb{N}$, for example the set in the halting problem of indices of machines that halt on empty input, and define $U_A=\{1^n:n\in A\}$. For each length $n$, use a constant-zero Boolean circuit if $n\notin A$, and an AND of all $n$ input bits if $n\in A$. These Boolean circuits have size $O(n+1)$ and accept exactly $U_A$. Thus undecidable unary languages with linear-size circuits belong to P/poly.

Every NP language is decidable by enumerating its finitely many polynomial-length certificate encodings and running the polynomial-time verifier. If $U_A$ were decidable, testing $1^n$ would decide $A$, a contradiction. ThereforeThis separates the classes in the stated direction; it does not claim that NP is not contained in P/poly.

For subsets $A,B\subseteq \mathbb{N}$, a many-one reduction $A{\le }_{m}B$ is a total computable function $h$ with $n\in A⟺h(n)\in B$. A Turing reduction $A{\le }_{T}B$ is an oracle machine with oracle $B$ computing the total indicator function ${\chi }_A$. It may make several adaptive oracle queries. A many-one reduction gives a Turing reduction using one query; the definitions impose no enumerability assumption on $A,B$.

The Friedberg–Muchnik theorem asserts that there exist computably enumerable sets $A,B$ withWe give the finite-injury priority construction. Fix an effective list ${\Phi }_e$ of Turing functionals and imposein priority order $R_0,S_0,R_1,S_1,\dots$. Each strategy has an unassigned, waiting or protected state; a private witness $x$ when assigned; and a restraint on the oracle set when protected. All witnesses, even abandoned ones, are permanently recorded and never reused. A strategy for $R_e$ is the only strategy ever allowed to enumerate its witness into $A$; the analogous statement holds for $S_e$ and $B$.

Start with finite sets $A_0=B_0=\varnothing$. At stage $s$, inspect the first $s+1$ strategies. An unassigned strategy needs attention. A waiting $R_e$ strategy needs attention if the computation ${\Phi }_e^{B_s}(x)$ converges within $s$ steps; waiting $S_e$ is symmetric. Act on the highest-priority strategy needing attention, if any. On assignment choose a fresh witness greater than $s$, every earlier witness and every higher-priority restraint, and enter the waiting state. On a convergence with output $v$ and oracle use $u$, act as follows: if $v=0$, enumerate the witness into its own target set; if $v\ne 0$, leave the witness out. Enter the protected state and restrain the oracle below $u$. The current characteristic value at the witness is now different from $v$, including outputs other than zero or one. Whenever a strategy acts, initialize every lower-priority strategy, discarding its current witness and restraint but retaining the permanent record of used witnesses. If none needs attention, change nothing.

Every enumeration respects higher-priority restraints: its witness was chosen beyond them after its last initialization, and a later higher-priority action would have initialized it. Each stage is effective, finite and monotone in $A_s,B_s$, so $A={\bigcup }_s{A}_s$ and $B={\bigcup }_s{B}_s$ are computably enumerable. Lower-priority restraints may be violated by a higher-priority action, exactly the allowed injuries.

Induct on priority to verify finite injury and satisfaction. Once all higher-priority strategies have made their last actions, the current strategy receives its final assignment and can act at most once more, on a convergence. If convergence is observed it is then protected permanently; otherwise it waits without further action. In either case every strategy acts only finitely often. After the final initialization of $R_e$, if it acts on a convergence, no higher strategy subsequently changes its assumptions and every lower strategy respects its restraint. The observed oracle computation therefore remains valid for the final $B$, while the permanently private witness retains the opposite characteristic value in $A$.

If it waits forever, then ${\Phi }_e^B(x)$ cannot converge. A convergent final computation uses only finitely many oracle bits; those bits in the increasing enumeration $B_s$ eventually equal their final values. For a sufficiently large stage the same finite computation would have been observed, and after the higher strategies have stopped it would receive attention, contradicting perpetual waiting. Thus $R_e$ is satisfied either by disagreement or by divergence. The same proof satisfies every $S_e$. This is private-witness diagonalization for incomparable enumerable sets, with the finite-injury verification supplying the required permanent disagreements.

A computable set reduces to every oracle, so incomparability makes both sets noncomputable. Every computably enumerable set reduces to the halting problem; if either of these sets had the halting degree, the other would reduce to it. Thus their c.e. degrees are also incomplete, giving the intermediate degrees sought by the Post problem.

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.

Rice theorem says that every nontrivial extensional property of programs computing partial functions is undecidable. Equivalently, a nontrivial index set cannot be a computable set.

Let $A$ be such an index set. Replacing $A$ by its complement if necessary, assume that the nowhere-defined function has no index in $A$. Since the property is nontrivial, choose an index $a\in A$. If membership in $A$ were decidable, we could decide the diagonal halting problem as follows. For each $x$, defineBy the S-m-n theorem, a total computable function $q$ produces an index $q(x)$ for ${\psi }_x$. If $f_{x,1}(x)$ diverges, then ${\psi }_x$ is nowhere defined and $q(x)\notin A$. If it halts, then ${\psi }_x\simeq f_{a,1}$ and extensionality gives $q(x)\in A$. A decider for $A$ would therefore decide whether $f_{x,1}(x)$ halts, a contradiction. Hence $A$ is undecidable.

Let $K\subseteq \mathbb{N}$ be the undecidable set denoted $\mathbb{K}$ in the question. The language satisfies the pumping lemma for regular languages with pumping length one. For any nonempty $s\in L$, write $s=xyz$ with $x=\epsilon$, $y$ its first symbol, and $z$ the remaining suffix.

If $s\in b^{\ast }$, then $x{y}^{i}z\in b^{\ast }$ for every $i\ge 0$. Otherwise $s=wa{b}^n$ for some $n\in K$. If the chosen first symbol lies in $w$, pumping it preserves the same final suffix $a{b}^n$. If $w=\epsilon$, then $s=a{b}^n$: pumping down gives $b^n\in b^{\ast }$, while every positive pump gives $a^i{b}^n$ and all but its last $a$ can be absorbed into $w$. Thus every sufficiently long word has a valid pumping decomposition.

Nevertheless, if $L$ were regular language, closure under intersection would makeregular. A finite automaton deciding this unary language would decide whether $n\in K$ by running it on $a{b}^n$, contradicting the halting problem. ThereforeThis is a nonregular language satisfying the pumping lemma.

The setis the diagonal halting set. It is recursively enumerable by simulating the coded machine, but it is not recursive by the halting problem diagonal argument.

By contrast, ${\mathbb{K}}_{100}$ is recursive: decode $n$, reject it if it is not a program code, otherwise simulate the program on input $n$ for exactly $100$ steps and accept precisely if it has halted. This bounded computation always terminates. Thus

Fix an effective enumeration of register-machine programs. The $n$th register machine is $P_n$, and its domainis the $n$th recursively enumerable set. A many-one reduction $A{\le }_{m}B$ is a total computable function $h$ satisfying $x\in A⟺h(x)\in B$. Rice theorem says that every nontrivial property depending only on the computed partial function, or equivalently on an r.e. set in its extensional form, has an undecidable index set.

There is no total equality algorithm: it would decide whether $W_n$ is empty by comparing it with a fixed index for the empty set, contradicting Rice's theorem.

There is no partial algorithm that halts exactly when $W_m=W_n$ either. Given $e$, effectively construct an index $h(e)$ whose machine enumerates nothing unless $P_e(e)$ halts, after which it enumerates $0$. ThenA semialgorithm for equality with a fixed empty index would enumerate the complement of the halting problem $K$. Since $K$ is r.e., both it and its complement would then be r.e., making $K$ recursive, a contradiction.

For an effective enumeration $(W_w{)}_{w\in \mathbb{W}}$ of the computably enumerable languages, the diagonal halting problem isEquivalently, if $f_{w,1}$ is the unary partial function coded by $w$, thenThus $\mathbf{K}$ is the diagonal halting set.

Post problem asks whether a computably enumerable set can have a Turing degree strictly between the computable degree and the degree of the halting problem. The Friedberg–Muchnik theorem answers yes by constructing two incomparable computably enumerable degrees.