Question

Undecidability .20 marks

Let L1 = {M | M is a TM that halts on the empty tape leaving exactly two words on its tape in the form Bw1Bw2B} where B represents Blank like w1 w2 . (a) The problem of deciding whether an arbitrary Turing machine will accept an arbitrary input is undecidable. Prove formally using problem reduction, that given an arbitrary Turing machine M, the problem of deciding if M ∈ L1 is undecidable.

(b) Is L1 recursive, recursively enumerable, non-recursively enumerable, uncomputable? Justify your answer.

Answer 1

(a)

We will prove that L1 is undecidable by showing that L1 is Turing reducible from L where

L = {<M,w> | if TM M accepts w}

Suppose that L1 is decidable and hence there exist Turing machine T which on input M decides whether M ∈ L1 or not.

Let us understand how to create Turing machine for L .

Given input instance <M,w> of L, construct Turing machine M1 which on input x performs as follows:-

1. If x is non-blank then clear entire input from the tape, reject the input and halt.

2. If x is blank then perform below steps

.....2.1 copy string w onto the input tape

.....2.2 move the tape header at the beginning of the string w.

....2.3 TM M1 will now simulate as M on input w.

....2.4 If M1 reach at any state which is accepting state in M then write Bw1Bw2B on the input tape and halt otherwise clear the input from tape and halt.

Now if <M,w> ∈ L then this means M will accept w and hence TM M1 on blank input will write Bw1Bw2B into the tape and if <M,w> L then M1 will not leave any symbol on the tape.

Hence if TM T exist to decide L1 then we will be able to decide L but since L is undecidable, hence decidable TM T cannot exist for L1, hence L1 is undecidable.

(b) L1 is not recursive because recursive problem are always decidable.

However L1 is recursive enumerable because if TM M on blank input halts with leaving Bw1Bw2B onto the tape then this can be verified by some Turing machine T. Hence L1 is recursive enumerable but not recursive.

Please comment for any clarification.