Question

Let REPEAT TM = . Show that REPEATTM is undecidable. Do not use Rice’s Theorem.

Answer 1

Explanation:

Let REPEAT
`_{TM`=

To prove that REPEAT
`_{TM` is undecidable.

Let REPEAT
`_{TM` M is a TM that does not accept M

Then, we form a TM u for L by applying TM v as a subroutine.

Assume Repeat is decidable

Let M be the algorithm that TM which decides the REPEATU = on input "s" simulate the M

Accept; if M ever enters the accept state

Reject; if M ever enters the reject state

U does not decide the REPEAT as it may loop over s

so REPEAT is undecidable