Bug fixes, and add a simulator

3 files changed, 261 insertions, 55 deletions

diff --git a/entries/jj/tm/fib-desc.txt b/entries/jj/tm/fib-desc.txt
index c766da6..289f927 100644
--- a/entries/jj/tm/fib-desc.txt
+++ b/entries/jj/tm/fib-desc.txt
@@ -11,14 +11,15 @@ A Turing machine is a 7-tuple T = (Q,Σ,Γ,δ,qI,qA,qR) where:
 - qR ∈ Q is the reject state
 
 - Q: {
+  ca, cb, cc, cd, ce, cf, cg, ch, ci,
   sa, sb, sc, sd,
   aa, ab, ac,
   aaa, aab, aac, aad, aae, aaf,
-  aba, abb, abc, abd, abe, abf, abg, abh,
+  aba, abb, abc, abd, abe, abf,
   ba, bb, bc,
   baa, bab, bac, bad, bae, baf,
   bba, bbb, bbc, bbd, bbe, bbf,
-  ca, cb, cc, cd, ce, cf, cg, ch, ci
+  za, zb, zc, zd
 }
 - Σ: not relevant as we entirely disregard the input to begin with.
 - Γ: {_, $, X, 0, 1, 0*, 1*} (_ means the blank symbol)
@@ -43,7 +44,7 @@ states c*: clearing the initial tape
 δ(ca, Γ) -> (cb, $, R)
 δ(cb, Γ) -> (cc, 0, R)
 δ(cc, Γ) -> (cd, $, R)
-δ(cd, Γ) -> (ce, 1, R)
+δ(cd, Γ) -> (ce, 1*, R)
 δ(ce, Γ) -> (cf, $, R)
 δ(cf, Γ) -> (cg, 1, R)
 δ(cg, Γ) -> (ch, $, R)
@@ -80,8 +81,8 @@ states a*: add the last digit of both numbers without carrying
 δ(aa, Γ \ $) -> (aa, , L)
 δ(aa, $) -> (ab, , L)
 
+δ(ab, Γ \ {0,1,$}) -> (ab, , L)
 δ(ab, 0) -> (aaa, 0*, L)
-
 δ(ab, 1) -> (aba, 1*, L)
 
 δ(ab, $) -> (ac, , R)
@@ -100,13 +101,15 @@ states aa*
 δ(aac, Γ \ _) -> (aac, , R)
 δ(aac, _) -> (aad, , L)
 δ(aad, Γ \ X) -> (aad, , L)
-δ(aad, X) -> (aba, 0, L)
+δ(aad, X) -> (aa, 0, L)
 
-δ(aab, 1*) -> (aad, 1, R)
+δ(aab, 1*) -> (aae, 1, R)
 δ(aae, Γ \ _) -> (aae, , R)
 δ(aae, _) -> (aaf, , L)
 δ(aaf, Γ \ X) -> (aaf, , L)
-δ(aaf, X) -> (baa, 1, L)
+δ(aaf, X) -> (aa, 1, L)
+
+δ(aab, Γ \ {0*,1*,$}) -> (aab, , L)
 
 states ab*
 - read left until $, then read left until:
@@ -123,35 +126,33 @@ states ab*
 δ(abd, Γ \ X) -> (abd, , L)
 δ(abd, X) -> (aa, 1, L)
 
-δ(abb, $) -> (abe, , R)
+δ(abb, 1*) -> (abe, 1, R)
 δ(abe, Γ \ _) -> (abe, , R)
 δ(abe, _) -> (abf, , L)
 δ(abf, Γ \ X) -> (abf, , L)
-δ(abf, X) -> (aa, 1, L)
+δ(abf, X) -> (ba, 0, L)
 
-δ(abb, 1*) -> (abd, 1, R)
-δ(abg, Γ \ _) -> (abg, , R)
-δ(abg, _) -> (abh, , L)
-δ(abh, Γ \ X) -> (abh, , L)
-δ(abh, X) -> (ba, 0, L)
+δ(abb, $) -> (abc, , R)
+
+δ(abb, Γ \ {0*,1*,$}) -> (abb, , L)
 
 
 states b*: add the last digit of both numbers while carrying a one
 - read left from end of tape, after reading $, until reading:
   - 0: replace with 0*, goto state (baa)
   - 1: replace with 1*, goto state (bba)
-  - $: do not replace, read right until _, goto state (ca)
+  - $: do not replace, read right until _, goto state (za)
 
 δ(ba, Γ \ $) -> (ba, , L)
 δ(ba, $) -> (bb, , L)
 
