Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 120 (Computability and Logic)

Use the synchronous group multiplier automata belonging to the automatic structure for a group. Write $u\otimes v$ for the padded convolution of words: the shorter tape is completed with a symbol $\#$ outside the alphabet, and reading stops when both words over an alphabet have ended. Our convention isLet $N\ge 1$ be at least the number of states of each of these finite-state automata, including $M_{\epsilon }$.

Choose a shortest representative $v\in L$ of $g$. In the first orientation, $M_x$ accepts $w\otimes v$; in the other orientation it accepts $v\otimes w$. If $|v|>|w|+N$, the accepting run has more than $N$ transitions after the tape containing $w$ has ended. Two states in that suffix coincide. Delete the intervening nonempty loop. Every deleted column contains $\#$ on the fixed tape and a genuine letter on the tape containing $v$, so the resulting input remains a valid padded convolution of words. The group multiplier automaton still accepts, giving a shorter representative of the same $g$. This contradicts minimality. Thus a representative can always be chosen withThis argument does not require a symmetric alphabet: the second orientation uses the same $M_x$ with its tapes interchanged in the input, rather than a presumed $M_{x^{-1}}$.

Apply the same pumping of a group multiplier automaton to the accepted pair containing the given representative $u$. Since $|u|>|w|+N$, there is a nonempty loop entirely after the tape containing $w$ has ended. Write $u=pqr$, with $q\ne \epsilon$ the letters read during this loop. Repeating the loop any number of times leaves the other tape equal to $w$, and the group multiplier automaton accepts the resulting padded convolution of words. ConsequentlyThese words over an alphabet have distinct lengths because $|q|>0$. Hence there are infinitely many representatives of $g$ in $L$. No uniqueness of representatives was assumed in either part.

Fix the first tape of the group multiplier automaton $M_x$ to be $u=a_1\cdots a_m$. Construct its possible runs by dynamic programming, one column at a time. A record consists of a state and a flag indicating whether the output tape has ended. At column $i\le m$, the first symbol is $a_i$ and the second symbol may be any letter of the alphabet, or $\#$; after the second tape first uses $\#$ it must continue to use $\#$. At later columns the first symbol is $\#$, and an additional column must have a genuine letter on the second tape. Never add a $(\#,\#)$ column.

Keep one predecessor record and its output symbol for each reachable state-and-flag pair in each layer. Two runs reaching the same record have exactly the same possible future completions, so this merging loses no accepting output. The merged dead state of a finite automaton can be discarded. At each layer $i\ge m$, test whether a reached state is accepting; the initial layer is included when $m=0$. Upon success, follow predecessor records backwards and omit padding symbols to recover $v$.

The automatic structure for a group supplies a representative in $L$ of $\overline{u}x$, so an accepted padded convolution of words exists and this search terminates. The output is the required representative:The search uses only the finite transition table; it does not presuppose a solution to the word problem for a group.

Part (a)(i), applied to $w=u$ and $g=\overline{u}x$, guarantees an accepted output of length at most $m+N$. Its padded convolution of words has at most $m+N$ columns. Thus the dynamic programming search in part (b) reaches an accepting layer by this bound.

Each layer has at most twice the fixed number of states of $M_x$, and each record has at most $|A|+1$ outgoing choices. These are constants for the fixed automatic structure for a group. Storing a pointer and a symbol takes constant time; copying whole partial output strings at every step would unnecessarily spoil this bound. Reconstruction also takes at most $m+N$ steps. Therefore automatic multiplication has linear time and bounded length increase:For nonempty inputs this is the requested $O(|u|)$ time complexity. The additive $1$ merely includes the constant work on the empty word.

The regular language $L$ is nonempty because it represents every element of the group. Find any accepted word $t=a_1\cdots a_k$ using breadth-first search in its finite-state automaton. If $t$ is the empty word, it already represents the identity.

Otherwise begin with $t\in L$ and repeatedly apply the linear-time multiplication in an automatic structure to the lettersThese letters belong to $A$ by symmetry of the alphabet. All intermediate words lie in $L$, and the final word $\gamma$ representsHence an identity representative can be constructed effectively:This is a finite preliminary computation depending only on the fixed automatic structure for a group; it uses no test for whether an arbitrary word represents the identity.

