Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 24 (Computable Function Theory)

Take $\mathbb{N}=\{0,1,2,\dots \}$ and fix a standard effective enumeration $({\phi }_e)$ of the unary partial computable functions by program texts. WriteThe diagonal halting set $K$ is not a computable set: a supposed decision procedure would give a program that halts on input $e$ exactly when $e\notin K$, contradicting its own index. Each $K_s$ is finite and uniformly decidable by bounded simulation of a computation, and $K_s\subseteq K_{s+1}$ with union $K$.

For $a<b<c$, define the computable colouringThis is a two-part decidable set partition on three-element subsets: sort the three inputs and perform the two finite simulations. Here $[0,a)=\{0,\dots ,a-1\}$. The halting-stage colouring of triples cannot have an infinite homogeneous set for a colouring of colour $1$. Indeed, fix its least element $a$. The finitely many bits of $K_s\cap [0,a)$ eventually stabilize. Choose two later elements $b<c$ of the putative homogeneous set for a colouring beyond that stabilization stage; the corresponding triple has colour $0$.

Now suppose $H$ is an infinite homogeneous set for a colouring of colour $0$. Its membership oracle computes $K$: to decide whether $n\in K$, search for $a,b\in H$ with $n<a<b$, and return whether $n\in K_b$. For every $c\in H$ above $b$, homogeneity gives $K_c\cap [0,a)=K_b\cap [0,a)$. Since $H$ is unbounded, taking such $c$ arbitrarily large proves that this common finite set is $K\cap [0,a)$. ThusIf $H$ were a computable set, the displayed Turing reduction would decide $K$, a contradiction. The displayed decidable two-colouring has no infinite decidable homogeneous set.

For the second construction, let $2^{<\omega }$ be the finite binary strings, with coordinates starting at $0$, and define the computable binary treeMembership is decided by finitely many tests using bounded simulation of a computation. It is a binary tree of finite strings: if a string satisfies the tests, each prefix satisfies its shorter and fewer tests. The infinite paths through a binary tree are exactlyThis set is nonempty: at a coordinate whose diagonal computation halts with a binary value choose the other value, and choose either bit elsewhere. This is an existence argument, not a proposed computable decision procedure for convergence. No member is a total computable function. If $f={\phi }_d$ were a total binary-valued function, the condition at $d$ would say $f(d)\ne {\phi }_d(d)=f(d)$. Thus each member is a binary diagonally noncomputable function.

Moreover, $[T]$ has no isolated point. There are arbitrarily large indices of programs that never halt: for example, distinct program texts with successively more unused instructions followed by an infinite loop provide infinitely many such indices in the usual syntactic program coding. At every one of these coordinates the bit is unrestricted. Given any $f\in [T]$ and any prefix length $n$, change its bit at one such index $e\ge n$ and leave all other bits unchanged. The resulting different path still belongs to $[T]$ and has the same length-$n$ prefix. Since a path space is closed in Cantor space, $T$ is decidable, $[T]$ is nonempty and perfect, and no infinite path is computable.

There is a definition issue with the adjective “perfect”. The preceding conclusion uses perfect path space, allowing finite dead ends in the decidable presentation. If “perfect tree” instead requires every node to have two incompatible extensions in the tree, the requested combination is impossible. Such a nonempty tree has no terminal nodes. Starting at the empty string, test the two immediate successors and choose the first that belongs to the tree; one always exists. This constructs a total computable function whose successive prefixes remain in the tree. Thus computable pruned binary trees have computable paths. Our $T$ necessarily has dead ends; its subtree consisting only of prefixes of infinite paths is perfect in the pruned sense but is not decidable. The construction therefore supplies the intended perfect closed path space and also resolves the stronger, inconsistent interpretation.

A function in intension is a finite description of a computation, such as a program or a formal construction expression. A function in extension is the resulting input-output map, including its domain if it is partial. Different descriptions may have the same extension: the programs that return $x$ directly and that compute $x+0$ describe the same function. Finite descriptions have Gödel numbers; equality of the resulting partial computable functions is a separate semantic question.

