 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/models-of-computation/3/d/ii/solution

The problem is undecidable. Reduce the halting problem to it. Given a Turing machine

M

and input word

w

T

over

{a, b, c}

with the following behavior on input

x

If $x \neq = ε$ , reject.
If $x = ε$ , simulate $M$ on the fixed word $w$ . If that simulation ever halts, whether accepting or rejecting, accept $x$ ; otherwise continue the simulation forever.

This is an effective construction:

M, w

are fixed data stored in the description of

T

. Its recognized formal language is

L (T) = {{ε} \emptyset M halts on w, M does not halt on w .

Therefore

T

accepts exactly one input word if and only if

M

halts on

w

. A supposed decision procedure for the singleton-language problem for Turing machines, applied to the constructed

T

, would decide the halting problem. The standard undecidability of the halting problem excludes that possibility.

The singleton-language problem for Turing machines is undecidable .

 New to topics? Read the docs here!