aboutsummaryrefslogtreecommitdiff
path: root/entries/jj
diff options
context:
space:
mode:
authorbraxtonhall2023-07-13 18:26:58 +0000
committerbraxtonhall2023-07-13 18:26:58 +0000
commitc37b806da507a699624ec4e800522ef4a47ad7bc (patch)
treebfe99e81e91603508be51bcd31f7bbb4d48f6b6f /entries/jj
parent972c5f34cd093d44e801bf6b41ac0af2032b0b96 (diff)
Update directories
Diffstat (limited to 'entries/jj')
-rw-r--r--entries/jj/nim/fib.nim17
-rw-r--r--entries/jj/tiles/README.md13
-rw-r--r--entries/jj/tiles/example.pngbin94057 -> 0 bytes
-rw-r--r--entries/jj/tiles/fib.pngbin26282 -> 0 bytes
-rw-r--r--entries/jj/tm/fib-desc.txt219
-rw-r--r--entries/jj/tm/fib.txt144
-rw-r--r--entries/jj/tm/tm.nim189
7 files changed, 0 insertions, 582 deletions
diff --git a/entries/jj/nim/fib.nim b/entries/jj/nim/fib.nim
deleted file mode 100644
index a12f8e6..0000000
--- a/entries/jj/nim/fib.nim
+++ /dev/null
@@ -1,17 +0,0 @@
-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/jj/tiles/README.md b/entries/jj/tiles/README.md
deleted file mode 100644
index ba10578..0000000
--- a/entries/jj/tiles/README.md
+++ /dev/null
@@ -1,13 +0,0 @@
-# Wang Tiling
-
-These are Wang tiles. For more information, see https://en.wikipedia.org/wiki/Wang_tile.
-
-![Wang tiles](fib.png)
-
-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 aperiodic tiling](example.png)
-
-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/jj/tiles/example.png b/entries/jj/tiles/example.png
deleted file mode 100644
index 28b7365..0000000
--- a/entries/jj/tiles/example.png
+++ /dev/null
Binary files differ
diff --git a/entries/jj/tiles/fib.png b/entries/jj/tiles/fib.png
deleted file mode 100644
index 7668696..0000000
--- a/entries/jj/tiles/fib.png
+++ /dev/null
Binary files differ
diff --git a/entries/jj/tm/fib-desc.txt b/entries/jj/tm/fib-desc.txt
deleted file mode 100644
index b98b324..0000000
--- a/entries/jj/tm/fib-desc.txt
+++ /dev/null
@@ -1,219 +0,0 @@
-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/jj/tm/fib.txt b/entries/jj/tm/fib.txt
deleted file mode 100644
index 402db15..0000000
--- a/entries/jj/tm/fib.txt
+++ /dev/null
@@ -1,144 +0,0 @@
-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/jj/tm/tm.nim b/entries/jj/tm/tm.nim
deleted file mode 100644
index 71debe4..0000000
--- a/entries/jj/tm/tm.nim
+++ /dev/null
@@ -1,189 +0,0 @@
-# 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()