+δ(bb, Γ \ {0,1,$}) -> (bb, , L)
 δ(bb, 0) -> (baa, 0*, L)
-
 δ(bb, 1) -> (bba, 1*, L)
 
 δ(bb, $) -> (bc, , R)
 δ(bc, Γ \ _) -> (bc, , R)
-δ(bc, _) -> (ca, , L)
+δ(bc, _) -> (za, , L)
 
 states ba*
 - read left until $, then read left until:
@@ -167,12 +168,14 @@ states ba*
 δ(bad, Γ \ X) -> (bad, , L)
 δ(bad, X) -> (aa, 1, L)
 
-δ(bab, 1*) -> (bad, 1, R)
+δ(bab, 1*) -> (bae, 1, R)
 δ(bae, Γ \ _) -> (bae, , R)
 δ(bae, _) -> (baf, , L)
 δ(baf, Γ \ X) -> (baf, , L)
 δ(baf, X) -> (ba, 0, L)
 
+δ(bab, Γ \ {0*,1*,$}) -> (bab, , L)
+
 states bb*
 - read left until $, then read left until:
   - 0*: replace with 0, read right until _, then read left until X and replace with 0, goto state (ba)
@@ -187,27 +190,32 @@ states bb*
 δ(bbd, Γ \ X) -> (bbd, , L)
 δ(bbd, X) -> (ba, 0, L)
 
-δ(bbb, 1*) -> (bbd, 1, R)
+δ(bbb, 1*) -> (bbe, 1, R)
 δ(bbe, Γ \ _) -> (bbe, , R)
 δ(bbe, _) -> (bbf, , L)
 δ(bbf, Γ \ X) -> (bbf, , L)
 δ(bbf, X) -> (ba, 1, L)
 
+δ(bbb, $) -> (bbc, , R)
+
+δ(bbb, Γ \ {0*,1*,$}) -> (bbb, , L)
 
 states c*: scooting over the computed number to make space for a carried digit
 - read left until $, then:
   - read right, noting the current number and writing the previous number
   - then go to state (sa)
 
-δ(ca, Γ \ $) -> (ca, , L)
-δ(ca, $) -> (cb, , L)
+δ(za, Γ \ $) -> (za, , L)
+δ(za, $) -> (zb, , R)
+
+δ(zb, Γ \ {0,1,_}) -> (zb, , R)
+δ(zb, 0) -> (zc, 1, R)
+δ(zb, 1) -> (zb, 1, R)
+δ(zb, _) -> (zd, 1, R)
 
-δ(cb, Γ \ {0,1,_}) -> (cb, , R)
-δ(cb, 0) -> (cc, 1, R)
-δ(cb, 1) -> (cb, 1, R)
-δ(cb, _) -> (sa, 1, R)
+δ(zc, Γ \ {0,1,_}) -> (zc, , R)
+δ(zc, 0) -> (zc, 0, R)
+δ(zc, 1) -> (zb, 0, R)
+δ(zc, _) -> (zd, 0, R)
 
-δ(cc, Γ \ {0,1,_}) -> (cc, , R)
-δ(cc, 0) -> (cc, 0, R)
-δ(cc, 1) -> (cb, 0, R)
-δ(cc, _) -> (sa, 0, R)
+δ(zd, _) -> (sa, $, R)
diff --git a/entries/jj/tm/fib.txt b/entries/jj/tm/fib.txt
index 43f4e55..3dd8bfc 100644
--- a/entries/jj/tm/fib.txt
+++ b/entries/jj/tm/fib.txt
@@ -11,14 +11,15 @@ A Turing machine is a 7-tuple T = (Q,Σ,Γ,δ,qI,qA,qR) where:
 - qR ∈ Q is the reject state
 
 - Q: {
+  ca, cb, cc, cd, ce, cf, cg, ch, ci,
   sa, sb, sc, sd,
   aa, ab, ac,
   aaa, aab, aac, aad, aae, aaf,
-  aba, abb, abc, abd, abe, abf, abg, abh,
+  aba, abb, abc, abd, abe, abf,
   ba, bb, bc,
   baa, bab, bac, bad, bae, baf,
   bba, bbb, bbc, bbd, bbe, bbf,
-  ca, cb, cc, cd, ce, cf, cg, ch, ci
+  za, zb, zc, zd
 }
 - Σ: not relevant as we entirely disregard the input to begin with.
 - Γ: {_, $, X, 0, 1, 0*, 1*} (_ means the blank symbol)