The primitive recursive functions are the smallest class of numerical functions containing the zero functions, the successor function and all projection functions, and closed under function composition in recursion theory and primitive recursion. More explicitly, from $g:{\mathbb{N}}^k\to \mathbb{N}$ and $h:{\mathbb{N}}^{k+2}\to \mathbb{N}$ the latter operation formsFor function composition in recursion theory, an $m$-ary $g$ and $k$-ary $h_1,\dots ,h_m$ give $g(h_1(\mathbf{x}),\dots ,h_m(\mathbf{x}))$. Zero functions of all allowed arities can be included, with nullary zero included if arity $0$ is part of the coding convention. Every resulting function is total: the initial functions are total, function composition in recursion theory preserves totality, and mathematical induction on $n$ verifies totality of primitive recursion. Applying structural induction for primitive recursive functions then covers all construction expressions.

Use a fixed effective Gödel numbering of finite tagged construction trees with decidable decoding. A node is tagged as zero, successor, projection, composition, or recursion. The primitive recursive syntax and arity checking algorithm first checks that the input decodes as a finite tree, then works upwards from its leaves. A projection tag $(k,j)$ is legal exactly when $1\le j\le k$, with output arity $k$. A composition node declares its output arity $k$ and is legal when its outer child has arity $m$, there are exactly $m$ inner children, and each has arity $k$; its arity is $k$. The declared arity also handles the case $m=0$. A recursion node is legal when its base child has arity $k$ and its step child has arity $k+2$; its arity is $k+1$. Zero and successor tags have their declared arities. Ill-formed nodes are rejected. The process terminates because there are only finitely many nodes. Thus, for each fixed $i$,This is a syntactic assertion about functions in intension. It does not assert that arbitrary machine indices computing primitive recursive functions form a decidable set. That extensional property is nontrivial, hence undecidable by Rice theorem. For an explicit reduction, given a program $e$ construct a program that, on every input, waits for ${\phi }_e(e)$ to halt and then returns $0$. Its extension is a primitive recursive function if $e\in K$, and otherwise is nowhere defined and so is not a primitive recursive function. A decision procedure for this latter semantic set would decide the diagonal halting set.

Enumerate the decidable syntax set $D_1$ in increasing code order as $p_0,p_1,\dots$. There are infinitely many such descriptions; iterating successor after a unary zero expression already supplies infinitely many. Let $F_p$ be the extension of a valid construction and defineTo compute $U$, find $p_n$ by the syntax test and interpret its finite construction tree. Evaluate function composition in recursion theory by evaluating the children, and evaluate primitive recursion by the prescribed finite loop of length equal to its final input. Termination follows from the totality argument above, so $U$ and $d$ are total computable functions.

If $d$ were a unary primitive recursive function, some construction $p_j$ would have extension $d$. Then the diagonal argument giveswhich is impossible. The displayed $d$ is total and computable but not primitive recursive. Repetitions of extensions in the enumeration cause no problem: every possible extension is represented, which is all the diagonal argument needs. The same argument shows that the two-variable interpreter $U$ cannot itself be primitive recursive.

Let $(W_e{)}_{e\in \mathbb{N}}$ enumerate all computably enumerable sets, with finite uniformly computable approximations $W_{e,s}$ increasing to $W_e$. For example, take $W_e=\mathrm{dom}{\phi }_e$ andWe construct a simple set by meeting the requirements $R_e$: if $W_e$ is infinite, then $W_e\cap X\ne \varnothing$. Begin with no enumerated elements and all requirements unmarked. At stage $s$, process $e=0,1,\dots ,s$ in this order. For an unmarked $R_e$, if there is an $x\in W_{e,s}$ with $x>2e$, enumerate the least such $x$ into $X$ and mark $R_e$ permanently. All membership tests at a stage are finite, and marking requires no test for eventual infinitude. The sparse-witness construction of a simple set therefore gives a computably enumerable set $X$; it is semidecidable by simulating this enumeration and halting when the input appears.

Each requirement enumerates at most one element. If an element in $[0,2n]$ is enumerated by $R_e$, then $2e<x\le 2n$, so $e<n$. At most $n$ elements of that interval can therefore enter $X$, even if some requirements choose the same element. ConsequentlyThe complement of a set $\mathbb{N}\setminus X$ is infinite.

If $W_e$ is infinite, it contains some $x>2e$, and that element eventually belongs to $W_{e,s}$ at a stage with $s\ge e$. If $R_e$ has already acted, it already placed an element of $W_e$ in $X$. Otherwise it acts by this stage and does so now. Thus every infinite semidecidable set meets $X$. Equivalently, its infinite complement of a set is an immune set. The constructed $X$ is semidecidable, coinfinite, and meets every infinite semidecidable set.

