A TM with reset is the same as a basic single-tape TM, except at any point...

 

Transcribed Image Text:

A TM with reset is the same as a basic single-tape TM, except at any point it its computation, it may "reset" resulting in both of the following: 1) The entire contents of the tape are erased and replaced with the machine's original input, and 2) The head is returned to the left end of the tape. (Note that resetting does not cause the TM to return to its start state.) (a) Give a simulation argument, using an implementation-level description, to show that TMs with reset recognize the class of Turing-recognizable languages. Hint: You may want to simulate using a two-tape TM. (12 points) (b) Consider the language RESETS = {(M, w) | M is a TM with reset that resets at least once when run on input w}. Show that RESETS is undecidable. (12 points) A TM with reset is the same as a basic single-tape TM, except at any point it its computation, it may "reset" resulting in both of the following: 1) The entire contents of the tape are erased and replaced with the machine's original input, and 2) The head is returned to the left end of the tape. (Note that resetting does not cause the TM to return to its start state.) (a) Give a simulation argument, using an implementation-level description, to show that TMs with reset recognize the class of Turing-recognizable languages. Hint: You may want to simulate using a two-tape TM. (12 points) (b) Consider the language RESETS = {(M, w) | M is a TM with reset that resets at least once when run on input w}. Show that RESETS is undecidable. (12 points)