0
$\begingroup$

enter image description here

I'm having trouble understanding state tables for turing machines where the state table shown in the above image is supposed to show the change from the top turing machine to the bottom such that an extra 1 was added at index 5. I don't see how when S0 reads 1 (at start, index 1) and shifts the head right it then reads 0 and then writes 1, as when it shifts right shouldn't the head be at index 2 and read 1? And if the head was at index 2 then the finish at S2 would be at index 2 as well (since it shifts left and then right again)?

$\endgroup$
2
$\begingroup$

They're the same Turing Machine, to be specific - the top diagram is a representation of the tape before the TM has run, and the bottom diagram is after.

There's no key regarding how to read the state transitions but I'm assuming >> means shift right one cell, << means shift left one cell and 1 means stay put.

You are right that the first move would be to index 2, using the first rule. But this rule applies three more times still, so the head ends up at index 5, where it encounters 0 and enters state S1 via the second rule - at the same time writing 1 at index 5.

The head then shifts back all the way to index 0 (one cell at a time) using the third rule, at which point the fourth rule is used (read 0, switch to S2, shift right). So it moves right to index 1 and then stops, as S2 is the final state.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.