diff options
Diffstat (limited to 'entries/jj/tm')
| -rw-r--r-- | entries/jj/tm/fib-desc.txt | 219 | ||||
| -rw-r--r-- | entries/jj/tm/fib.txt | 144 | ||||
| -rw-r--r-- | entries/jj/tm/tm.nim | 189 |
3 files changed, 0 insertions, 552 deletions
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() |