The Imitation Game

Computer Science Level 4

Turing machines are idealized computers that take an input and halt on an output once it has run out of instructions. Alan Turing, hence the name, used these machines in order to revolutionize the notion of computability. A Turing machine consists of a infinite tape with blocks containing one symbol each, and a scanner. The machine itself is in a certain internal state $q_i$ at any given time for $i \geq 1$ . When a symbol is being scanned, the machine executes an overt and a covert action. The overt action will either halt the machine, move the scanner one block left or right, or write a new symbol in place of the old symbol. A covert action will change the internal state of the machine.

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?

The answer is 80.

1 solution

Nicola Mignoni
May 5, 2018

Red digits indicate the scanner position.

Initial state: $\displaystyle \hspace{40pt} ...BB100111\textcolor{#D61F06}{1}BB...$
Change from $1$ to $0$ $\displaystyle \hspace{10pt} ...BB100111\textcolor{#D61F06}{0}BB...$
Move left $\displaystyle \hspace{47pt} ...BB10011\textcolor{#D61F06}{1}0BB...$
Change from $1$ to $0$ $\displaystyle \hspace{10pt} ...BB10011\textcolor{#D61F06}{0}0BB...$
Move left $\displaystyle \hspace{47pt} ...BB1001\textcolor{#D61F06}{1}00BB...$
Change from $1$ to $0$ $\displaystyle \hspace{10pt} ...BB1001\textcolor{#D61F06}{0}00BB...$
Move left $\displaystyle \hspace{47pt} ...BB100\textcolor{#D61F06}{1}000BB...$
Change from $1$ to $0$ $\displaystyle \hspace{10pt} ...BB100\textcolor{#D61F06}{0}000BB...$
Move left $\displaystyle \hspace{47pt} ...BB10\textcolor{#D61F06}{0}0000BB...$
Change from $0$ to $1$ $\displaystyle \hspace{10pt} ...BB10\textcolor{#D61F06}{1}0000BB...$
Move right $\displaystyle \hspace{43pt} ...BB101\textcolor{#D61F06}{0}000BB...$
Move right $\displaystyle \hspace{43pt} ...BB1010\textcolor{#D61F06}{0}00BB...$
Move right $\displaystyle \hspace{43pt} ...BB10100\textcolor{#D61F06}{0}0BB...$
Move right $\displaystyle \hspace{43pt} ...BB101000\textcolor{#D61F06}{0}BB...$
Move right $\displaystyle \hspace{43pt} ...BB1010000\textcolor{#D61F06}{B}B...$
Move left, end process $\displaystyle ...BB101000\textcolor{#D61F06}{0}BB...$

So, the result in $1010000$ , in decimal $\boxed{80}$

The Imitation Game

The answer is 80.

1 solution

0 pending reports