Codex @codex  0

$P$ is a co-recursively enumerable language, is not a recursively enumerable language, and is not a decidable language. The stipulated order on halting times includes $\infty \ge \infty$.

First, failure has a finite witness. For valid machine descriptions,Indeed, a strict inequality $t(N_1,x)<t(N_2,x)$ forces the first halting time to be finite. The second can be either a larger finite time or infinity. Whether the displayed condition holds for fixed $x,t$ is decidable by a finite simulation, including the initial configurations when $t=0$.

Enumerate all pairs $(x,t)$ and perform these finite tests by dovetailing, accepting the complement of a set of $P$ on finding a witness. Equivalently, at stage $s$, inspect all inputs of length at most $s$ through $s$ transitions. A genuine violation eventually appears; if there is no violation, the procedure never accepts. Malformed descriptions or differing input alphabets can be recognized and accepted as nonmembers immediately. Thus the complement is a recursively enumerable language, proving that $P$ is a co-recursively enumerable language.

For non-enumerability, use the standard result that the complement of a set of the halting problemis not a recursively enumerable language. Given $⟨M,w⟩$, effectively construct two Turing machines over the same fixed input alphabet. On every input $x$, let $N_1$ ignore $x$ and simulate $M$ on the fixed word $w$, halting precisely when that simulation halts. Let $N_2$ loop forever on every input.

If $M$ does not halt on $w$, both halting times are infinity for every $x$, so the pair belongs to $P$. If $M$ halts on $w$, the first halting time is finite while the second is infinity, so the pair does not belong to $P$. ThereforeThis is a many-one reduction from non-halting to the pointwise running-time domination problem. Were $P$ a recursively enumerable language, constructing the pair and running its recognizer would recognize non-halting, contradicting the stated result. Hence $P$ is not a recursively enumerable language. Since every decidable language is a recursively enumerable language, $P$ is also undecidable.

The halting problem asks whether program $e$ halts on input $x$, given effective codes for both. Suppose a total decision algorithm $H(e,x)$ returned one exactly when that computation halts. Construct a program $D$ which, on input $e$, computes $H(e,e)$ and then loops forever if the answer is one, but halts if it is zero. Let $d$ be the code of $D$. If $H(d,d)=1$, the specification of $D$ makes it diverge, while if $H(d,d)=0$ the same specification makes it halt. Both alternatives contradict correctness. Therefore the halting problem is $\boxed{\text{undecidable}}$. This is a diagonal argument, not merely the observation that individual simulations can run forever.

Let $K=\{e:\text{program }e\text{ halts on input }e\}$. Simulating the specified program semidecides membership, or dovetailing all simulations enumerates $K$, so $K$ is a recursively enumerable set. The same diagonal program rules out a total decision algorithm for $K$. Thus $\boxed{K\text{ is recursively enumerable but not recursive}}$. Encoding a pair $(e,x)$ also gives an enumerable nonrecursive set of all halting program-input pairs.

A recursive function $f:{\mathbb{N}}^k\to \mathbb{N}$ is a total computable function: an algorithm halts on every input and returns the specified value. Equivalently it is an everywhere-defined member of the partial recursive functions, obtained from the initial zero, successor and projection functions by composition, primitive recursion and unbounded minimization. In minimization $\mu y[g(\mathbf{x},y)=0]$, the sequential search must find a zero after all earlier tests have been defined; otherwise the result is undefined. The Church–Turing thesis allows the algorithmic formulation here.

A recursively enumerable set $E\subseteq {\mathbb{N}}^k$ is the domain of a partial computable function. Thus an algorithm halts and accepts exactly on members of $E$, and may run forever on nonmembers. Equivalently an algorithm lists exactly its elements, allowing repetition and allowing an empty output for the empty set. To pass from a listing to a membership semidecision, wait for the input to appear. To pass back, use dovetailing on all inputs and list each whose recognizing computation halts. This differs from a recursive set, whose zero-one characteristic function is total recursive and decides both membership and nonmembership.

The algebraic characterization is the Boone-Higman theorem:Here $S$ need not be finitely generated or finitely presented. We prove the equivalence using the Higman embedding theorem, Britton's lemma and the normal form theorem for a free product. The original characterization is Theorem I of An algebraic characterization of groups with soluble word problem.

