# CS 273: More Reduction Examples

## 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:

• 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 Mw as follows:
• Input is a string x.
• Erase the input x and replace it with the constant string w.
• Simulate M on w.
• Feed <Mw> to R. If R accepts, accept. If R rejects, reject.

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:

• 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 Mw as follows:
• Input is a string x.
• Ignore the value of x.
• Simulate M on w.
• Feed <Mw> to R. If R accepts, accept. If R rejects, reject.

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:

• 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 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:

• 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 Mw 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 <Mw>. If R accepts, accept. If R rejects, reject.

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:

• 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 Mw 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 <Mw> to R. If R accepts, accept. If R rejects, reject.

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.