CS 273: More Reduction Examples

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

The language LUIUC

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

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

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

But we know that ATM is undecidable. So S can't exist. Therefore we have a contradiction. So LUIUC must have been undecidable.

The language HALTEMPTYTM

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

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

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

But we know that ATM is undecidable. So S can't exist. Therefore we have a contradiction. So HALTEMPTYTM must have been undecidable.

The language L111

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

Suppose that L111 were decidable. Let R be a Turing machine deciding L111. We will now construct a Turing machine S that decides ATM.

S is constructed as follows:

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 ATM.

But we know that ATM is undecidable. So S can't exist. Therefore we have a contradiction. So L111 must have been undecidable.

The language Lx

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

Suppose that Lx were decidable. Let R be a Turing machine deciding Lx. We will now construct a Turing machine S that decides ATM.

S is constructed as follows:

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

But we know that ATM is undecidable. So S can't exist. Therefore we have a contradiction. So Lx must have been undecidable.

The language L3

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

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

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

But we know that ATM is undecidable. So S can't exist. Therefore we have a contradiction. So L3 must have been undecidable.