The Imitation Game
Turing machines are normally represented as diagrams which help to simplify what is going on. Circles or nodes represent internal states of the machine, with the leftmost node being the first internal state. Arrows from one node, or internal state, to another represent a change in the internal state in the machine. Along each arrow there is a symbol, indicating which symbol to apply the action to, followed by a colon and then another symbol representing an overt action to execute. For example if you were to see \( 1:R \) along an arrow going from internal state \( q_m \) to \( q_n \), the machine would move one block right along the tape if it was scanning a 1 in internal state \( m \). After this action is taken the machine would enter internal state \( n \).
A physical Turing machine may look something like this: Physical Turing Machine
Consider the following initial tape \( \ldots BB1001111BB \ldots \) where \( B \) is the symbol for blank. The combination of 0's and 1's can be interpreted as a binary number. Therefore the initial number on the tape, in decimal form, is 79. The scanner of the Turing machine begins on the rightmost symbol of the initial binary number.
Consider the following Turing machine acting on the above tape: Turing Machine
What will be the number on the tape once the machine has halted, in decimal form?