Design an NTM (normalised Turing machine) that never terminates, so that regardless of the input string, it always gives an infinite configuration sequence. (You only need two states!)

Thanks in advance!

- Thread starter leo0liver
- Start date

Design an NTM (normalised Turing machine) that never terminates, so that regardless of the input string, it always gives an infinite configuration sequence. (You only need two states!)

Thanks in advance!

The problem I was having with this question is I was not sure what the set of inputs would be. For example if they had stated that it was a binary input I would have moved the tape head to the right for inputs 1 and 0 and then started an infinite loop causing the tape head to never return to the first position and therefore never terminate. If the input language is not specified wouldnt there be a very large of possibilities of letters that the machine first sees on the tape that would cause it to abort and finish in the starting position? Or is there a way to move left on the tape no matter what the input?

I could also be overthinking it and what they really are asking for is a machine that never terminates for an input of 0 1 or blank.