diff options
Diffstat (limited to 'entries/omentic')
| -rw-r--r-- | entries/omentic/nim/fib.nim | 17 | ||||
| -rw-r--r-- | entries/omentic/tiles/README.md | 13 | ||||
| -rw-r--r-- | entries/omentic/tiles/example.png | bin | 0 -> 94057 bytes | |||
| -rw-r--r-- | entries/omentic/tiles/fib.png | bin | 0 -> 26282 bytes | |||
| -rw-r--r-- | entries/omentic/tm/fib-desc.txt | 219 | ||||
| -rw-r--r-- | entries/omentic/tm/fib.txt | 144 | ||||
| -rw-r--r-- | entries/omentic/tm/tm.nim | 189 |
7 files changed, 582 insertions, 0 deletions
diff --git a/entries/omentic/nim/fib.nim b/entries/omentic/nim/fib.nim new file mode 100644 index 0000000..a12f8e6 --- /dev/null +++ b/entries/omentic/nim/fib.nim @@ -0,0 +1,17 @@ +func fib(n: Natural): Natural = + if n < 2: + return n + else: + return fib(n-1) + fib(n-2) + +func fib2(n: int, a = 0, b = 1): int = + return if n == 0: a else: fib2(n-1, b, a+b) + +iterator fib3: int = + var a = 0 + var b = 1 + while true: + yield a + swap a, b + b += a + diff --git a/entries/omentic/tiles/README.md b/entries/omentic/tiles/README.md new file mode 100644 index 0000000..ba10578 --- /dev/null +++ b/entries/omentic/tiles/README.md @@ -0,0 +1,13 @@ +# Wang Tiling + +These are Wang tiles. For more information, see https://en.wikipedia.org/wiki/Wang_tile. + + + +There is only one arrangement of these tiles that tiles the infinite plane _aperiodically_. This arrangement forms the Fibonacci sequence. + +Begin by placing down the third tile (the one with the North and West edges being black, the East edge being green, and the South edge being yellow), and continue by placing tiles such that the infinite plane can continue to be filled. The eleventh tile (the one with the North edge being black and the West, East, and South edges being purple) will appear in Fibonacci-spaced intervals. + + + +The algorithm for this is adapted from https://grahamshawcross.com/2012/10/12/wang-tiles-and-turing-machines/ (with some fixes and tweaks). diff --git a/entries/omentic/tiles/example.png b/entries/omentic/tiles/example.png Binary files differnew file mode 100644 index 0000000..28b7365 --- /dev/null +++ b/entries/omentic/tiles/example.png diff --git a/entries/omentic/tiles/fib.png b/entries/omentic/tiles/fib.png Binary files differnew file mode 100644 index 0000000..7668696 --- /dev/null +++ b/entries/omentic/tiles/fib.png diff --git a/entries/omentic/tm/fib-desc.txt b/entries/omentic/tm/fib-desc.txt new file mode 100644 index 0000000..b98b324 --- /dev/null +++ b/entries/omentic/tm/fib-desc.txt @@ -0,0 +1,219 @@ +The following is a low-level description of a Turing machine that will write +the Fibonacci sequence (represented in binary, separated by $) without halting. + +A Turing machine is a 7-tuple T = (Q,Σ,Γ,δ,qI,qA,qR) where: +- Q is the set of states; non-empty and finite +- Σ is the input alphabet; non-empty and finite +- Γ is the tape alphabet; non-empty and finite +- δ is the transition function: δ(Q, Γ) -> (Q, Γ, {L, R}) +- qI ∈ Q is the initial state +- qA ∈ Q is the accept state +- 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, + ba, bb, bc, + baa, bab, bac, bad, bae, baf, + bba, bbb, bbc, bbd, bbe, bbf, + za, zb, zc, zd +} +- Σ: not relevant as we entirely disregard the input to begin with. +- Γ: {_, $, X, 0, 1, 0*, 1*} (_ means the blank symbol) +- δ: described below. a note on syntax: + - no entry in the output parameter means do not write a character to the tape. + - similarly, no entry in the position parameter means do not move the tape head. + - numerous "possible" transition functions are not stated. those are thought by the author to be inaccessible in normal operation of this machine (and if they are, it is probably a bug). +- qI: the initial state is ca. +- qA: the machine does not accept. +- qR: the machine does not reject. + +Overview: +1. We clear the tape and write our initial state: the first three Fibonacci numbers +2. We write a number of Xs to the end of the tape for convenience +3. We add the last two numbers of the sequence digit-by-digit to create another number + - Effort/pain is taken to ensure carrying works: including when the next number is a digit larger +4. Upon having created the new Fibonacci number, we write a $ and repeat from step 3, ad nauseam + +states c*: clearing the initial tape +- clear the tape: write $0$1$1$, then write _ until reading a _ + +δ(ca, Γ) -> (cb, $, R) +δ(cb, Γ) -> (cc, 0, R) +δ(cc, Γ) -> (cd, $, R) +δ(cd, Γ) -> (ce, 1*, R) +δ(ce, Γ) -> (cf, $, R) +δ(cf, Γ) -> (cg, 1, R) +δ(cg, Γ) -> (ch, $, R) +δ(ch, Γ \ _) -> (ci, _, R) +δ(ch, _) -> (sa, , ) + + +states s*: making space for the next number +- from the end: append XX...X where len(XX...X) = len(previous_number) + +δ(sa, {_,X}) -> (sa, , L) +δ(sa, $) -> (sb, , L) + +δ(sb, {0*,1*}) -> (sb, , L) +δ(sb, 0) -> (sc, 0*, R) +δ(sb, 1) -> (sc, 1*, R) +δ(sb, $) -> (sd, , R) + +δ(sc, Γ \ _) -> (sc, , R) +δ(sc, _) -> (sa, X, L) + +δ(sd, {$,X}) -> (sd, , R) +δ(sd, 0*) -> (sd, 0, R) +δ(sd, 1*) -> (sd, 1, R) +δ(sd, _) -> (aa, , L) + + +states a*: add the last digit of both numbers without carrying +- read left until $, then read left until: + - 0: replace with 0*, goto state (aaa) + - 1: replace with 1*, goto state (aba) + - $: do not replace, read right until _, write $, goto state (s) + +δ(aa, {X,0,1}) -> (aa, , L) +δ(aa, $) -> (ab, , L) + +δ(ab, {0*,1*}) -> (ab, , L) +δ(ab, 0) -> (aaa, 0*, L) +δ(ab, 1) -> (aba, 1*, L) + +δ(ab, $) -> (ac, , R) +δ(ac, Γ \ _) -> (ac, , R) +δ(ac, _) -> (sa, $, R) + +states aa* +- read left until $, then read left until: + - 0*: replace with 0, read right until _, then read left until X and replace with 0 + - 1*: replace with 1, read right until _, then read left until X and replace with 1 + +δ(aaa, {0,1}) -> (aaa, , L) +δ(aaa, $) -> (aab, , L) + +δ(aab, 0*) -> (aac, 0, R) +δ(aac, Γ \ _) -> (aac, , R) +δ(aac, _) -> (aad, , L) +δ(aad, {0,1}) -> (aad, , L) +δ(aad, X) -> (aa, 0, L) + +δ(aab, 1*) -> (aae, 1, R) +δ(aae, Γ \ _) -> (aae, , R) +δ(aae, _) -> (aaf, , L) +δ(aaf, {0,1}) -> (aaf, , L) +δ(aaf, X) -> (aa, 1, L) + +δ(aab, {0,1}) -> (aab, , L) + +states ab* +- read left until $, then read left until: + - 0*: replace with 0, read right until _, then read left until X and replace with 1 + - $: do not replace, read right until _, then read left until X and replace with 1 + - 1*: replace with 1, read right until _, then read left until X and replace with 0, goto state (b) + +δ(aba, {0,1}) -> (aba, , L) +δ(aba, $) -> (abb, , L) + +δ(abb, 0*) -> (abc, 0, R) +δ(abc, Γ \ _) -> (abc, , R) +δ(abc, _) -> (abd, , L) +δ(abd, {0,1}) -> (abd, , L) +δ(abd, X) -> (aa, 1, L) + +δ(abb, 1*) -> (abe, 1, R) +δ(abe, Γ \ _) -> (abe, , R) +δ(abe, _) -> (abf, , L) +δ(abf, {0,1}) -> (abf, , L) +δ(abf, 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 (za) + +δ(ba, {X,0,1}) -> (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, _) -> (za, , L) + +states ba* +- read left until $, then read left until: + - 0*: replace with 0, read right until _, then read left until X and replace with 1, then goto state (aa) + - 1*: replace with 1, read right until _, then read left until X and replace with 0, then goto state (ba) + +δ(baa, {0,1}) -> (baa, , L) +δ(baa, $) -> (bab, , L) + +δ(bab, 0*) -> (bac, 0, R) +δ(bac, Γ \ _) -> (bac, , R) +δ(bac, _) -> (bad, , L) +δ(bad, {0,1}) -> (bad, , L) +δ(bad, X) -> (aa, 1, L) + +δ(bab, 1*) -> (bae, 1, R) +δ(bae, Γ \ _) -> (bae, , R) +δ(bae, _) -> (baf, , L) +δ(baf, {0,1}) -> (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) + - 1*: replace with 1, read right until _, then read left until X and replace with 1, goto state (ba) + +δ(bba, {0,1}) -> (bba, , L) +δ(bba, $) -> (bbb, , L) + +δ(bbb, 0*) -> (bbc, 0, R) +δ(bbc, Γ \ _) -> (bbc, , R) +δ(bbc, _) -> (bbd, , L) +δ(bbd, {0,1}) -> (bbd, , L) +δ(bbd, X) -> (ba, 0, L) + +δ(bbb, 1*) -> (bbe, 1, R) +δ(bbe, Γ \ _) -> (bbe, , R) +δ(bbe, _) -> (bbf, , L) +δ(bbf, {0,1}) -> (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) + +δ(za, {0,1}) -> (za, , L) +δ(za, $) -> (zb, , R) + +δ(zb, 0) -> (zc, 1, R) +δ(zb, 1) -> (zb, 1, R) +δ(zb, _) -> (zd, 1, R) + +δ(zc, 0) -> (zc, 0, R) +δ(zc, 1) -> (zb, 0, R) +δ(zc, _) -> (zd, 0, R) + +δ(zd, _) -> (sa, $, R) diff --git a/entries/omentic/tm/fib.txt b/entries/omentic/tm/fib.txt new file mode 100644 index 0000000..402db15 --- /dev/null +++ b/entries/omentic/tm/fib.txt @@ -0,0 +1,144 @@ +The following is a low-level description of a Turing machine that will write +the Fibonacci sequence (represented in binary, separated by $) without halting. + +A Turing machine is a 7-tuple T = (Q,Σ,Γ,δ,qI,qA,qR) where: +- Q is the set of states; non-empty and finite +- Σ is the input alphabet; non-empty and finite +- Γ is the tape alphabet; non-empty and finite +- δ is the transition function: δ(Q, Γ) -> (Q, Γ, {L, R}) +- qI ∈ Q is the initial state +- qA ∈ Q is the accept state +- 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, + ba, bb, bc, + baa, bab, bac, bad, bae, baf, + bba, bbb, bbc, bbd, bbe, bbf, + za, zb, zc, zd +} +- Σ: not relevant as we entirely disregard the input to begin with. +- Γ: {_, $, X, 0, 1, 0*, 1*} (_ means the blank symbol) +- δ: described below. a note on syntax: + - no entry in the output parameter means do not write a character to the tape. + - similarly, no entry in the position parameter means do not move the tape head. + - numerous "possible" transition functions are not stated. those are thought by the author to be inaccessible in normal operation of this machine (and if they are, it is probably a bug). +- qI: the initial state is ca. +- qA: the machine does not accept. +- qR: the machine does not reject. + +δ(ca, Γ) -> (cb, $, R) +δ(cb, Γ) -> (cc, 0, R) +δ(cc, Γ) -> (cd, $, R) +δ(cd, Γ) -> (ce, 1*, R) +δ(ce, Γ) -> (cf, $, R) +δ(cf, Γ) -> (cg, 1, R) +δ(cg, Γ) -> (ch, $, R) +δ(ch, Γ \ _) -> (ci, _, R) +δ(ch, _) -> (sa, , ) + +δ(sa, {_,X}) -> (sa, , L) +δ(sa, $) -> (sb, , L) +δ(sb, {0*,1*}) -> (sb, , L) +δ(sb, 0) -> (sc, 0*, R) +δ(sb, 1) -> (sc, 1*, R) +δ(sb, $) -> (sd, , R) +δ(sc, Γ \ _) -> (sc, , R) +δ(sc, _) -> (sa, X, L) +δ(sd, {$,X}) -> (sd, , R) +δ(sd, 0*) -> (sd, 0, R) +δ(sd, 1*) -> (sd, 1, R) +δ(sd, _) -> (aa, , L) + +δ(aa, {X,0,1}) -> (aa, , L) +δ(aa, $) -> (ab, , L) +δ(ab, {0*,1*}) -> (ab, , L) +δ(ab, 0) -> (aaa, 0*, L) +δ(ab, 1) -> (aba, 1*, L) +δ(ab, $) -> (ac, , R) +δ(ac, Γ \ _) -> (ac, , R) +δ(ac, _) -> (sa, $, R) + +δ(aaa, {0,1}) -> (aaa, , L) +δ(aaa, $) -> (aab, , L) +δ(aab, 0*) -> (aac, 0, R) +δ(aac, Γ \ _) -> (aac, , R) +δ(aac, _) -> (aad, , L) +δ(aad, {0,1}) -> (aad, , L) +δ(aad, X) -> (aa, 0, L) +δ(aab, 1*) -> (aae, 1, R) +δ(aae, Γ \ _) -> (aae, , R) +δ(aae, _) -> (aaf, , L) +δ(aaf, {0,1}) -> (aaf, , L) +δ(aaf, X) -> (aa, 1, L) +δ(aab, {0,1}) -> (aab, , L) + +δ(aba, {0,1}) -> (aba, , L) +δ(aba, $) -> (abb, , L) +δ(abb, 0*) -> (abc, 0, R) +δ(abc, Γ \ _) -> (abc, , R) +δ(abc, _) -> (abd, , L) +δ(abd, {0,1}) -> (abd, , L) +δ(abd, X) -> (aa, 1, L) +δ(abb, 1*) -> (abe, 1, R) +δ(abe, Γ \ _) -> (abe, , R) +δ(abe, _) -> (abf, , L) +δ(abf, {0,1}) -> (abf, , L) +δ(abf, X) -> (ba, 0, L) +δ(abb, $) -> (abc, , R) +δ(abb, {0,1}) -> (abb, , L) + +δ(ba, {X,0,1}) -> (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, _) -> (za, , L) + +δ(baa, {0,1}) -> (baa, , L) +δ(baa, $) -> (bab, , L) +δ(bab, 0*) -> (bac, 0, R) +δ(bac, Γ \ _) -> (bac, , R) +δ(bac, _) -> (bad, , L) +δ(bad, {0,1}) -> (bad, , L) +δ(bad, X) -> (aa, 1, L) +δ(bab, 1*) -> (bae, 1, R) +δ(bae, Γ \ _) -> (bae, , R) +δ(bae, _) -> (baf, , L) +δ(baf, {0,1}) -> (baf, , L) +δ(baf, X) -> (ba, 0, L) +δ(bab, {0,1}) -> (bab, , L) + +δ(bba, {0,1}) -> (bba, , L) +δ(bba, $) -> (bbb, , L) +δ(bbb, 0*) -> (bbc, 0, R) +δ(bbc, Γ \ _) -> (bbc, , R) +δ(bbc, _) -> (bbd, , L) +δ(bbd, {0,1}) -> (bbd, , L) +δ(bbd, X) -> (ba, 0, L) +δ(bbb, 1*) -> (bbe, 1, R) +δ(bbe, Γ \ _) -> (bbe, , R) +δ(bbe, _) -> (bbf, , L) +δ(bbf, {0,1}) -> (bbf, , L) +δ(bbf, X) -> (ba, 1, L) +δ(bbb, $) -> (bbc, , R) +δ(bbb, {0,1}) -> (bbb, , L) + +δ(za, {0,1}) -> (za, , L) +δ(za, $) -> (zb, , R) + +δ(zb, 0) -> (zc, 1, R) +δ(zb, 1) -> (zb, 1, R) +δ(zb, _) -> (zd, 1, R) + +δ(zc, 0) -> (zc, 0, R) +δ(zc, 1) -> (zb, 0, R) +δ(zc, _) -> (zd, 0, R) + +δ(zd, _) -> (sa, $, R) diff --git a/entries/omentic/tm/tm.nim b/entries/omentic/tm/tm.nim new file mode 100644 index 0000000..71debe4 --- /dev/null +++ b/entries/omentic/tm/tm.nim @@ -0,0 +1,189 @@ +# 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: set[Symbol] + next_state: State + write_symbol: Symbol + move_direction: Direction + +# convenience constructor +func δ(a: State, b: set[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, {`_`}, cb, `$`, R), + δ(cb, {`_`}, cc, `0`, R), + δ(cc, {`_`}, cd, `$`, R), + δ(cd, {`_`}, ce, `1*`, R), + δ(ce, {`_`}, cf, `$`, R), + δ(cf, {`_`}, cg, `1`, R), + δ(cg, {`_`}, ch, `$`, R), + δ(ch, {`_`}, sa, noop, S), + + δ(sa, {`_`, `X`}, sa, noop, L), + δ(sa, {`$`}, sb, noop, L), + δ(sb, {`0*`, `1*`}, sb, noop, L), + δ(sb, {`0`}, sc, `0*`, R), + δ(sb, {`1`}, sc, `1*`, R), + δ(sb, {`$`}, sd, noop, R), + δ(sc, {`$`, `X`, `0*`, `1*`}, sc, noop, R), + δ(sc, {`_`}, sa, `X`, L), + δ(sd, {`$`, `X`}, sd, noop, R), + δ(sd, {`0*`}, sd, `0`, R), + δ(sd, {`1*`}, sd, `1`, R), + δ(sd, {`_`}, aa, noop, L), + + δ(aa, {`X`, `0`, `1`}, aa, noop, L), + δ(aa, {`$`}, ab, noop, L), + δ(ab, {`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, {`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`}, 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`}, aaf, noop, L), + δ(aaf, {`X`}, aa, `1`, L), + δ(aab, {`0`, `1`}, aab, noop, L), + + δ(aba, {`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`}, 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`}, abf, noop, L), + δ(abf, {`X`}, ba, `0`, L), + δ(abb, {`$`}, abc, noop, R), + δ(abb, {`0`, `1`}, abb, noop, L), + + δ(ba, {`X`, `0`, `1`}, ba, noop, L), + δ(ba, {`$`}, bb, noop, L), + δ(bb, {`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, {`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`}, 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`}, baf, noop, L), + δ(baf, {`X`}, ba, `0`, L), + δ(bab, {`0`, `1`}, bab, noop, L), + + δ(bba, {`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`}, 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`}, bbf, noop, L), + δ(bbf, {`X`}, ba, `1`, L), + δ(bbb, {`$`}, bbc, noop, R), + δ(bbb, {`0`, `1`}, bbb, noop, L), + + δ(za, {`0`, `1`}, za, noop, L), + δ(za, {`$`}, zb, noop, R), + + δ(zb, {`0`}, zc, `1`, R), + δ(zb, {`1`}, zb, `1`, R), + δ(zb, {`_`}, zd, `1`, 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() |
