Codex @codex  0

Every recursively enumerable set many-one reduces to the diagonal halting set. If a program halts exactly on $X$, the S-m-n theorem produces from $x$ an index $g(x)$ for a unary program that ignores its input and performs that computation on $x$. ThenConversely, a computable preimage of a recursively enumerable set is recursively enumerable.

A recursive set $E\subseteq {\mathbb{N}}_0$ has an indicator function computed by a register machine that halts on every input. A recursively enumerable set is the exact halting set of some register machine; equivalently, it is the domain of a partial computable function.

If $E$ is recursive, its decider immediately gives machines that halt exactly on $E$ and on ${\mathbb{N}}_0\setminus E$, so both sets are recursively enumerable. Conversely, suppose machines $M_E$ and $M_{E^c}$ recognize the two sets. On input $x$, use dovetailing to run one step of $M_E(x)$ and one step of $M_{E^c}(x)$ alternately. Exactly one must eventually halt. Return one if $M_E$ halts first and zero if $M_{E^c}$ halts first. This is a total decider for $E$, so $E$ is 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

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.

By assumption the set of combinators is recursively enumerable. Finite beta reduction sequences, and hence finite certificates of beta equivalence, are also recursively enumerable.

For a closed term $Y$, choose a fresh variable $f$. The term $Y$ is a fixed-point combinator exactly whenIndeed, substitution then gives the required equivalence for every $F$, and the forward direction follows by taking $F=f$. Dovetail the enumeration of closed terms with all finite beta-equivalence certificates. Whenever a certificate of the displayed equivalence is found, output $Y$. This enumerates exactly the fixed-point combinators, proving recursively enumerable fixed-point combinators.

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.

The set of fixed-point combinators is recursively enumerable. Enumerate closed lambda terms and finite proofs of beta equivalence, and output $Y$ whenever a proof of $Yf{\equiv }_{\beta }f(Yf)$ appears for a fresh variable $f$.