@@ -33,7 +34,7 @@ A Turing machine is a 7-tuple T = (Q,Σ,Γ,δ,qI,qA,qR) where:
 δ(ca, Γ) -> (cb, $, R)
 δ(cb, Γ) -> (cc, 0, R)
 δ(cc, Γ) -> (cd, $, R)
-δ(cd, Γ) -> (ce, 1, R)
+δ(cd, Γ) -> (ce, 1*, R)
 δ(ce, Γ) -> (cf, $, R)
 δ(cf, Γ) -> (cg, 1, R)
 δ(cg, Γ) -> (ch, $, R)
@@ -55,6 +56,7 @@ A Turing machine is a 7-tuple T = (Q,Σ,Γ,δ,qI,qA,qR) where:
 
 δ(aa, Γ \ $) -> (aa, , L)
 δ(aa, $) -> (ab, , L)
+δ(ab, Γ \ {0,1,$}) -> (ab, , L)
 δ(ab, 0) -> (aaa, 0*, L)
 δ(ab, 1) -> (aba, 1*, L)
 δ(ab, $) -> (ac, , R)
@@ -67,12 +69,13 @@ A Turing machine is a 7-tuple T = (Q,Σ,Γ,δ,qI,qA,qR) where:
 δ(aac, Γ \ _) -> (aac, , R)
 δ(aac, _) -> (aad, , L)
 δ(aad, Γ \ X) -> (aad, , L)
-δ(aad, X) -> (aba, 0, L)
-δ(aab, 1*) -> (aad, 1, R)
+δ(aad, X) -> (aa, 0, L)
+δ(aab, 1*) -> (aae, 1, R)
 δ(aae, Γ \ _) -> (aae, , R)
 δ(aae, _) -> (aaf, , L)
 δ(aaf, Γ \ X) -> (aaf, , L)
-δ(aaf, X) -> (baa, 1, L)
+δ(aaf, X) -> (aa, 1, L)
+δ(aab, Γ \ {0*,1*,$}) -> (aab, , L)
 
 δ(aba, Γ \ $) -> (aba, , L)
 δ(aba, $) -> (abb, , L)
@@ -81,24 +84,22 @@ A Turing machine is a 7-tuple T = (Q,Σ,Γ,δ,qI,qA,qR) where:
 δ(abc, _) -> (abd, , L)
 δ(abd, Γ \ X) -> (abd, , L)
 δ(abd, X) -> (aa, 1, L)
-δ(abb, $) -> (abe, , R)
+δ(abb, 1*) -> (abe, 1, R)
 δ(abe, Γ \ _) -> (abe, , R)
 δ(abe, _) -> (abf, , L)
 δ(abf, Γ \ X) -> (abf, , L)
-δ(abf, X) -> (aa, 1, L)
-δ(abb, 1*) -> (abd, 1, R)
-δ(abg, Γ \ _) -> (abg, , R)
-δ(abg, _) -> (abh, , L)
-δ(abh, Γ \ X) -> (abh, , L)
-δ(abh, X) -> (ba, 0, L)
+δ(abf, X) -> (ba, 0, L)
+δ(abb, $) -> (abc, , R)
+δ(abb, Γ \ {0*,1*,$}) -> (abb, , L)
 
 δ(ba, Γ \ $) -> (ba, , L)
 δ(ba, $) -> (bb, , L)
+δ(bb, Γ \ {0,1,$}) -> (bb, , L)
 δ(bb, 0) -> (baa, 0*, L)
 δ(bb, 1) -> (bba, 1*, L)
 δ(bb, $) -> (bc, , R)
 δ(bc, Γ \ _) -> (bc, , R)
-δ(bc, _) -> (ca, , L)
+δ(bc, _) -> (za, , L)
 
 δ(baa, Γ \ $) -> (baa, , L)
 δ(baa, $) -> (bab, , L)
@@ -107,11 +108,12 @@ A Turing machine is a 7-tuple T = (Q,Σ,Γ,δ,qI,qA,qR) where:
 δ(bac, _) -> (bad, , L)
 δ(bad, Γ \ X) -> (bad, , L)
 δ(bad, X) -> (aa, 1, L)
-δ(bab, 1*) -> (bad, 1, R)
+δ(bab, 1*) -> (bae, 1, R)
 δ(bae, Γ \ _) -> (bae, , R)
 δ(bae, _) -> (baf, , L)
 δ(baf, Γ \ X) -> (baf, , L)
 δ(baf, X) -> (ba, 0, L)
