While learning about Turing machines, I've stumbled onto a problem that I'm not sure how to solve. I've put a lot of work into trying to find the solution, any help would be appreciated.
The problem lists sets of quintuples in this format:
(state, read: write, direction, new_state)
Where state is the current state, read is the value to be read, write is the value to overwrite it with, direction is the direction, and new_state is the new state to jump into.
(0, 0: 0, R, 0)
(0, 1: 0, R, 1)
(1, 0: 0, R, 2)
(1, 1: 0, R, 3)
(2, 0: 0, R, 4)
(2, 1: 1, R, 0)
(3, 0: 1, R, 1)
(3, 1: 1, R, 2)
(4, 0: 1, R, 3)
(4, 1: 1, R, 4)
The instructions say to start at state 0, and to begin with the leftmost, non-blank character. None of the quintuples I was given halt the machine, it just keeps going to the right.
The input tapes given look like this:
...[][][]110011[][][]...
...[][][]1001010[][][]...
...[][][]0011001[][][]...
I went through the steps and evaluated all of the input tapes, like so. But, even after receiving the output, I'm still having trouble figuring out what this machine is trying to evaluate.
I was given a hint to check the values of the input tapes in decimal form before and after going through the states. I did that for all of the examples.
Given an input of (110011, 51), the machine outputs (001010, 10)
Given an input of (111110, 62), the machine outputs (001100, 12)
Given an input of (1001010, 74), the machine outputs (0001110, 14)
Given an input of (0011001, 25), the machine outputs (0000101, 5)
I can see there's some sort of pattern in the quintuples themselves, the 0th, and 1st states all write out 0's, and the 3rd and 4th states all write out 1's, where the 2nd state maintains the same values. I can see the symmetry there, but I'm not sure what it's doing.
Any help would be appreciated, thank you.
This is a $\mod 5$ machine: with the input treated as a binary number, the state that the machine ends up in equals the input $\mod 5$. The output written by this machine is completely irrelevant and a distraction, really. Combined with the fact that this machine only moves to the right, we are therefore really just dealing with a Finite State Automaton:
Simplified to this, we can now also better understand how it works. The key claim is that the machine is in state $i$ after reading the first $n$ bits from the input if and only if the binary number represented by those first $n$ bits $\equiv i \mod 5$. So, for example, suppose the machine is in state $3$. That means that the binary number it has seen so far $\equiv 3 \mod 5$. Now, when there is another bit to follow, then that means that we have to double the number, and add the bit, to get the binary number as represented by the first $n+1$ bits. So, if the next bit is a $0$, then we simply double, and hence we get $2 \times 3 \equiv 1 \mod 5$. So, if we are in state $3$ and see a $0$, we should go to state $1$. However, if we see a $1$, then we get $2 \times 3 +1 \equiv 2 \mod 5$, and so if we are in state $3$ and see a $1$, we should go to state $2$. You can easily verify that the machine does all the other transitions correctly as well.