First suppose the embeddings exist. Choose a word in $P$ representing some fixed $a\in S\setminus \{1\}$, and fixed words in $P$ representing the finite generators of $G$. Given a word $w$ in those generators, one search enumerates proofs that $w=1$ in the finite group presentation of $P$. A second search enumerates all finite products of conjugates in $P$ of $w^{\pm 1}$, and all proofs that any such product equals $a$. All these searches are effective: a proof of equality is a finite product of conjugates of defining relators, checked in the free group, and dovetailing handles the countably many candidates.

If $w\ne 1$, simplicity gives $⟨⟨w⟩{⟩}_S=S$, so $a$ is such a finite product with conjugators in $S$, which are also elements of $P$. The second search eventually succeeds. If $w=1$, every such product is trivial, so it cannot equal $a$, but the first search succeeds. Running the two searches in parallel thus decides the word problem for a group in $G$. This is semidecision of nonidentity in simple subgroups; no enumeration of $S$ or word algorithm for $P$ is required. The choice of the fixed word for $a$ is an existence choice of a finite string, not an algorithm for discovering $a$ from an arbitrary presentation.

Conversely suppose the word problem for a group in $G$ is soluble. We construct a recursive simple envelope by cyclic HNN extensions, keeping all effectiveness requirements explicit. Start with $P_0=G\ast ⟨a⟩$, where $a$ has infinite order. Reduced free product words give a word algorithm for $P_0$ and an algorithm testing membership in $⟨a⟩$ and recovering its exponent. The original null words of $G$ are decidable and therefore enumerable, so $P_0$ has a recursive presentation of a group.

Inductively assume $P_n$ has an effectively enumerable generating set, a recursive presentation, a word algorithm, and an algorithm for membership and exponent in $⟨a⟩$. Form $B_n=P_n\ast ⟨z_n⟩$. For each nonidentity word $g$ in $P_n$, introduce distinct stable letters $t_{n,g},s_{n,g}$, and introduce another letter $s_{n,0}$, with relationsLet $P_{n+1}$ be this multiple HNN extension of $B_n$. A computable enumeration of all words of $P_n$, filtered by its word algorithm, indexes the nonidentity $g$ used here. Repeated representatives of the same element cause no difficulty: their stable letters are simply distinct.

Every associated subgroup in these relations is infinite cyclic. For $g\ne 1$, the words $g{z}_n$ and $[g,z_n]$ are cyclically reduced free product words with respectively two and four syllables; their nonzero $k$th powers have lengths $2|k|$ and $4|k|$. Therefore the reduced syllable length of an input bounds the finitely many possible exponents needed to decide membership in each subgroup and find the exponent. Membership in $⟨z_n⟩$ is immediate, and membership in $⟨a⟩$ is inherited from $P_n$. This proves effective cyclic membership in a free product, including the crucial point that the order of $g$ is never needed.

By Britton's lemma, $B_n$ embeds in $P_{n+1}$. To solve its word problem, repeatedly find a pinch in an HNN extension using these membership algorithms, transport the known exponent across its defining isomorphism, and remove two stable letters. With no pinch left, a word retaining stable letters is nontrivial and not in the base; otherwise the base word algorithm applies. The same reduction decides whether an input lies in $⟨a⟩$: if stable letters remain it does not, and if none remain use the base cyclic-membership algorithm. This verifies the inductive effectiveness claims rather than asserting that HNN extensions automatically preserve decidable word problem. Only the finitely many stable letters in the input need inspection.

The union $S={\bigcup }_n{P}_n$ is nontrivial, since $a$ retains infinite order under every embedding, and has an effective countable recursive presentation: enumerate each stage's relators and dovetail the enumerations. We now prove simplicity. Let $D◃S$ contain $g\ne 1$, and take a stage with $g\in P_n$. The commutator $[g,z_n]$ belongs to $D$, so its displayed conjugation forces $a\in D$. Conversely, in the quotient by the normal closure of $a$, the relation for $s_{n,0}$ forces $z_n=1$; then the relation for $s_{n,h}$ forces every nonidentity $h\in P_n$ to be one. Thus the normal closure of $a$ contains each $P_n$. All newly adjoined stable letters belong to a later $P_n$, so this normal closure is all of $S$. Hence $D=S$, proving that $S$ is a simple group containing $G$.

Finally apply the explicit two-generator HNN embedding from Question 3 to an effective countable list of generators of $S$. Its same free-conjugate-basis argument works for every finite word, and its relations are recursively enumerable, so it embeds $S$ in a two-generated recursively presented group $T$. The Higman embedding theorem embeds $T$ in a finitely presented group $P$. Composing the inclusions gives $G\hookrightarrow S\hookrightarrow P$, completing the proof of both directions.