+δ(bab, Γ \ {0*,1*,$}) -> (bab, , L)
 
 δ(bba, Γ \ $) -> (bba, , L)
 δ(bba, $) -> (bbb, , L)
@@ -120,21 +122,25 @@ A Turing machine is a 7-tuple T = (Q,Σ,Γ,δ,qI,qA,qR) where:
 δ(bbc, _) -> (bbd, , L)
 δ(bbd, Γ \ X) -> (bbd, , L)
 δ(bbd, X) -> (ba, 0, L)
-δ(bbb, 1*) -> (bbd, 1, R)
+δ(bbb, 1*) -> (bbe, 1, R)
 δ(bbe, Γ \ _) -> (bbe, , R)
 δ(bbe, _) -> (bbf, , L)
 δ(bbf, Γ \ X) -> (bbf, , L)
 δ(bbf, X) -> (ba, 1, L)
+δ(bbb, $) -> (bbc, , R)
+δ(bbb, Γ \ {0*,1*,$}) -> (bbb, , L)
 
-δ(ca, Γ \ $) -> (ca, , L)
-δ(ca, $) -> (cb, , L)
+δ(za, Γ \ $) -> (za, , L)
+δ(za, $) -> (zb, , R)
 
-δ(cb, Γ \ {0,1,_}) -> (cb, , R)
-δ(cb, 0) -> (cc, 1, R)
-δ(cb, 1) -> (cb, 1, R)
-δ(cb, _) -> (sa, 1, R)
+δ(zb, Γ \ {0,1,_}) -> (zb, , R)
+δ(zb, 0) -> (zc, 1, R)
+δ(zb, 1) -> (zb, 1, R)
+δ(zb, _) -> (zd, 1, R)
 
