Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 12I (Automata & Formal Languages)

The relation $A{\le }_{m}B$ means that there is a total computable function $g:\mathbb{W}\to \mathbb{W}$ such thatfor every word $w$. Such a $g$ is a many-one reduction.

A set $A$ is $\mathcal{C}$-complete under many-one reductions whenThe first condition is membership in the class; the second is $\mathcal{C}$-hardness. This is a many-one complete set.

A set $A\subseteq \mathbb{W}$ is a Sigma-1 set when it is the domain of a partial computable function: there is a partial computable $f$ such thatEquivalently, $w\in A$ iff $\exists tR(w,t)$ for some computable predicate $R$; one may take $R(w,t)$ to say that the truncated computation function observes a halt within $t$ steps.

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.

First, $\mathbf{K}\in {\Sigma }_1$: the partial procedure on input $w$ simulates $f_{w,1}(w)$ and halts exactly when that computation halts.

For hardness, let $A\in {\Sigma }_1$. Choose a partial computable function $g$ withFor each fixed $w$, define a unary program $P_w$ as follows: on any input $x$, simulate $g(w)$; if that simulation halts, halt and output $x$, and otherwise run forever. The S-m-n theorem gives a total computable function $h$ that maps $w$ to a code for $P_w$. Its accepted language isIn particular,Thus $h$ is a many-one reduction $A{\le }_m\mathbf{K}$. Since $A$ was arbitrary, $\mathbf{K}$ is ${\Sigma }_1$-hard; together with membership this proves the many-one completeness of the halting problem.

Membership is immediate from the supplied characterization of ${\Pi }_2$. Define the partial computable functionThenso $\mathbf{Tot}\in {\Pi }_2$.

Now let $P\in {\Pi }_2$. There is a partial computable $f$ such thatFor each $w$, define a unary partial functionOperationally, its program simulates $f(w,x)$ and returns $x$ if that computation halts. By the S-m-n theorem, a total computable map $h$ produces an index $h(w)$ for $g_w$. ThereforeThus every Pi-2 set many-one reduces to $\mathbf{Tot}$. Combined with membership, this proves that the totality problem is ${\Pi }_2$-complete.