Chapter “Computability”, exercise 1

Text

Write the table of instructions of a Turing machine with four states – A (initial state), B, C, and D (final state) – such that, once reached the final state, only the cells immediately on the left and on the right of the initial position of the head of the machine will have the value 1 specified. The final state must not have any instruction specified in the table.

Answer

The table of instructions of the Turing machine is as follows:

Current state	Tape symbol	Write symbol	Move head	Next state
A	0	1	right	B
A	1	0	left	C
B	0	1	left	A
C	0	1	left	D

The starting state is A while the ending state is D.

The same machine, specified in the format used in the Turing machine visualisation website, is available as follows.

blank: '0'
start state: A
table:
  A:
    0: { write: 1, R: B }
    1: { write: 0, L: C }
  B:
    0: { write: 1, L: A }
  C:
    0: { write: 1, L: D }
  D:

Additional material

The YAML file (that can be run at the Turing machine visualisation website) is available online.