From 972c5f34cd093d44e801bf6b41ac0af2032b0b96 Mon Sep 17 00:00:00 2001 From: Braxton Hall Date: Mon, 3 Jul 2023 14:23:56 -0700 Subject: Update JJ's username --- people.json | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/people.json b/people.json index ea6f724..1a0f3db 100644 --- a/people.json +++ b/people.json @@ -617,7 +617,7 @@ ] }, { - "github": "j-james", + "github": "omentic", "name": "JJ", "title": "BSc Student, UBC", "entries": [ -- cgit v1.2.3-70-g09d2 From c37b806da507a699624ec4e800522ef4a47ad7bc Mon Sep 17 00:00:00 2001 From: braxtonhall Date: Thu, 13 Jul 2023 20:26:58 +0200 Subject: Update directories --- entries/jj/nim/fib.nim | 17 --- entries/jj/tiles/README.md | 13 --- entries/jj/tiles/example.png | Bin 94057 -> 0 bytes entries/jj/tiles/fib.png | Bin 26282 -> 0 bytes entries/jj/tm/fib-desc.txt | 219 -------------------------------------- entries/jj/tm/fib.txt | 144 ------------------------- entries/jj/tm/tm.nim | 189 -------------------------------- entries/omentic/nim/fib.nim | 17 +++ entries/omentic/tiles/README.md | 13 +++ entries/omentic/tiles/example.png | Bin 0 -> 94057 bytes entries/omentic/tiles/fib.png | Bin 0 -> 26282 bytes entries/omentic/tm/fib-desc.txt | 219 ++++++++++++++++++++++++++++++++++++++ entries/omentic/tm/fib.txt | 144 +++++++++++++++++++++++++ entries/omentic/tm/tm.nim | 189 ++++++++++++++++++++++++++++++++ people.json | 6 +- 15 files changed, 585 insertions(+), 585 deletions(-) delete mode 100644 entries/jj/nim/fib.nim delete mode 100644 entries/jj/tiles/README.md delete mode 100644 entries/jj/tiles/example.png delete mode 100644 entries/jj/tiles/fib.png delete mode 100644 entries/jj/tm/fib-desc.txt delete mode 100644 entries/jj/tm/fib.txt delete mode 100644 entries/jj/tm/tm.nim create mode 100644 entries/omentic/nim/fib.nim create mode 100644 entries/omentic/tiles/README.md create mode 100644 entries/omentic/tiles/example.png create mode 100644 entries/omentic/tiles/fib.png create mode 100644 entries/omentic/tm/fib-desc.txt create mode 100644 entries/omentic/tm/fib.txt create mode 100644 entries/omentic/tm/tm.nim 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 Binary files a/entries/jj/tiles/example.png and /dev/null differ diff --git a/entries/jj/tiles/fib.png b/entries/jj/tiles/fib.png deleted file mode 100644 index 7668696..0000000 Binary files a/entries/jj/tiles/fib.png and /dev/null 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() 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. + +![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/omentic/tiles/example.png b/entries/omentic/tiles/example.png new file mode 100644 index 0000000..28b7365 Binary files /dev/null and b/entries/omentic/tiles/example.png differ diff --git a/entries/omentic/tiles/fib.png b/entries/omentic/tiles/fib.png new file mode 100644 index 0000000..7668696 Binary files /dev/null and b/entries/omentic/tiles/fib.png differ 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() diff --git a/people.json b/people.json index 1a0f3db..0369227 100644 --- a/people.json +++ b/people.json @@ -623,15 +623,15 @@ "entries": [ { "name": "nim", - "link": "./entries/jj/nim/fib.nim" + "link": "./entries/omentic/nim/fib.nim" }, { "name": "turing machine", - "link": "./entries/jj/tm/fib.txt" + "link": "./entries/omentic/tm/fib.txt" }, { "name": "wang tiling", - "link": "./entries/jj/tiles/fib.png" + "link": "./entries/omentic/tiles/fib.png" } ] }, -- cgit v1.2.3-70-g09d2