Es gibt ein GOTO-Programm, dass die Werte zweier Variablen addieren kann.
Daraus kann man ein GOTO-Programm schreiben, dass die Werte zweier Variablen multiplizieren kann.
Daraus kann man ein GOTO-Programm schreiben, dass prüft ob eine Zahl gerade ist und eines das prüft ob eine Zahl eine Primzahl ist.
Damit kann man den Inhalt eines in beide Richtungen unendlichen Bandes in einer Variable kodieren:
\(x = \prod_{i=1}^\infty p_i^{x_i}\)
wobei \(p_i\) die \(i\)-te Primzahl ist. Die ungeraden \(i\) codieren die Zellen des Bandes rechts von der ersten Zelle, die Geraden \(i\) codieren die Zellen des Bandes links von der ersten Zelle.
Bis auf das Band sind alle weiteren Komponenten einer Turingmaschine endlich.