Chapter “Computability”, exercise 3

Text

Consider an algorithm that takes as input a 0-1 sequence of exactly five symbols, and returns a 1 if the sequence contains at least three 1s in any order, and returns a 0 otherwise. Implement the algorithm with a Turing machine, where the cell correspondent to the starting position of the head is where the final result must be stored. Also, the five cells following the starting position of the head are initialised with the 0-1 sequence of five symbols used as input of the algorithm.

Answer

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

Current state	Tape symbol	Write symbol	Move head	Next state
start	0	1	right	pn
pn	0	0	right	p0
pn	1	0	right	p1
p0	0	0	right	p00
p0	1	0	right	p01
p1	0	0	right	p01
p1	1	0	right	p11
p00	0	0	left	fail
p00	1	0	right	p001
p01	0	0	right	p001
p01	1	0	right	p011
p11	0	0	right	p011
p11	1	0	left	stop
p001	0	0	left	fail
p001	1	0	right	p0011
p011	0	0	right	p0011
p011	1	0	left	stop
p0011	0	0	left	fail
p0011	1	0	left	stop
fail	0	0	left	fail
fail	1	0	left	stop

The starting state is start while the ending state is stop.

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

input: '010001'
blank: '0'
start state: start
table:
  start:
    0: { write: 1, R: pn }
  pn:
    0: { write: 0, R: p0 }
    1: { write: 0, R: p1 }
  p0:
    0: { write: 0, R: p00 }
    1: { write: 0, R: p01 }
  p1:
    0: { write: 0, R: p01 }
    1: { write: 0, R: p11 }
  p00:
    0: { write: 0, L: fail }
    1: { write: 0, R: p001 }
  p01:
    0: { write: 0, R: p001 }
    1: { write: 0, R: p011 }
  p11:
    0: { write: 0, R: p011 }
    1: { write: 0, L: stop }
  p001:
    0: { write: 0, L: fail }
    1: { write: 0, R: p0011 }
  p011:
    0: { write: 0, R: p0011 }
    1: { write: 0, L: stop }
  p0011:
    0: { write: 0, L: fail }
    1: { write: 0, L: stop }
  fail:
    0: { write: 0, L: fail }
    1: { write: 0, L: stop }
  stop:

Additional material

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