Not sure about Turing machine

62 Views Asked by At

Not quite sure, if I understand Turing machine correctly. So I tried building one, which should give back the predecessor of a number in binary code.

e.g. 111 -Turing-> 110

picture of turing m.

If it ends in an accepting state, the header has to be at the beginning/end or can it be also in the middle of the "word"?

1

There are 1 best solutions below

1
On

Many variations of the rules for Turing machines are possible. If you have a Turing machine that might halt in the middle, and you want to ensure that the head is at the left end of the word when you halt, it's easy to achieve that: just put in a "pre-halt" state where you move to the left until you encounter a blank, then halt. Similarly if you want the head to end up at the right end of the word.