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); die Zählbänder werden durch c zyklisch gewechselt.
Ein Entwurf aus seinem Nachlass ist etwas ausführlicher und vielleicht besser zu lesen: Exponentiell-diophantische Beschreibung einer kleinen Turing-Maschine .
Primär unter dem Gesichtspunkt einer Rematerialisation (d.h. einem physischen Demonstrationsmodell) habe ich mir Notizen gemacht, in der diese UTM in Kapitel 3 ausführlich betrachtet wird: Hasenjaeger's Register Machine with Wang Instructions. Dies ist nach meiner Taxonometrie TM-Index mit 15.5 bzw. 20 Punkten durchaus eine sehr kleine Maschine; die Werte für die Mini-Wang sind 24 bzw. 44. Mit der dort schon verwendeten Technik der variablen Befehlslänge ergibt sich eine Variante, die mit einem TM-Index von 9.8 bzw. 12 noch kleiner ist und den Vorteil hat, dass das Programmband rein binär ist.
