UTM-84

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

Es handelt sich um eine Maschine mit zwei Zuständen, einem Programmband (mit den vier Symbolen c, d, e und f für change, decrement, enlarge und forward) und drei nicht beschreibbaren Turing-Bändern, die als Zähler dienen und durch c zyklisch gewechselt werden.