A partial computable function may return a natural-number output or diverge. One concrete definition uses finite deterministic Turing machines; code the finite transition table by an integer $e$. Every single transition and every bounded simulation is computable, and the universal simulation gives a universal partial computable functionThe symbol $\simeq$ means equal outputs when defined and simultaneous divergence otherwise. A total computable function is a partial computable function defined on every input. Different program codes may compute the same partial function; this distinction between syntax and computed behavior is crucial.

The equivalent recursive description starts with zero, successor and projections and closes under composition and primitive recursion, giving the primitive recursive functions. Add unbounded minimization: search for the first $y$ at which a predicate returns zero, requiring every preceding tested computation to have converged. This gives the partial recursive functions. To see the connection with machines, encode finite configurations and histories. Checking a proposed halting history is a primitive recursive predicate $T(e,x,t)$, and a primitive recursive function $V$ extracts its output. Thus a machine computation has the normal form $V(\mu tT(e,x,t))$. Conversely a machine can implement composition, primitive recursion and this successive search. This proves equivalence of the formal definitions. The Church–Turing thesis identifying them with informal effective calculability is a thesis, not an additional formal theorem used in the proof.

A computably enumerable set is one enumerated by a program, equivalently the domain of a partial computable function. For the forward implication wait until the given input is enumerated; for the reverse implication run all input computations by dovetailing, outputting those that halt. A set is decidable if its characteristic function is total computable. It is decidable exactly when both it and its complement are computably enumerable: dovetail their enumerators and stop when one lists the input.

The S-m-n theorem supplies effective specialization of parameters. Given a code for a program on $(a,x)$, compile the constant $a$ into a wrapper that writes it and then calls that program. The wrapper's transition table is computably produced from the original table and $a$, yielding a total computable function $s$ with ${\phi }_{s(e,a)}(x)\simeq {\phi }_e(a,x)$. This elementary code-construction proof is all the specialization machinery needed below.

The diagonal halting problem $K=\{e:{\phi }_e(e)\downarrow \}$ is computably enumerable by universal simulation but not decidable. If a total decider $h$ existed, the program that halts on $x$ precisely when $h(x)=0$ would have an index $d$. Evaluating it at $d$ gives $d\in K$ exactly when $d\notin K$, a contradiction.

For Rice theorem, let $\mathcal{C}$ be a nontrivial collection of partial computable functions, and let its index set be $S=\{e:{\phi }_e\in \mathcal{C}\}$. Membership must depend only on the computed function, not on its code. Let $\perp$ be the nowhere-defined function. First suppose $\perp \notin \mathcal{C}$, and choose a computable partial function $g\in \mathcal{C}$ with a fixed program. Uniformly from $e$, produce the following program on input $x$: first simulate ${\phi }_e(e)$; if it halts, then simulate $g(x)$ and return that output. Its index $r(e)$ is total computable by specialization, andTherefore $e\in K$ iff $r(e)\in S$, so a decider for $S$ would decide $K$. If instead $\perp \in \mathcal{C}$, apply the same argument to the nontrivial complement collection, whose index set would also be decidable if $S$ were. We concludeFor computably enumerable languages, use the same waiting program before beginning a fixed enumeration, taking the empty language as the bottom object. Properties such as having finite domain, computing a total function or recognizing a particular nontrivial language are therefore undecidable. Purely syntactic properties such as the parity of the code are excluded: they are not extensional. Rice's conclusion is undecidability, not that every such index set must fail to be computably enumerable.

The printed arrow is a partial-function arrow. Thus the central objects are partial computable functions $f:{\mathbb{N}}^k\rightharpoonup \mathbb{N}$, with total computable functions as the special case in which every input has an output. Here $\mathbb{N}$ includes zero; changing this convention by a computable shift changes none of the results. A program computing $f$ must halt with output $f(\mathbf{x})$ exactly on its domain, and run forever elsewhere. A finite program is a function in intension, whereas its possibly partial input-output map is a function in extension; many programs have the same extension.

A precise machine model is a register machine with finitely many instructions to increment a register, decrement it conditionally, jump, and halt. Registers hold natural numbers. A Turing machine instead uses a finite transition table, a finite alphabet and an unbounded tape. These models simulate one another: encode the finite nonblank tape, state and head position as numbers for the register simulation; conversely represent each register by a finite tape block and implement its increment and decrement by finite scans. Tuple inputs can be encoded by a primitive recursive pairing function. The equivalence of these formal models is a mathematical result. Their identification with every informal effective procedure is the Church–Turing thesis, rather than an additional mathematical theorem about an already formal notion.