-δ(cc, Γ \ {0,1,_}) -> (cc, , R)
-δ(cc, 0) -> (cc, 0, R)
-δ(cc, 1) -> (cb, 0, R)
-δ(cc, _) -> (sa, 0, R)
+δ(zc, Γ \ {0,1,_}) -> (zc, , R)
+δ(zc, 0) -> (zc, 0, R)
+δ(zc, 1) -> (zb, 0, R)
+δ(zc, _) -> (zd, 0, R)
+
+δ(zd, _) -> (sa, $, R)
diff --git a/entries/jj/tm/tm.nim b/entries/jj/tm/tm.nim
new file mode 100644
index 0000000..42b9ff4
--- /dev/null
+++ b/entries/jj/tm/tm.nim
@@ -0,0 +1,192 @@
+# A simple Turing machine simulator implemented in Nim.
+
+import std/enumerate
+
+type Symbol = enum
+  `_`, `$`, `X`, `0`, `1`, `0*`, `1*`,
+  noop
+
+type Tape = seq[Symbol]
+
+type Direction = enum
+  L, R, S
+
+type State = enum
+  ca, cb, cc, cd, ce, cf, cg, ch, ci
+  sa, sb, sc, sd,
+  aa, ab, ac,
+  aaa, aab, aac, aad, aae, aaf,
+  aba, abb, abc, abd, abe, abf,
+  ba, bb, bc,
+  baa, bab, bac, bad, bae, baf,
+  bba, bbb, bbc, bbd, bbe, bbf,
+  za, zb, zc, zd
+
+type Transition = object
+  current_state: State
+  read_symbol: seq[Symbol]
+  next_state: State
+  write_symbol: Symbol
+  move_direction: Direction
+
+# convenience constructor
+func δ(a: State, b: seq[Symbol], c: State, d: Symbol, e: Direction): Transition =
+  return Transition(current_state: a, read_symbol: b, next_state: c, write_symbol: d, move_direction: e)
+
+# safe get for an infinite tape: pretty, right?
+func get(tape: var Tape, i: int): Symbol =
+  for j in tape.len .. i:
+    tape.add(`_`)
+  return tape[i]
+
+# safe set for an infinite tape
+func set(tape: var Tape, i: int, s: Symbol) =
+  for j in tape.len .. i:
+    tape.add(`_`)
+  tape[i] = s
+
+let turing_machine = @[
+  δ(ca, @[`_`, `$`, `X`, `0`, `1`, `0*`, `1*`], cb, `$`, R),
+  δ(cb, @[`_`, `$`, `X`, `0`, `1`, `0*`, `1*`], cc, `0`, R),
+  δ(cc, @[`_`, `$`, `X`, `0`, `1`, `0*`, `1*`], cd, `$`, R),
+  δ(cd, @[`_`, `$`, `X`, `0`, `1`, `0*`, `1*`], ce, `1*`, R),
+  δ(ce, @[`_`, `$`, `X`, `0`, `1`, `0*`, `1*`], cf, `$`, R),
+  δ(cf, @[`_`, `$`, `X`, `0`, `1`, `0*`, `1*`], cg, `1`, R),
+  δ(cg, @[`_`, `$`, `X`, `0`, `1`, `0*`, `1*`], ch, `$`, R),
+  δ(ch, @[`$`, `X`, `0`, `1`, `0*`, `1*`], ci, `_`, R),
+  δ(ch, @[`_`], sa, noop, S),
+
+  δ(sa, @[`_`, `X`, `0`, `1`, `0*`, `1*`], sa, noop, L),
+  δ(sa, @[`$`], sb, noop, L),
+  δ(sb, @[`_`, `X`, `0*`, `1*`], sb, noop, L),
+  δ(sb, @[`0`], sc, `0*`, R),
+  δ(sb, @[`1`], sc, `1*`, R),
+  δ(sb, @[`$`], sd, noop, R),
+  δ(sc, @[`$`, `X`, `0`, `1`, `0*`, `1*`], sc, noop, R),
+  δ(sc, @[`_`], sa, `X`, L),
+  δ(sd, @[`$`, `X`, `0`, `1`], sd, noop, R),
+  δ(sd, @[`0*`], sd, `0`, R),
+  δ(sd, @[`1*`], sd, `1`, R),
+  δ(sd, @[`_`], aa, noop, L),
+
+  δ(aa, @[`_`, `X`, `0`, `1`, `0*`, `1*`], aa, noop, L),
+  δ(aa, @[`$`], ab, noop, L),
+  δ(ab, @[`_`, `X`, `0*`, `1*`], ab, noop, L),
+  δ(ab, @[`0`], aaa, `0*`, L),
+  δ(ab, @[`1`], aba, `1*`, L),
+  δ(ab, @[`$`], ac, noop, R),
+  δ(ac, @[`$`, `X`, `0`, `1`, `0*`, `1*`], ac, noop, R),
+  δ(ac, @[`_`], sa, `$`, R),
+
+  δ(aaa, @[`_`, `X`, `0`, `1`, `0*`, `1*`], aaa, noop, L),
+  δ(aaa, @[`$`], aab, noop, L),
+  δ(aab, @[`0*`], aac, `0`, R),
+  δ(aac, @[`$`, `X`, `0`, `1`, `0*`, `1*`], aac, noop, R),
+  δ(aac, @[`_`], aad, noop, L),
+  δ(aad, @[`_`, `$`, `0`, `1`, `0*`, `1*`], aad, noop, L),
+  δ(aad, @[`X`], aa, `0`, L),
+  δ(aab, @[`1*`], aae, `1`, R),
+  δ(aae, @[`$`, `X`, `0`, `1`, `0*`, `1*`], aae, noop, R),
+  δ(aae, @[`_`], aaf, noop, L),
+  δ(aaf, @[`_`, `$`, `0`, `1`, `0*`, `1*`], aaf, noop, L),
+  δ(aaf, @[`X`], aa, `1`, L),
+  δ(aab, @[`_`, `X`, `0`, `1`], aab, noop, L),
+
+  δ(aba, @[`_`, `X`, `0`, `1`, `0*`, `1*`], aba, noop, L),
+  δ(aba, @[`$`], abb, noop, L),
+  δ(abb, @[`0*`], abc, `0`, R),
+  δ(abc, @[`$`, `X`, `0`, `1`, `0*`, `1*`], abc, noop, R),
+  δ(abc, @[`_`], abd, noop, L),
+  δ(abd, @[`_`, `$`, `0`, `1`, `0*`, `1*`], abd, noop, L),
+  δ(abd, @[`X`], aa, `1`, L),
+  δ(abb, @[`1*`], abe, `1`, R),
+  δ(abe, @[`$`, `X`, `0`, `1`, `0*`, `1*`], abe, noop, R),
+  δ(abe, @[`_`], abf, noop, L),
+  δ(abf, @[`_`, `$`, `0`, `1`, `0*`, `1*`], abf, noop, L),
+  δ(abf, @[`X`], ba, `0`, L),
+  δ(abb, @[`$`], abc, noop, R),
+  δ(abb, @[`_`, `X`, `0`, `1`], abb, noop, L),
+
+  δ(ba, @[`_`, `X`, `0`, `1`, `0*`, `1*`], ba, noop, L),
+  δ(ba, @[`$`], bb, noop, L),
+  δ(bb, @[`_`, `X`, `0*`, `1*`], bb, noop, L),
+  δ(bb, @[`0`], baa, `0*`, L),
+  δ(bb, @[`1`], bba, `1*`, L),
+  δ(bb, @[`$`], bc, noop, R),
+  δ(bc, @[`$`, `X`, `0`, `1`, `0*`, `1*`], bc, noop, R),
+  δ(bc, @[`_`], za, noop, L),
+
+  δ(baa, @[`_`, `X`, `0`, `1`, `0*`, `1*`], baa, noop, L),
+  δ(baa, @[`$`], bab, noop, L),
+  δ(bab, @[`0*`], bac, `0`, R),
+  δ(bac, @[`$`, `X`, `0`, `1`, `0*`, `1*`], bac, noop, R),
+  δ(bac, @[`_`], bad, noop, L),
+  δ(bad, @[`_`, `$`, `0`, `1`, `0*`, `1*`], bad, noop, L),
+  δ(bad, @[`X`], aa, `1`, L),
+  δ(bab, @[`1*`], bae, `1`, R),
+  δ(bae, @[`$`, `X`, `0`, `1`, `0*`, `1*`], bae, noop, R),
+  δ(bae, @[`_`], baf, noop, L),
+  δ(baf, @[`_`, `$`, `0`, `1`, `0*`, `1*`], baf, noop, L),
+  δ(baf, @[`X`], ba, `0`, L),
+  δ(bab, @[`_`, `X`, `0`, `1`], bab, noop, L),
+
+  δ(bba, @[`_`, `X`, `0`, `1`, `0*`, `1*`], bba, noop, L),
+  δ(bba, @[`$`], bbb, noop, L),
+  δ(bbb, @[`0*`], bbc, `0`, R),
+  δ(bbc, @[`$`, `X`, `0`, `1`, `0*`, `1*`], bbc, noop, R),
+  δ(bbc, @[`_`], bbd, noop, L),
+  δ(bbd, @[`_`, `$`, `0`, `1`, `0*`, `1*`], bbd, noop, L),
+  δ(bbd, @[`X`], ba, `0`, L),
+  δ(bbb, @[`1*`], bbe, `1`, R),
+  δ(bbe, @[`$`, `X`, `0`, `1`, `0*`, `1*`], bbe, noop, R),
+  δ(bbe, @[`_`], bbf, noop, L),
+  δ(bbf, @[`_`, `$`, `0`, `1`, `0*`, `1*`], bbf, noop, L),
+  δ(bbf, @[`X`], ba, `1`, L),
+  δ(bbb, @[`_`, `X`, `0`, `1`], bbb, noop, L),
+  δ(bbb, @[`$`], bbc, noop, R),
+
+  δ(za, @[`_`, `X`, `0`, `1`, `0*`, `1*`], za, noop, L),
+  δ(za, @[`$`], zb, noop, R),
+
+  δ(zb, @[`$`, `X`, `0*`, `1*`], zb, noop, R),
+  δ(zb, @[`0`], zc, `1`, R),
+  δ(zb, @[`1`], zb, `1`, R),
+  δ(zb, @[`_`], zd, `1`, R),
+
+  δ(zc, @[`$`, `X`, `0*`, `1*`], zc, noop, R),
+  δ(zc, @[`0`], zc, `0`, R),
+  δ(zc, @[`1`], zb, `0`, R),
+  δ(zc, @[`_`], zd, `0`, R),
+
+  δ(zd, @[`_`], sa, `$`, R)
+]
+
+proc print(state: State, tape: Tape, position: int) =
+  stdout.write($state)
+  for i, s in enumerate(tape):
+    if i == position:
+      stdout.write("[" & $s & "]")
+    elif s == `$`:
+      stdout.write(" ")
+    else:
+      stdout.write($s)
+  stdout.write("\n")
+
+var state = ca
+var position = 0
+var tape = @[`_`]
+
+proc step() =
+  # print(state, tape, position)
+  for δ in turing_machine:
+    if state == δ.current_state and tape.get(position) in δ.read_symbol:
+      state = δ.next_state
+      if δ.write_symbol != noop: tape.set(position, δ.write_symbol)
+      if δ.move_direction == L: position.dec
+      elif δ.move_direction == R: position.inc
+      return
+  echo "Invalid state! crashing"
+  quit()
+
+while true:
+  step()