This page contains some additional reduction examples, supplementing those in Sipser.

Let L_{UIUC} = { < M > : L(M) contains the string "UIUC"}.
L_{UIUC} is undecidable.

Proof by reduction from A_{TM}. Suppose that L_{UIUC}
were decidable and let R be a Turing machine deciding it.
We use R to construct a Turing machine deciding A_{TM}. S
is constructed as follows:

- Input is <M,w>, where M is the code for a Turing Machine and w is a string.
- Construct code for a new Turing machine M
_{w}as follows:- Input is a string x.
- Erase the input x and replace it with the constant string w.
- Simulate M on w.

- Feed <M
_{w}> to R. If R accepts, accept. If R rejects, reject.

If M accepts w,
the language of M_{w} contains all strings and, thus, the
string "UIUC". If M doesn't accept w,
the language of M_{w} is the empty set and, thus, doesn't
contain the string "UIUC". So R(<M_{w}>) accepts
exactly when M accepts w. Thus, S decides A_{TM}

But we know that A_{TM} is undecidable. So S can't exist. Therefore
we have a contradiction. So L_{UIUC} must have been undecidable.

Let HALTEMPTY_{TM}
= { < M > : M halts on blank input}.
Let HALTEMPTY_{TM} is undecidable.

Proof by reduction from A_{TM}. Suppose that HALTEMPTY_{TM}
were decidable and let R be a Turing machine deciding it.
We use R to construct a Turing machine deciding A_{TM}. S
is constructed as follows:

- Input is <M,w>, where M is the code for a Turing Machine and w is a string.
- Construct code for a new Turing machine M
_{w}as follows:- Input is a string x.
- Ignore the value of x.
- Simulate M on w.

- Feed <M
_{w}> to R. If R accepts, accept. If R rejects, reject.

If M accepts w,
the language of M_{w} contains all strings and, thus, in
particular the
empty string. If M doesn't accept w,
the language of M_{w} is the empty set and, thus, doesn't
contain the empty string. So R(<M_{w}>) accepts
exactly when M accepts w. Thus, S decides A_{TM}

But we know that A_{TM} is undecidable. So S can't exist. Therefore
we have a contradiction. So HALTEMPTY_{TM}
must have been undecidable.

Let L_{111} = {<M> : M prints three one's in a row
on blank input}. This language is undecidable.

Suppose that L_{111} were decidable.
Let R be a Turing machine deciding L_{111}.
We will now construct a Turing machine S that decides A_{TM}.

S is constructed as follows:

- Input is <M,w>, where M is the code for a Turing Machine and w is a string.
- Construct the code for a new Turing machine M', which is just
like M except that
- every use of the character 1 is replaced by a new character 1' which M does not use.
- when M would accept, M' first prints 111 and then accepts

- Similarly, create a string w' in which every character 1 has been replaced by 1'.
- Create a second new Turing machine M'
_{w}which simulates M' on the hardcoded string w'. - Run R on <M'
_{w}>. If R accepts, accept. If R rejects, reject.

If M accepts w, then M'_{w} will print 111 on any input
(and thus on a blank input). If M does not accept w, then M'_{w}
is guaranteed never to print 111 accidently. So R will
accept <M'_{w}> exactly when M accepts w. Therefore,
S decides A_{TM}.

But we know that A_{TM} is undecidable. So S can't exist. Therefore
we have a contradiction. So L_{111} must have been undecidable.

Let L_{x} = {<M> : M writes an x at some point, when
started on blank input}. This language is undecidable.

Suppose that L_{x} were decidable.
Let R be a Turing machine deciding L_{x}.
We will now construct a Turing machine S that decides A_{TM}.

S is constructed as follows:

- Input is <M,w>, where M is the code for a Turing Machine and w is a string.
- Construct the code for a new Turing machine M
_{w}as follows- On input y (which will be ignored).
- Simulate M on w, but substituting X for x, everywhere that x occurs in w or the code for M.
- If M rejects w, reject.
- If M accepts w, print x on the tape and then accept.

- Run R on <M
_{w}>. If R accepts, accept. If R rejects, reject.

If M accepts w, then M_{w} will print x on any input
(and thus on a blank input). If M rejects w or loops on w,
then M_{w}
is guaranteed never to print x accidently. So R will
accept <M_{w}> exactly when M accepts w. Therefore,
S decides A_{TM}.

But we know that A_{TM} is undecidable. So S can't exist. Therefore
we have a contradiction. So L_{x} must have been undecidable.

Let L_{3} = { < M > : |L(M)| = 3}.
That is L_{3} contains all Turing machines whose languages contain
exactly three strings. L_{3} is undecidable.

Proof by reduction from A_{TM}. Suppose that L_{3}
were decidable and let R be a Turing machine deciding it.
We use R to construct a Turing machine deciding A_{TM}. S
is constructed as follows:

- Input is <M,w>, where M is the code for a Turing Machine and w is a string.
- Construct code for a new Turing machine M
_{w}as follows:- Input is a string x.
- Simulate M on w.
- If M rejects w, reject.
- Else accept x exactly when x is one of the three strings "UIUC", "Iowa", or "Michigan".

- Feed <M
_{w}> to R. If R accepts, accept. If R rejects, reject.

If M accepts w,
the language of M_{w} contains exactly three strings.
If M doesn't accept w,
the language of M_{w} is the empty set.
So R(<M_{w}>) accepts
exactly when M accepts w. Thus, S decides A_{TM}

But we know that A_{TM} is undecidable. So S can't exist. Therefore
we have a contradiction. So L_{3} must have been undecidable.