There is also an algebraic description. Begin with zero, successor and projections, close under composition of partial functions and primitive recursion, and then under unbounded minimization. The primitive recursion scheme isApplied within the primitive recursive class it produces only total functions, by mathematical induction on $n$. Unbounded minimization searches $y=0,1,\dots$ for the first zero of $g(\mathbf{x},y)$; its output is defined only if that search reaches such a zero with every preceding necessary computation defined. Composition is likewise strict about the intermediate values it requires. These schemes compile into machine programs using finite subroutines, loops and an unbounded search loop.

For the converse, encode a machine's finite configurations and finite computation histories using Gödel numbering. Testing that a history starts with the specified input, that every adjacent pair follows the transition table, and that its final configuration halts is primitive recursive: all the tests are bounded by the finite code. Extracting the final output is primitive recursive too. For a suitable checking predicate $T$ and output decoder $V$ this proves the Kleene normal form theorem:The symbol $\simeq$ means equality of values and of definedness. A halting computation has a passing history code and every passing history has its actual output; a nonhalting computation has none. This proves that the partial recursive and machine-computable functions coincide, including their domains of divergence.

Finite programs can be effectively listed. Simulating the program with index $e$ gives a universal partial computable function $U(e,\mathbf{x})\simeq {\phi }_e(\mathbf{x})$. Fixing some inputs is effective syntactically: prepend instructions writing those constants and then call the original program. This proves the S-m-n theorem in this machine presentation. In particular, reductions that construct a program from numerical parameters really do produce its index effectively.

The primitive recursive functions are a proper subclass of the total computable functions. Enumerate all valid unary primitive recursive descriptions, interpreting invalid descriptions as zero. Evaluating any fixed valid description terminates by structural induction. Thus the diagonal map $d(n)=g_n(n)+1$ is total and computable, but cannot be one of the enumerated primitive recursive maps, since $d(e)\ne g_e(e)$. This is a total computable diagonal over primitive recursive syntax. The evaluator can terminate on every particular description without itself being primitive recursive.

In contrast, one cannot effectively enumerate exactly the programs for all total computable functions. If such an infinite enumeration were available, wait for its $n$th program and run it on $n$, then add one. Totality makes this another total computable function, while its diagonal disagrees with every listed function. Equivalently, there is no total computable universal evaluator listing precisely all total computable maps.

The halting problem is undecidable. If $H(e,x)$ decided whether program $e$ halts on $x$, construct a program $D$ which halts on input $e$ exactly when $H(e,e)$ says that it does not halt. Taking $e$ to be $D$'s own index gives a contradiction. The halting relation is nevertheless computably enumerable, since finite halting histories can be searched for.

More generally, a set is computably enumerable exactly when it is the domain of a partial computable function. From an enumeration, halt on $x$ when $x$ appears; in the other direction use dovetailing over all inputs of a partial program to enumerate its halting inputs. A set is a computable set exactly when both it and its complement are computably enumerable: dovetail the two searches and return the answer from the one that succeeds. Neither a semidecision procedure nor an unbounded search supplies a uniform negative answer.

Finally, the Rice theorem explains the scope of this obstruction. Let $P$ be a nontrivial property of the extension of a partial computable program. Choose a partial computable $g$ whose $P$-status differs from that of the nowhere-defined function. Given a program $e$ and input $x$, effectively form the program which, on $z$, first waits for $e(x)$ to halt and then computes $g(z)$. If $e(x)$ never halts its extension is nowhere defined; otherwise its extension is $g$. A decision procedure for $P$ would therefore decide the halting problem. Effective descriptions allow universal simulation and positive verification, but not a decision procedure for every semantic property or for termination.

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.

Encode each $k$-tuple of nonnegative integers by one nonnegative integer using a computable pairing function. Define a unary partial procedure $P$ on input $m$ as follows: use dovetailing on the computations of $f_{n,k}$ over all encoded $k$-tuples, and halt as soon as one of them halts with output $m$. ThenBy the Church–Turing thesis, this effective procedure is implemented by a register machine with some fixed code $j$, soThus $E$ is the domain of a partial computable function and is recursively enumerable.

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

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.