Question

Let REPEAT TM = { | M is a TM, and for all s ∈ L(M), s = uv where u = v }. Show that REPEATTM is undecidable. Do not use Rice’s Theorem.

Answer 1

Answer:

Step-by-step explanation:

Let REPEAT $_{TM$= { | M is a TM, and for all s ∈ L(M), s = uv where u = v }

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