Question

Prove that there is no algorithm that determines whether an arbitrary Turing machine halts when run with the input string 101.

can someone help me with this problem? thanks

Answer 1

Q) Prove that there is no algorithm that determines whether an arbitrary Turing machine halts when run with the input string 101.

Method 1) By contradiction

• Assume such a Turing Machine does exist.

   Call it A:

M Halts on 101 R(M)101A M doesn't halt on 101

• Create a Turing Machine N which produces the encoding of a Turing

Machine M’.

• M’ has all of M’s transitions, but some additional transitions to erase

any input so that M’ runs M on an empty tape:

• Note that M halts on a blank tape exactly when M’ halts on 101.

This will decide the blank tape problem which is undecidable. Seeè

M Halts on 101M halts on a blank tape R(M) -N R(M )101 M 'doesn't halt on 101M doesn't halt on a blank tape

Method 2)

• Again assume, machine A exists:

M Halts on 101 R(M)101A M doesn't halt on 101

• To reduce HP to this, consider a TM N that :

               1) converts R(M) w to R(M’)101 where M’ has all of M’s transitions except that

               2) there are extra transitions to replace 101 with w,

3) return the tape head to the beginning and to the start state of M, and 4) then run M see è

M Halts on 101 M halts on w R(M)w-N R(M )101 M 'doesn't halt on 101M doesn't halt on w