Write the input word over an alphabet as $w=a_1\cdots a_n$. Starting with $z_0=\gamma$, obtain $z_i$ from $z_{i-1}$ by linear-time multiplication in an automatic structure with $a_i$. Mathematical induction givesThe time complexity of step $i$ is at most a constant times $|\gamma |+(i-1)N+1$. Summing the costs givesThe automatic structure for a group, $N$ and $\gamma$ are fixed, so the required representative isFor the empty word, return $\gamma$ in constant time.

Construct $z$ as above, and run the equality group multiplier automaton $M_{\epsilon }$ on $z\otimes \gamma$. Both inputs belong to $L$, soThe final finite-state automaton run takes $O(\max (|z|,|\gamma |)+1)=O(n+1)$ time. The word problem for a group is therefore decidable in quadratic time:The empty word is accepted immediately. Comparing $z$ and $\gamma$ as literal strings would be incorrect, since an automatic structure for a group need not give unique representatives.

For a finite position $s\in A^{<\omega }$, let $[s]$ be the cylinder set of infinite plays extending $s$. Because the factors have the discrete topology, these cylinder sets form a basis for the product topology. PutMembership in $D$ means that I has already secured the outcome, regardless of future moves. Since $G$ is an open set, a play belongs to $G$ exactly when one of its prefixes belongs to $D$.

Build the winning-position attractor in an infinite game by transfinite recursion. Start with $W_0=D$, use unions at limit ordinals, and setThis sequence is increasing: the defining operation is order-preserving, and $W_0\subseteq W_1$. It stabilizes at some ordinal. Indeed, if it strictly increased at every successor stage below the successor cardinal number of $|A^{<\omega }|$, choosing one newly added position per stage would inject that larger cardinal into $A^{<\omega }$. Denote the stable set by $W$. This constructs the needed fixed point directly, without an appeal to an unstated fixed-point theorem.

Every position in $W$ has a least entry ordinal, its rank. Rank zero means membership in $D$. A positive rank is a successor $\alpha +1$: at an I-position some extension belongs to $W_{\alpha }$, while at a II-position every extension does. If the empty word belongs to $W$, I always chooses an extension of smaller rank until $D$ is reached. II's choices also decrease rank before that happens. There is no infinite strictly decreasing sequence of ordinals, so some finite prefix lies in $D$. This is a winning strategy in an infinite game for I.

If the empty word is outside $W$, the fixed point equation says that every extension of an I-position outside $W$ is still outside $W$, and that a II-position outside $W$ has at least one extension outside $W$. II chooses such an extension. Every resulting prefix avoids $D$, hence the whole play avoids $G$ by openness. This is a winning strategy in an infinite game for II.

The choices can be made simultaneously by fixing a well-order of $A$, as allowed by the usual axiom of choice. The argument does not assume that $A$ is countable. Every such open game is determined:

Rice theorem: every nontrivial extensional property of programs computing partial computable functions has an undecidable index set. More precisely, take an acceptable effective enumeration $({\phi }_e)$ of the unary partial computable functions. If $\mathcal{P}$ contains some but not all of these functions, then“Extensional” means that equality of partial functions, including their domains, preserves membership; no syntactic restriction on program codes is being considered.

We use two standard facts, stated explicitly. The diagonal halting set $K=\{e:{\phi }_e(e)\downarrow \}$ is undecidable. For the associated acceptable enumerations ${\phi }_e^{(r)}$ of $r$-ary partial computable functions, with ${\phi }_e={\phi }_e^{(1)}$, the S-m-n theorem says that for every $m,n\ge 1$ there is a total computable function $s_n^m$ such thatwhere $\simeq$ means equality of defined values and equality of undefinedness. Thus fixed parameters in a program can be compiled into its index effectively.

Let $\perp$ be the nowhere-defined partial computable function. Choose a partial computable function $h$ whose membership in $\mathcal{P}$ is opposite to that of $\perp$; this is possible by nontriviality. For each $e$, construct the programThis is a uniform partial computation. Take an index $d$ for the binary partial computable function $(e,y)\mapsto {\psi }_e(y)$. The S-m-n theorem gives the total computable function $q(e)=s_1^1(d,e)$ with ${\phi }_{q(e)}={\psi }_e$. Crucially,Even when $h(y)$ itself is undefined, the equality of partial functions remains correct. If $\perp \notin \mathcal{P}$, this gives a many-one reduction of $K$ to $I_{\mathcal{P}}$; if $\perp \in \mathcal{P}$, it gives a many-one reduction of $K$ to the complement of $I_{\mathcal{P}}$. A decision procedure for $I_{\mathcal{P}}$ would therefore decide $K$ in either case, a contradiction.

