Question

2. (25 points) Consider the language Li = {(M)M is a Turing machine that halts when started on the empty tape) Is Li є o? Justify your answer. ,

Answer 1

Yes, because the language L₁ is undecidable and every undecidable language is in $\Sigma_0$.

Lets prove how L₁ is undecidable.

Consider famous halting problem which on input <M,w> accept it if M halts on w and reject otherwise. Halting problem is undecidable and let us understand how we can reducing input <M,w> to input of language L₁.

Consider input <M,w> of halting problem, construct TM M₁ which on input $\epsilon$ :-

1. Write string w on blank tape.

2. Go to start position of string w on tape.

3. Simulate behaviour of TM M on string w.

Now note that M₁ will halt on $\epsilon$ i.e. <M₁> will be in L₁ if and only if M will halt on w. Hence we are able to decide where M halts on w on not, if language L₁ is decidable. But since halting problem is undecidable, so L₁ cannot be decidable. Hence $L_1 \in \Sigma_0$.

Please comment for any clarification.