Past exam of the computer science course of the University of Oxford / 2015 / Computational complexity / 1

Exactly the regular languages. A read-only-from-left Turing acceptor has only its current control state as usable memory: it never changes a tape symbol, and its head never returns to an earlier cell. This is the behaviour of a deterministic finite automaton while it reads the input.

To make the correspondence precise, retain the control states and the transitions on the input alphabet. Replace accepting and rejecting halts by absorbing states, so that halting before the end of a word over an alphabet has the same effect on every continuation. For each remaining state $q$, follow the transitions on blank symbols and mark $q$ accepting in the deterministic finite automaton exactly when this blank-only continuation eventually accepts. This marking is a finite calculation: either a halting state is reached or a state repeats, after which the blank-only run loops. The resulting deterministic finite automaton accepts exactly the same formal language as the read-only-from-left Turing acceptor. If the latter is a decider, the blank-only run from every reachable end-of-input state halts.

Conversely, simulate any deterministic finite automaton by a read-only-from-left Turing acceptor, using its state transitions while reading the input. At the first blank symbol, halt and accept or reject according to the current deterministic finite automaton state. This machine halts on every input and decides the required regular language.

Rice's theorem, in its formal language version, says: every nontrivial property of the computably enumerable language accepted by a Turing machine has an undecidable set of machine descriptions. Here nontrivial means that some computably enumerable language has the property and some does not. The property must be an extensional property of programs: any two Turing machines accepting the same formal language must agree about it. It need not be a property of all formal languages, including those no Turing machine accepts.

Let $\mathcal{P}$ be such a property and writeWe prove the theorem by a many-one reduction from the halting problem. First suppose the empty language is not in $\mathcal{P}$. Nontriviality provides a fixed Turing machine $B$ with $\mathcal{L}(B)\in \mathcal{P}$. Given a Turing machine $M$ and a word over an alphabet $w$, effectively construct a Turing machine $N_{M,w}$ which, on input $x$, first simulates $M$ on $w$. If that simulation ever halts, it simulates $B$ on $x$ and accepts precisely when $B$ accepts. If the first simulation never halts, it never accepts $x$.

The Turing machine encoding of $N_{M,w}$ is computable from those of $M,w$: the description merely embeds $M,w$ and the fixed simulator for $B$. Constructing it does not require predicting whether $M$ halts. Its accepted formal language isConsequentlyA decider for $I_{\mathcal{P}}$ would therefore decide the halting problem, a contradiction. Invalid descriptions can be mapped to a fixed description of a machine accepting the empty language, if the many-one reduction is formulated on all strings.

If the empty language does belong to $\mathcal{P}$, apply the preceding argument to the opposite property, within the computably enumerable languages. This opposite property is still nontrivial and excludes the empty language. A hypothetical decider for $I_{\mathcal{P}}$ would decide the opposite property's index set by first rejecting malformed Turing machine encodings and otherwise reversing its answer. The opposite property is undecidable by the first case, giving the required contradiction in this case too.

For example, takeThis is a decidable language: check that the input is a valid Turing machine encoding, count its declared states, and test the count's integer parity. There are Turing machines with even state counts and Turing machines with odd state counts, so the formal language contains some but not all valid descriptions.

There is no contradiction with Rice's theorem because this is a syntactic property of the description. Add one unreachable state to a Turing machine, assigning any permitted transitions to it. The accepted formal language is unchanged, while the integer parity of the state count changes. Thus the property is not an extensional property of programs, which is an essential hypothesis of Rice's theorem.

${\mathcal{L}}_{\ell 3}$ is undecidable. The condition depends only on the accepted formal language. It holds for a Turing machine accepting the empty language, and fails for a Turing machine accepting the singleton $\{aaaa\}$, where $a$ is an alphabet symbol. It is therefore a nontrivial extensional property of programs, and Rice's theorem applies. In particular, the condition does not assert that the machine halts on every input; nonacceptance of long words over an alphabet may result from rejection or from an infinite computation.

${\mathcal{L}}_{1\mathrm{T}}$ is a decidable language: it consists of every valid Turing machine encoding. Every multitape Turing machine has an equivalent single-tape Turing machine. To see this, represent the finitely used portions of its tapes on one tape, separated by delimiters, and mark each simulated head position. To simulate one step, scan these portions to read the marked symbols, retain this fixed number of symbols and the control state in finite control, and scan again to update the symbols and head marks. Extend a represented portion with a blank cell when necessary. Each simulated step takes finitely many real steps.

The single-tape Turing machine accepts exactly when the simulated multitape Turing machine accepts; infinite computations remain infinite. The simulation may increase time complexity, but the question only asks about accepted formal languages. Hence a decider simply checks the syntax of the Turing machine encoding and accepts every valid description. Rice's theorem does not make this property undecidable, because the property is true of every computably enumerable language and is therefore trivial in the theorem's sense.

The clique decision problem is a decidable language: on a valid finite graph and an integer $k$, reject if $k$ exceeds the number of vertices, and otherwise examine all $k$-element subsets of vertices, accepting if one is a clique. Each candidate can be checked by examining all its pairs of distinct vertices. This finite search gives at least one Turing machine deciding the problem, without any claim of polynomial time.

By well-ordering of the natural numbers, there is a least state count $n_0$ among Turing machines deciding the clique decision problem. For every $n\ge n_0$, add $n-n_0$ unreachable states to a machine with $n_0$ states. Its behaviour on every input is unchanged, and it has exactly $n$ states. For $n<n_0$ there is no such machine, by minimality. ThusA Turing machine with the fixed constant $n_0$ in its description decides this threshold language by validating the input and comparing its value with $n_0$. The argument proves the existence of a decider; it does not compute the smallest possible clique decision problem decider. There is no need to search through machine descriptions and attempt to certify their behaviour on every input.

Let $V$ be the decidable language of syntactically valid descriptions $\mathrm{enc}(M)\#\#w$. ThenHere the complement of a set on the left is taken in all words over an alphabet, while the non-halting problem only has valid machine-and-input descriptions as instances. Any malformed description belongs to $\overline{{\mathcal{L}}_{\mathrm{H}}}$ but not to ${\mathcal{L}}_{\mathrm{NH}}$. For example, the empty word has no separating ##, so cannot be a valid instance under the displayed encoding.

Fix valid descriptions $h$ and $\ell$ of, respectively, an immediately halting Turing machine on the empty word and a Turing machine looping forever on the empty word. ThenFor the first many-one reduction, use the total computable functionFor a valid input, nonmembership in ${\mathcal{L}}_{\mathrm{H}}$ is exactly membership in ${\mathcal{L}}_{\mathrm{NH}}$, so retaining it is correct. Every invalid input is a yes-instance of $\overline{{\mathcal{L}}_{\mathrm{H}}}$, and $f$ sends it to the fixed yes-instance $\ell$. Therefore $x\in \overline{{\mathcal{L}}_{\mathrm{H}}}$ if and only if $f(x)\in {\mathcal{L}}_{\mathrm{NH}}$.

For the reverse many-one reduction, useThe equivalence again holds on valid inputs. Invalid inputs are no-instances of ${\mathcal{L}}_{\mathrm{NH}}$, and $h$ is a no-instance of $\overline{{\mathcal{L}}_{\mathrm{H}}}$. Syntax checking terminates, so $g$ is also a total computable function. We have proved