The equivalent language formulation says that every nontrivial property of computably enumerable languages depending only on the recognized language has an undecidable index set. Apply the function formulation to the property of a partial computable function that its domain has the specified language property: every computably enumerable language occurs as such a domain.

For (1)(a), a primitive recursive function is obtained by a finite construction from the zero function, successor function and projection functions, using function composition in recursion theory and primitive recursion. The recursion rule, with parameters $\mathbf{x}$, isHere $g,h$ have already been constructed. All these functions are total on nonnegative integers: the initial functions are total, composition preserves totality, and ordinary mathematical induction proves totality of each recursion.

For (1)(b), use a shifted hyperoperation sequence, beginning with addition. Defineand, for each fixed $r\ge 0$, defineThe first three members are therefore addition, multiplication and exponentiation:The exponentiation convention includes $a^0=1$, hence $0^0=1$. The next member iterates exponentiation, with $H_3(a,0)=1$; there is no need for an exceptional domain restriction at $a=0$.

For (1)(c), $H_0$ is a primitive recursive function by its displayed recursion. If $H_r$ is a primitive recursive function, thenare primitive recursive functions, using constants, projection functions and function composition in recursion theory. Primitive recursion applied to $g_r,h_r$ gives $H_{r+1}$. Mathematical induction on the fixed rank $r$ proves every member of the sequence is primitive recursive. This does not assert that the joint three-variable evaluator $(r,a,b)\mapsto H_r(a,b)$ is a primitive recursive function.

For (2), as written, the answer is no: the empty set $X=\varnothing$ is semidecidable, whereas a total computable function from $\mathbb{N}$ to $\mathbb{N}$ always has a nonempty range. This is the only obstruction. To prove the stronger useful statement, suppose $X$ is a nonempty computably enumerable set and choose $x_0\in X$. Fix a Turing machine which halts exactly on the inputs in $X$. Its bounded halting predicateis primitive recursive: encode configurations arithmetically, iterate its total single-step operation $t$ times by primitive recursion, and check the halt state. A halted configuration is kept fixed. This is a bounded simulation, not unbounded waiting.

Fix a primitive recursive pairing function $⟨x,t⟩$ with primitive recursive inverse coordinate functions. For example, the Cantor pairing function has inverses obtained by bounded minimization. DefineThe two coordinate functions, the bounded predicate, and the finite case distinction are primitive recursive functions, so $f$ is a primitive recursive function. Its values always lie in $X$. Conversely, if $x\in X$, its computation halts within some finite $t$, and $f(⟨x,t⟩)=x$. ThusThe range need not be a computable set; deciding whether a value occurs anywhere in this total enumeration is an unbounded search.

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 which, with membership oracle $B$, halts on every input and computes the indicator function ${\chi }_A$. It may make finitely many adaptive queries on each input. A many-one reduction gives a Turing reduction by a single query, but Turing reducibility allows more general procedures.

The Friedberg–Muchnik theorem states that there are computably enumerable sets $A,B$ with incomparable Turing degrees:Here is a finite-injury priority construction proving it. Effectively enumerate all Turing functionals $({\Phi }_e)$. Arrange the requirements in the priority orderEquality would require the Turing functional to be total and give the correct bit at every input; one disagreement or one undefined input defeats it.

Start with $A_0=B_0=\varnothing$ and enumerate elements without ever removing them. A strategy has a private witness, a flag recording whether it has acted, and a restraint on its oracle. Every new witness is larger than every previously assigned witness and every current higher-priority restraint. Retired witnesses are never reused. The only possible enumeration of a witness is by its owner, so an unacted witness remains outside its target set.

The strategy for $R_e$ chooses a witness $x$ and waits for a stage at which the bounded simulation givesOn seeing this, put $x$ into $B$, declare the strategy acted, and impose restraint $u$ on $A$, where $u$ is the oracle use: one more than the largest queried number, or zero if there were no queries. Initialize every lower-priority strategy, discarding its current witness, acted flag and restraint. An acted strategy does nothing further until initialized. The strategy for $S_e$ is identical with $A,B$ interchanged. Waiting specifically for zero is enough: if the eventual output is nonzero while the witness stays out, it already disagrees with the target indicator function.