As a useful check on the construction, $X$ cannot be a computable set. If it were, its infinite complement of a set would also be a computably enumerable set disjoint from $X$, contradicting the property just proved. The argument requires neither deciding which $W_e$ are infinite nor protecting a prechosen infinite list of omitted numbers; the numerical witness bound provides all the required room.

For subsets $A,B\subseteq \mathbb{N}$, a many-one reduction $A{\le }_{m}B$ is a total computable function $f:\mathbb{N}\to \mathbb{N}$ such thatA Turing reduction $A{\le }_{T}B$ is an oracle machine that, using membership queries to $B$, halts on every input and computes the indicator function of $A$. It may make several adaptive queries, and need not preserve the yes/no answer to a single query. A many-one reduction yields a Turing reduction by computing $f(x)$ and querying $B$ once. Two sets have the same Turing degree when each is Turing reducible to the other. Write $0^{\prime }$ for the degree of the diagonal halting set $K$.

We prove the Kleene–Post incomparability theorem by an oracle-assisted finite-extension construction. Fix an effective list $({\Phi }_e)$ of all Turing functionals. We shall build increasing finite binary strings ${\alpha }_s,{\beta }_s$ whose unions are the indicator functions of $A,B$. A finite oracle computation ${\Phi }_e^{\tau }(n)\downarrow =v$ means that the computation halts with output $v$ and every oracle query is strictly below $|\tau |$. Its answers are supplied by $\tau$. By the finite oracle use property, every infinite oracle extending $\tau$ preserves this computation.

Here is the decision available from $K$. Given $e,n$ and a finite string $\beta$, considerThis predicate is semidecidable: enumerate all finite extensions $\tau$ of $\beta$ and dovetail their finite oracle simulations, stopping at the first halting binary output. There is a computably produced program which, on its own index as well as on every other input, performs this search and halts exactly if it succeeds. Membership of its code in $K$ therefore decides $E$. In a yes case, running the search finds an actual witness $(\tau ,v)$. The decision oracle is essential in a no case; merely waiting would not produce a terminating construction.

Start with empty strings. At stage $s$ first ensureChoose $n=|{\alpha }_s|$, which is not yet assigned in $A$. Ask whether $E(s,n,{\beta }_s)$ holds. If yes, find a witness $(\tau ,v)$, extend the current $B$ string to $\tau$, and append the bit $1-v$ to the current $A$ string. If no, leave the current $B$ string unchanged and append $0$ to the current $A$ string. The yes case permanently forces disagreement at $n$, since later strings extend both commitments. In the no case no final oracle extending the current $B$ string can give a binary output at $n$: any such convergent computation would use finitely many bits and hence supply a forbidden finite witness. Thus it cannot be the indicator function of $A$ either, regardless of whether it diverges or returns a nonbinary value.

Next, using the strings just obtained, ensureby the same procedure with the roles reversed. Choose $m$ equal to the current length of the $B$ string, ask the analogous extension question about the current $A$ string, and, if it has witness output $v$, extend $A$ to that witness and append $1-v$ to $B$. Otherwise append $0$ to $B$. Finally pad both strings with zeros if necessary so that each length is at least $s+1$, and call the resulting strings ${\alpha }_{s+1},{\beta }_{s+1}$. Every operation is computable using the membership oracle $K$ and terminates. Earlier disagreements remain protected because no already fixed bit is ever changed.

Set $1_A={\bigcup }_s{\alpha }_s$ and $1_B={\bigcup }_s{\beta }_s$. The length condition makes these total binary functions. To compute either bit $n$ with oracle $K$, run the construction through stage $n$, when both strings have length at least $n+1$, and read that bit. Consequently $A,B{\le }_{T}K$. Every Turing functional has been defeated in both directions, soNeither set is computable, since a computable set is Turing reducible to every oracle. Neither can have degree $0^{\prime }$: if $K{\le }_{T}A$, then $B{\le }_{T}K{\le }_{T}A$, contrary to incomparability; the other case is symmetric. ThereforeThis proves the requested theorem. The argument does not claim $A$ or $B$ is computably enumerable; it constructs sets computable in $K$. Obtaining incomparable computably enumerable degrees is the stronger Friedberg–Muchnik theorem, which is not needed for the printed request.