From 667253f48d20f76aff54f7ce9464b13c169ad96e Mon Sep 17 00:00:00 2001 From: j-james Date: Mon, 14 Nov 2022 23:55:42 -0800 Subject: Add cursed Fibonacci implementations --- fib/README.md | 3 + fib/nim/fib.nim | 16 + fib/tiles/README.md | 13 + fib/tiles/example.png | Bin 0 -> 94057 bytes fib/tiles/example.svg | 19092 ++++++++++++++++++++++++++++++++++++++++++++++++ fib/tiles/fib.png | Bin 0 -> 26282 bytes fib/tiles/fib.svg | 669 ++ fib/tiles/wang.svg | 602 ++ fib/tm/fib-desc.txt | 219 + fib/tm/fib.txt | 144 + fib/tm/tm.nim | 189 + 11 files changed, 20947 insertions(+) create mode 100644 fib/README.md create mode 100644 fib/nim/fib.nim create mode 100644 fib/tiles/README.md create mode 100644 fib/tiles/example.png create mode 100644 fib/tiles/example.svg create mode 100644 fib/tiles/fib.png create mode 100644 fib/tiles/fib.svg create mode 100644 fib/tiles/wang.svg create mode 100644 fib/tm/fib-desc.txt create mode 100644 fib/tm/fib.txt create mode 100644 fib/tm/tm.nim diff --git a/fib/README.md b/fib/README.md new file mode 100644 index 0000000..f321c29 --- /dev/null +++ b/fib/README.md @@ -0,0 +1,3 @@ +# the fibonacci only you would give me + +See [braxtonhall/fib](https://github.com/braxtonhall/fib) for more information. diff --git a/fib/nim/fib.nim b/fib/nim/fib.nim new file mode 100644 index 0000000..fc193f6 --- /dev/null +++ b/fib/nim/fib.nim @@ -0,0 +1,16 @@ +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/fib/tiles/README.md b/fib/tiles/README.md new file mode 100644 index 0000000..ba10578 --- /dev/null +++ b/fib/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/fib/tiles/example.png b/fib/tiles/example.png new file mode 100644 index 0000000..28b7365 Binary files /dev/null and b/fib/tiles/example.png differ diff --git a/fib/tiles/example.svg b/fib/tiles/example.svg new file mode 100644 index 0000000..0c6aab4 --- /dev/null +++ b/fib/tiles/example.svg @@ -0,0 +1,19092 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/fib/tiles/fib.png b/fib/tiles/fib.png new file mode 100644 index 0000000..7668696 Binary files /dev/null and b/fib/tiles/fib.png differ diff --git a/fib/tiles/fib.svg b/fib/tiles/fib.svg new file mode 100644 index 0000000..1f03ac0 --- /dev/null +++ b/fib/tiles/fib.svg @@ -0,0 +1,669 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/fib/tiles/wang.svg b/fib/tiles/wang.svg new file mode 100644 index 0000000..222b3a6 --- /dev/null +++ b/fib/tiles/wang.svg @@ -0,0 +1,602 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/fib/tm/fib-desc.txt b/fib/tm/fib-desc.txt new file mode 100644 index 0000000..b98b324 --- /dev/null +++ b/fib/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/fib/tm/fib.txt b/fib/tm/fib.txt new file mode 100644 index 0000000..402db15 --- /dev/null +++ b/fib/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/fib/tm/tm.nim b/fib/tm/tm.nim new file mode 100644 index 0000000..71debe4 --- /dev/null +++ b/fib/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() -- cgit v1.2.3-70-g09d2