For a completely effective schedule, at stage $s$ visit the first $s+1$ strategies in priority order. Assign an unassigned witness when visited. Simulate each unacted strategy's computation for at most $s$ steps with the current finite oracle. If some strategy can act, perform the first such action and end the stage; otherwise end after all visits. All steps are finite and algorithmic, so the limiting $A,B$ are computably enumerable sets.

Every lower-priority enumeration respects higher-priority restraints. When its witness was chosen it lay above these restraints. Any subsequent action of a higher-priority strategy would have initialized it, so its current witness remains safe to enumerate. The initialization of all lower strategies also removes their obsolete restraints before they can obstruct a legitimate higher-priority action.

We verify finite injury by mathematical induction on priority. The first strategy is never injured and acts at most once. If all predecessors of a strategy act finitely often, there is a last stage when a higher-priority action initializes it. It is subsequently visited, chooses its permanent witness, and acts at most once. Thus it too acts finitely often and all its lower-priority strategies suffer only finitely many injuries. The scheduling cannot starve a fixed strategy: after the finitely many higher-priority actions, all sufficiently large stages visit it.

Consider the final uninjured $R_e$ with witness $x$. If it acts, then $x\in B$ permanently, and every later lower-priority enumeration into $A$ respects its restraint. No later higher-priority action occurs. The preserved computation is thereforeIf it never acts, $x\notin B$. Were ${\Phi }_e^A={\chi }_B$, the final computation on $x$ would halt with zero and have finite oracle use. The finitely many oracle bits it queries eventually stabilize, and a sufficiently late bounded stage simulation would see exactly this zero computation. The strategy would then act, a contradiction. Hence $R_e$ holds in this case too. The same reasoning proves every $S_e$.

All possible Turing reductions in both directions are excluded. This proves the Friedberg–Muchnik theorem; in particular both constructed Turing degrees are noncomputable, since a computable set is Turing reducible to every oracle.

Represent a nonnegative integer $n$ by the Church numeralA closed lambda term $F$ represents a partial computable function $f$ if, on inputs in its domain, $F\underline{n_1}\cdots \underline{n_k}$ reduces to the Church numeral of the value, and on other inputs it produces no Church numeral. We use untyped lambda calculus and normal-order beta reduction.

First every primitive recursive function has such a representation on all inputs. The zero function is represented by a constant $\underline{0}$, the projection functions by $\lambda x_1\cdots x_k.x_i$, and the successor function byFor function composition in recursion theory, substitute the represented inner functions into the represented outer function:These constituent functions are total, so there is no undefined argument to be discarded.

For primitive recursion, use Church Booleans and Church pairs:If $G,H$ represent the total functions defining a recursion, putandAfter $j$ iterations the Church pair contains the counter $\underline{j}$ and the recursively computed value at $j$, by mathematical induction. Thus this lambda definition of primitive recursion by pair iteration represents the recursion. A structural induction for primitive recursive functions now represents every primitive recursive function.

To pass to arbitrary partial computable functions, use the Kleene normal form theorem in the following form: for every $f:{\mathbb{N}}^k\rightharpoonup \mathbb{N}$, there are total primitive recursive functions $C,U$ such thatwith $f$ undefined precisely when no such $t$ exists. The predicate checks codes of valid finite halting histories for the chosen program; $U$ extracts their common output. This expresses unbounded minimization of a total predicate, so no earlier undefined test can interfere with the search.

Let $\hat{C},\hat{U}$ be the represented total functions. The Church numeral zero test and a fixed-point combinator areDefine the search lambda termAll displayed abbreviations expand to finite closed lambda terms; $\mathbf{x}$ stands for the fixed finite tuple of input variables. Because $YH{\equiv }_{\beta }H(YH)$, normal-order beta reduction tests $t=0,1,2,\dots$. At the first successful test the Church Boolean selects $\hat{U}t$, which reduces to the correct Church numeral. The unused recursive branch is discarded.

If no test succeeds, every finite search step returns to another head search, never exposing a numeral. The term has no head normal form and hence cannot be beta equivalent to a Church numeral. This last point is why the output operation occurs inside the successful branch: simply applying a possibly argument-discarding outer function to a divergent search would not justify undefinedness. Therefore every computable function is representable, including partial computable functions with their correct undefined inputs: