Skip to content

Instantly share code, notes, and snippets.

@bgrenet

bgrenet/UTM_Hopcroft_Ullman1969.yaml

Last active January 21, 2026 14:38
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save bgrenet/a3482dd81642cb972b5a6e7e7c4546a1 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save bgrenet/a3482dd81642cb972b5a6e7e7c4546a1 to your computer and use it in GitHub Desktop.
Download ZIP
Universal Turing Machines
Raw
UTM_Hopcroft_Ullman1969.yaml
name: UTM_Hopcroft_Ullman_1969
source code: |-
# Source: J. E. Hopcroft and J. D. Ullman, Formal languages and their relation to automata. Addison-Wesley, 1969.
# - Figure 7.4 pp 105 - 107
# - Input is Figure 7.2 p 103
#
# Alphabet:
# - non-marked symbols ("upper track" is B): 0, 1, c, L, R, ' ' (blank)
# - marked symbols ("upper track" is m): O (for m0), I (for m1), C (for mc), ' ' (for m' ')
#
# Fixed transitions:
# - From DB: missing direction when reading 0
# - From TL0,TL1,TR0,TR1: missing transition when reading C
input: 'ccC0c0c11R0cc111L1c111L1c11R1cc1111R0c1111R0c111L1cc0c0c0cccI111'
blank: ' '
start state: A
table:
A:
[0, 1, c, L, R]: R
C: {R: B}
B:
[0, 1, c, L, R]: R
O: {L: C0}
I: {L: C1}
'_': {L: CB}
C0:
[0, 1, c, L, R]: L
C: {write: c, R: D0}
C1:
[0, 1, c, L, R]: L
C: {write: c, R: D1}
CB:
[0, 1, c, L, R]: L
C: {write: c, R: DB}
DB:
1: {write: I, L: E}
0: {L: V} # fixed: direction L was missing
D0:
[0, 1, L, R]: R
c: {R: DB}
D1:
[0, 1, L, R]: R
c: {R: D0}
E:
[0, 1, L, R]: L
c: {L: F}
F:
[0, 1, L, R]: {L: E}
c: {L: G}
G:
[0, 1, L, R]: {L: E}
c: {R: H}
H:
c: {R: I}
I:
c: {write: C, R: J}
J:
[0, 1, c, L, R]: R
I: {write: 1, R: KL}
KL:
1: {write: I, L: ML}
L: {R: TL}
R: {R: TR}
ML:
[0, 1, c, L, R]: L
C: {write: c, R: NL}
TL:
0: {R: TL0}
1: {R: TL1}
TR:
0: {R: TR0}
1: {R: TR1}
NL:
[0, 1, L, R]: R
c: {R: PL}
I: {R: NR}
PL:
[0, 1, L, R]: {R: NL}
c: {write: C, R: SL}
I: {R: NR}
NR:
[0, 1, L, R]: R
c: {R: PR}
SL:
[0, 1, c, L, R]: R
I: {write: 1, R: KL}
KR:
1: {write: I, R: MR}
L: {R: TL}
R: {R: TR}
MR:
[0, 1, c, L, R]: R
C: {write: 1, R: NR}
PR:
[0, 1, L, R]: {R: NR}
c: {write: C, L: SR}
SR:
[0, 1, c, L, R]: L
I: {write: 1, R: KR}
TL0:
[0, 1, c, L, R, C]: R # fixed: C was missing
[O, I, '_']: {write: 0, L: U}
TL1:
[0, 1, c, L, R, C]: R # fixed: C was missing
[O, I, '_']: {write: 1, L: U}
TR0:
[0, 1, c, L, R, C]: R # fixed: C was missing
[O, I, '_']: {write: 0, R: U}
TR1:
[0, 1, c, L, R, C]: R # fixed: C was missing
[O, I, '_']: {write: 1, R: U}
U:
0: {write: O, L: C0}
1: {write: I, L: C1}
' ': {write: '_', L: CB}
V:
[0,1,L,R]: L
c: {L: W}
W:
[0,1,L,R]: {L: V}
c: {R: X1}
X1:
c: {R: X2}
X2:
0: {R: X3}
X3:
c: {R: X4}
X4:
0: {R: X5}
X5:
c: {R: X6}
X6:
0: {R: Y}
Y:
positions:
A: {x: 37.98, y: 113.63}
B: {x: 139.76, y: 114.14}
C0: {x: 256.48, y: 118.57}
C1: {x: 255.72, y: 64.53}
CB: {x: 255.42, y: 176.62}
DB: {x: 349.32, y: 179.62}
D0: {x: 349.42, y: 120.37}
D1: {x: 346.39, y: 65.63}
E: {x: 453.95, y: 174.29}
F: {x: 457.75, y: 79.73}
G: {x: 530.27, y: 81.99}
H: {x: 596.92, y: 83.45}
I: {x: 668.44, y: 81.64}
J: {x: 739.73, y: 80.83}
KL: {x: 537.39, y: 195.72}
ML: {x: 567.92, y: 276.76}
TL: {x: 497.3, y: 408.1}
TR: {x: 492.67, y: 288.44}
NL: {x: 644.47, y: 281.74}
PL: {x: 744.33, y: 285.06}
NR: {x: 732.72, y: 398.71}
SL: {x: 707.83, y: 163.84}
KR: {x: 573.14, y: 428.95}
MR: {x: 626.04, y: 396.22}
PR: {x: 738.52, y: 476.68}
SR: {x: 625, y: 478.34}
TL0: {x: 404, y: 453.24}
TL1: {x: 406.89, y: 375.04}
TR0: {x: 399.81, y: 314.23}
TR1: {x: 395.95, y: 249.78}
U: {x: 325.47, y: 353.05}
V: {x: 212.56, y: 301.97}
W: {x: 127.19, y: 301.09}
X1: {x: 128.67, y: 214.11}
X2: {x: 34.1, y: 215.26}
X3: {x: 38.11, y: 309.64}
X4: {x: 38.25, y: 399.74}
X5: {x: 41.57, y: 480}
X6: {x: 131.16, y: 480}
Y: {x: 228.21, y: 480}
Raw
UTM_modified_from_Hopcroft_Ullman.yaml
name: Universal
source code: |-
# Source: modified from the UTM of Hopcroft & Ullman (1969)
# Input: Binary increment with input 1011
# End of computation: final state marked with +
#
# Encoding of the transition table:
# - States numbered 1 (initial state) to N
# - Transition δ(q,X) = (q',Y,m) for X, Y ∈ {0, 1, B}, m ∈ {R,L}: 1...1mY with q' ones
# - Transitions for state q: δ(q,B) δ(q,0) δ(q,1) (rules concatenated)
# - Transition table: "rules state 1 | rules state 2 | .... | rules state N"
#
# Input: "+ transition table | input" with first input symbol marked (0→o, 1→i, B→b)
input: '+11L_1R01R1|111L1111L111L0|000|i011'
blank: ' '
start state: 'init'
table:
'init':
['0', '1', '_', '|', '+', 'L', 'R']: R
['o']: {L: 'read0'}
['i']: {L: 'read1'}
['b']: {L: 'readB'}
'read0':
['0', '1', '_', '|', 'L', 'R']: L
['+']: {write: '|', R: 'tr0'}
'read1':
['0', '1', '_', '|', 'L', 'R']: L
['+']: {write: '|', R: 'tr1'}
'readB':
['0', '1', '_', '|', 'L', 'R']: L
['+']: {write: '|', R: 'trB'}
'trB':
['1']: {write: 'i', L: 'back'}
['0']: {L: 'end'}
'tr0':
['0']: {R: 'trB'}
['1']: R
['R', 'L']: {R: 'tr0B'}
'tr1':
['0']: {R: 'tr0'}
['1']: R
['R', 'L']: {R: 'tr10'}
'back':
['0', '1', '_', '|', '+', 'L', 'R']: L
[' ']: {R: 'stInit'}
'end':
['0', '1', '_', 'R', 'L']: L
['|']: {write: '+', R}
'tr0B':
['0', '1', '_']: {R: 'trB'}
'tr10':
['0', '1', '_']: {R: 'tr0'}
'stInit':
['|']: {write: '+', R: 'st'}
'st':
['0', '1', '|', '_', 'L', 'R']: R
['i']: {write: '1', R: 'stiG'}
'stiG':
['1']: {write: 'i', L: 'st|G'}
['L']: {R: 'L'}
['R']: {R: 'R'}
'st|G':
['0', '1', '_', '|', 'L', 'R']: L
['+']: {write: '|', R: 'st+G'}
'L':
['0']: {R: 'L0'}
['1']: {R: 'L1'}
['_']: {R: 'LB'}
'R':
['0']: {R: 'R0'}
['1']: {R: 'R1'}
['_']: {R: 'RB'}
'st+G':
['0', '1', '_', 'L', 'R']: R
['|']: {write: '+', R: 'st1G'}
['i']: {R: 'st+D'}
'st1G':
['0', '1', '_', 'L', 'R', '|']: R
['i']: {write: '1', R: 'stiG'}
'st+D':
['0', '1', '_', 'L', 'R']: R
['|']: {write: '+', L: 'st1D'}
'stiD':
['1']: {write: 'i', R: 'st|D'}
['L']: {R: 'L'}
['R']: {R: 'R'}
'st|D':
['0', '1', '_', '|', 'L', 'R']: R
['+']: {write: '|', R: 'st+D'}
'st1D':
['0', '1', '_', 'L', 'R', '|']: L
['i']: {write: '1', R: 'stiD'}
'L0':
['0', '1', '_', '|', '+', 'L', 'R']: R
['o', 'i', 'b']: {write: '0', L: 'mark'}
'L1':
['0', '1', '_', '|', '+', 'L', 'R']: R
['o', 'i', 'b']: {write: '1', L: 'mark'}
'LB':
['0', '1', '_', '|', '+', 'L', 'R']: R
['o', 'i', 'b']: {write: '_', L: 'mark'}
'R0':
['0', '1', '_', '|', '+', 'L', 'R']: R
['o', 'i', 'b']: {write: '0', R: 'mark'}
'R1':
['0', '1', '_', '|', '+', 'L', 'R']: R
['o', 'i', 'b']: {write: '1', R: 'mark'}
'RB':
['0', '1', '_', '|', '+', 'L', 'R']: R
['o', 'i', 'b']: {write: '_', R: 'mark'}
'mark':
['0']: {write: 'o', L: 'read0'}
['1']: {write: 'i', L: 'read1'}
[' ', '_']: {write: 'b', L: 'readB'}
['|']: {R: 'shift'}
'shift':
['0']: {write: 'b', R: 'shift0'}
['1']: {write: 'b', R: 'shift1'}
[' ', '_']: {write: 'b', L: 'readB'}
'shift0':
['0']: R
['1']: {write: '0', R: 'shift1'}
[' ', '_']: {write: '0', L: 'shiftr'}
'shift1':
['0']: {write: '1', R: 'shift0'}
['1']: R
[' ', '_']: {write: '1', L: 'shiftr'}
'shiftr':
['0', '1']: L
['b']: {L: 'readB'}
positions:
init: {x: 49.44, y: 83.98}
read0: {x: 162.67, y: 97.98}
read1: {x: 164.15, y: 41.64}
readB: {x: 163.78, y: 150.31}
trB: {x: 245.81, y: 152.55}
tr0: {x: 246.55, y: 94.66}
tr1: {x: 245.54, y: 41.57}
back: {x: 378.3, y: 151.4}
end: {x: 276.58, y: 251.54}
tr0B: {x: 304.15, y: 127.01}
tr10: {x: 310.85, y: 64.79}
stInit: {x: 391.59, y: 42.52}
st: {x: 492.36, y: 44.38}
stiG: {x: 598.24, y: 295}
st|G: {x: 577.62, y: 197.38}
L: {x: 503.04, y: 357.37}
R: {x: 487.66, y: 449.15}
st+G: {x: 616.55, y: 123.55}
st1G: {x: 635.5, y: 198.34}
st+D: {x: 737.1, y: 120.71}
stiD: {x: 740.27, y: 296.81}
st|D: {x: 706.25, y: 195.41}
st1D: {x: 769.22, y: 194.73}
L0: {x: 365.47, y: 313.07}
L1: {x: 368.12, y: 270.36}
LB: {x: 366.24, y: 356.5}
R0: {x: 368.87, y: 438.62}
R1: {x: 368.85, y: 397.41}
RB: {x: 367.5, y: 480}
mark: {x: 249.48, y: 356.72}
shift: {x: 183.42, y: 469.98}
shift0: {x: 63.14, y: 472.53}
shift1: {x: 123.69, y: 411.43}
shiftr: {x: 66.07, y: 362.93}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment