From c37b806da507a699624ec4e800522ef4a47ad7bc Mon Sep 17 00:00:00 2001 From: braxtonhall Date: Thu, 13 Jul 2023 20:26:58 +0200 Subject: Update directories --- entries/omentic/tm/tm.nim | 189 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 189 insertions(+) create mode 100644 entries/omentic/tm/tm.nim (limited to 'entries/omentic/tm/tm.nim') 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() -- cgit v1.2.3-70-g09d2