Dies ist eine alte Version des Dokuments!
UTM-84
Zur Übersicht: Hasenjaegers Materialisationen
In einem Artikel von 1984 (Gisbert Hasenjaeger: Universal Turing machines (UTM) and Jones-Matijasevich-masking. In: Logic and Machines: Decision Problems and Complexity, Proceedings of the Symposium „Rekursive Kombinatorik“ May 23-28, Münster 1983) verwendet Hasenjaeger eine sehr kleine universelle Turing-Maschine mit nur zwei Zuständen, einem Programm- und drei Zählbändern:
S PRJ rj s Remark Group 1: sequential instructions 0 c.0 #. . cycle tape d10 -. . decrement register e.0 +. . increment register f.0 .. 1 start jumping Group 2: executing a jump 0 c.1 .- . decrement J for c d.1 .- . decrement J for d f.1 .. . skip f Group 3: do not jump as R is zero 1 c0. .. 0 terminated by c d0. .. 0 terminated by d f0. .. . ignore f Group 4: collect jump distance 1 c1. .. 0 found c d1. .. 0 found d f1. .+ . count number of 'f's
Das Programmband hat vier Symbole c
, d
, e
und f
(für change, decrement, enlarge und forward) und drei nicht beschreibbare Turing-Bändern, die als Zähler dienen und durch c
zyklisch gewechselt werden.
Ein Entwurf aus seinem Nachlass ist etwas ausführlicher und vielleicht besser zu lesen: Exponentiell-diophantische Beschreibung einer kleinen Turing-Maschine .