UoL CS Notes
Menu

Programming Turing Machines

COMP218 Lectures

Consider that we want to make a TM that accepts the following language:

\[L=\{w\#w:w\in\{a,b\}^*\}\]

We can write the following program, that instructs the head:

  1. Until you reach $\#$
    1. Read and remember entry ($x\underline bbaa\#xbbaa$)
      1. Write $x$ ($x\underline xbaa\#xbbaa$)
      2. Move right past $\#$ and past all $x$s ($xxbaa\#x\underline bbaa$)
    2. If this entry is different, reject
      otherwise:
      1. Write $x$ ($xxbaa\#x\underline baa$)
      2. Move left past $\#$ and to right of first $x$ ($xx\underline baa\#xxbaa$)
  2. If you see only $x$s followed by $\square$, accept.

From this we can make the following state machine:

stateDiagram
direction LR
[*] --> q0
q0 --> qa1:a/xR
q0 --> q1:#/#R
q0 --> qb1:b/xR
qa1 --> qa1:a/aR\nb/bR
qa1 --> qa2:#/#R
q1 --> q1:x/xR
q1 --> qacc:□/□R
qacc --> [*]
qb1 --> qb1:a/aR\nb/bR
qb1 --> qb2:#/#R
qa2 --> qa2:x/xR
qa2 --> q2:a/xL
qb2 --> qb2:x/xR
qb2 --> q2:b/xL
q2 --> q2:a/aL\nb/bL\nx/xL
q2 --> q3:#/#L
q3 --> q3:a/aL\nb/bL
q3 --> q0:x/xR

All other transitions go to $q_\text{rej}$.

We will generally just use the high level description for simplicity.

Examples

There are additional examples of Turing machines that complete:

  • Multiplication
  • Comparing Strings
  • Reading Graphs as Strings $\langle G\rangle$ (Serialisation)

in the lecture video.