Anzeigen des Gesamtinhalts (oder Logo links anklicken) oder des Impressums.

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Nächste Überarbeitung		Vorhergehende Überarbeitung
hasenjaeger:utm84 [2021-06-29 13:19] – angelegt rainerhasenjaeger:utm84 [2021-06-29 19:44] (aktuell) – rainer
Zeile 1: Zeile 1:
 ====== UTM-84 ====== ====== UTM-84 ======
 +
 +Zur Übersicht: [[hasenjaeger:inhalt|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: 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:
  
-{{:hasenjaeger:hasenjaeger1984_statetable.png?600|UTM84}}+        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: 
 +{{:hasenjaeger:hasenjaeger_exponential-diophantische-beschreibung-einer-kleinen-utm.pdf|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:gh_regutm84_2013-06-24.pdf|Hasenjaeger's Register Machine with Wang Instructions}}. Dies ist nach meiner Taxonometrie [[hasenjaeger:tm-index|TM-Index]] mit 15.5 bzw. 20 Punkten durchaus eine sehr kleine Maschine; die Werte für die  
 +[[hasenjaeger:mini-wang|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.  
 + 
 + 
  
-Es handelt sich um eine Maschine mit zwei Zuständen, einem Programmband (mit vier Symbolen in zwei Bit) und drei nicht beschreibbaren Turing-Bändern, die als Zähler dienen.  

Anmelden