aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTom Harley2018-05-13 23:13:04 +0100
committerTom Harley2018-05-13 23:13:04 +0100
commit36872f5c2e65ffe1570e0f1758833e0253dee9ed (patch)
tree4d6ef61df030fbf86f148d9a4f4c67f05fba2ec5
downloadmachines-36872f5c2e65ffe1570e0f1758833e0253dee9ed.tar.gz
machines-36872f5c2e65ffe1570e0f1758833e0253dee9ed.zip

Initial commit

-rw-r--r--addition.tm65
-rwxr-xr-xbingen.sh12
-rwxr-xr-xcompile2
-rwxr-xr-xget-nim.sh5
-rw-r--r--lib.nim222
-rw-r--r--mt.nim41
-rwxr-xr-xpalgen.sh12
-rw-r--r--palindrome.tm35
-rw-r--r--report.md133
-rwxr-xr-xtest.sh14
-rw-r--r--test.tm10
-rw-r--r--tm.nim18
12 files changed, 569 insertions, 0 deletions
diff --git a/addition.tm b/addition.tm
new file mode 100644
index 0000000..f2b61f8
--- /dev/null
+++ b/addition.tm
@@ -0,0 +1,65 @@
+states 14
+S
+0A
+0B
+0C
+0D
+1A
+1B
+1C
+1D
+R1
+R2
+Ca
+_1
+_2 +
+alphabet 3 # 0 1
+S # S # R
+S 0 0A # R
+S 1 1A # R
+S _ _1 _ R
+0A # 0B _ R
+0A 0 0A 0 R
+0A 1 0A 1 R
+0A _ 0B _ R
+0B # 0D # R
+0B 0 0C _ R
+0B 1 1C _ R
+0B _ 0B _ R
+0C # 0D # R
+0C 0 0C 0 R
+0C 1 0C 1 R
+0D # 0D # R
+0D 0 R1 # L
+0D _ R1 _ L
+1A # 1B _ R
+1A 0 1A 0 R
+1A 1 1A 1 R
+1A _ 1B _ R
+1B # 1D # R
+1B 0 1C _ R
+1B 1 Ca _ R
+1B _ 1B _ R
+1C # 1D # R
+1C 0 1C 0 R
+1C 1 1C 1 R
+1D # 1D # R
+1D 1 R1 # L
+R1 # R1 # L
+R1 0 R1 0 L
+R1 1 R1 1 L
+R1 _ R2 _ L
+R2 # S # R
+R2 0 R2 0 L
+R2 1 R2 1 L
+R2 _ R2 _ L
+Ca # 0D 1 R
+Ca 0 0C 1 R
+Ca 1 Ca 0 R
+_1 # _2 # R
+_1 0 0C _ R
+_1 1 1C _ R
+_1 _ _1 _ R
+_2 # _2 # R
+_2 0 _2 0 R
+_2 1 0D 1 S
diff --git a/bingen.sh b/bingen.sh
new file mode 100755
index 0000000..b9a0717
--- /dev/null
+++ b/bingen.sh
@@ -0,0 +1,12 @@
+#!/bin/bash
+
+function dec2bin {
+ echo "obase=2;$1" | bc | tr -d '\n' | rev
+}
+
+for i in {1..1000} ; do
+ a=$RANDOM
+ b=$RANDOM
+ c=$(($a + $b))
+ echo "`dec2bin $a`#`dec2bin $b`#`dec2bin $c` true"
+done
diff --git a/compile b/compile
new file mode 100755
index 0000000..c95ef83
--- /dev/null
+++ b/compile
@@ -0,0 +1,2 @@
+#!/bin/sh
+nim c -d:tmname=$1 -d:release -o:$1 tm.nim
diff --git a/get-nim.sh b/get-nim.sh
new file mode 100755
index 0000000..3ec78c6
--- /dev/null
+++ b/get-nim.sh
@@ -0,0 +1,5 @@
+#!/bin/sh
+# Copied from https://nim-lang.org/install_unix.html:
+curl https://nim-lang.org/choosenim/init.sh -sSf | sh
+
+export PATH=$HOME/.nimble/bin:"$PATH"
diff --git a/lib.nim b/lib.nim
new file mode 100644
index 0000000..b909478
--- /dev/null
+++ b/lib.nim
@@ -0,0 +1,222 @@
+import hashes, tables, strutils, sets
+
+type
+ state* = string
+ letter* = char
+ input* = tuple[state: state, letter: letter]
+
+proc `$`(input: input): string =
+ "(" & $input[0] & " " & $input[1] & ")"
+
+type Direction* = enum
+ Dec = -1,
+ None = 0,
+ Inc = 1
+
+proc `$`*(this: Direction): string =
+ case this
+ of Dec:
+ return "L"
+ of None:
+ return "S"
+ of Inc:
+ return "R"
+
+type transition* = tuple[
+ newState: state,
+ toWrite: letter,
+ moveDir: Direction]
+
+proc `$`(t: transition): string =
+ "[" & $t.newState & " " & $t.toWrite & " " & $t.moveDir & "]"
+
+type tape* = Table[int, letter]
+type ttable* = Table[input, transition]
+
+type DTM* = ref object
+ currentState*: state
+ acceptingStates*: HashSet[state]
+ tape*: tape
+ position*: int
+ transitions*: Table[(state, letter), transition]
+
+type description* = tuple [
+ currentState: state,
+ acceptingStates: HashSet[state],
+ transitions: Table[input, transition]
+ ]
+
+# Parses a Direction from a string
+proc toDirection(token: string): Direction =
+ case token[0]
+ of 'R':
+ return Inc
+ of 'L':
+ return Dec
+ of 'S':
+ return None
+ else:
+ return None
+
+proc `[]`(this: DTM, i: int): letter =
+ if this.tape.hasKey(i):
+ return this.tape[i]
+ else:
+ return '_'
+
+proc `[]=`(this: DTM, i: int, l: letter) =
+ this.tape[i] = l
+
+# Tape string conversion
+proc `$`(this: DTM): string =
+ result = ""
+ for i in -150..150:
+ if i == 0:
+ result &= '['
+ result &= $this[this.position + i]
+ if i == 0:
+ result &= ']'
+
+proc write(this: DTM, c: letter): DTM {.discardable.} =
+ this[this.position] = c
+ return this
+
+## Write to and move DTM
+proc move(this: DTM, move: transition): DTM {.discardable.} =
+ # Change state:
+ this.currentState = move.newState
+ # Write to tape:
+ this[this.position] = move.toWrite
+ # Move position on tape:
+ this.position += cast[int](move.moveDir)
+ return this
+
+proc insert(this: var tape, input: string, p = 0): tape {.discardable.} =
+ for i, c in input:
+ this[i + p] = cast[letter](c)
+ return this
+
+# Makes a Tape containing this string
+proc tapeOf(input: string): tape =
+ result = initTable[int, letter]()
+ result.insert(input)
+
+## Fits this DTM with a Tape containing this string
+proc load(tm: DTM, input: string): DTM =
+ return DTM(
+ tape: tapeOf(input),
+ acceptingStates: tm.acceptingStates,
+ currentState: tm.currentState,
+ transitions: tm.transitions
+ )
+
+## Fits this DTM with a Tape containing this string
+proc `<<`(tm: DTM, input: string): DTM =
+ return tm.load(input)
+
+## Iterator over every line in a file
+proc lineIterator(f: File): (iterator(): TaintedString {.closure.}) =
+ iterator yes(): TaintedString {.closure.} =
+ var line: TaintedString
+ while readLine(f, line):
+ yield line
+ return yes
+
+iterator characters(filename: string): char =
+ for line in lines filename:
+ for letter in line:
+ yield letter
+
+## Construct a DTM from an iterator of rules from a description file
+proc parse*(description: string): description =
+ var noStates = -1
+ var statesSeen = -1
+ var transitions = initTable[input, transition]()
+ var acceptingStates = initSet[state]()
+ var currentState = cast[state]("")
+ var alphabet = false
+ for line in description.splitLines:
+ # If the line is empty
+ if line.len == 0:
+ continue
+ # If we haven't seen any states yet
+ if noStates < 0:
+ noStates = line.splitWhiteSpace()[1].parseInt()
+ statesSeen = 0
+ # If we're partway through seeing states
+ elif noStates > statesSeen:
+ let split = line.splitWhiteSpace()
+ # If it's an accepting state
+ if split.len == 2:
+ acceptingStates.incl(split[0])
+ # If it's the first state mentioned
+ if statesSeen == 0:
+ currentState = (split[0])
+ statesSeen += 1
+ # If we haven't seen the alphabet yet
+ elif not alphabet:
+ alphabet = true
+ # If we're past all that and are at transitions
+ else:
+ let s = line.splitWhiteSpace()
+ let
+ ins = s[0]
+ inl = s[1][0]
+ outs = s[2]
+ outl = s[3][0]
+ outd = toDirection(s[4])
+ let transition = (
+ newState: outs,
+ toWrite: outl,
+ moveDir: outd)
+ transitions[(ins, inl)] = transition
+ # Next line
+ return (
+ currentState: currentState,
+ acceptingStates: acceptingStates,
+ transitions: transitions
+ )
+
+proc makeDTM*(desc: description, input: string): DTM =
+ return DTM(
+ currentState: desc[0],
+ acceptingStates: desc[1],
+ transitions: desc.transitions,
+ tape: tapeOf(input))
+
+proc toFile*(desc: description): string =
+ var states = initSet[state]()
+ var alphabet: set[letter] = {}
+ for k, v in desc.transitions:
+ states.incl k.state
+ states.incl v.newState
+ alphabet.incl k.letter
+ alphabet.incl v.toWrite
+ result = "states " & $states.len & "\n"
+ for v in states:
+ result &= $v & "\n"
+ result &= "alphabet " & $alphabet.card()
+ for v in alphabet:
+ result &= " " & $v
+ result &= "\n"
+ for k, v in desc.transitions:
+ result &= $k.state & " " & $k.letter & " " & $v.newState & " " & $v.toWrite
+ result &= " " & $v.moveDir & "\n"
+
+## Step through DTM emulation until it would halt
+proc test*(tm: DTM, speak: bool): bool =
+ var m: transition
+ var i = 0
+ try:
+ while true:
+ i += 1
+ if speak:
+ echo(tm, " ", tm.currentState, " ", i)
+ m = tm.transitions[(tm.currentState, tm[tm.position])]
+ tm.move(m)
+ except KeyError:
+ return tm.acceptingStates.contains(tm.currentState)
+
+## Does this DTM accept this string as input?
+proc `<<?`*(tm: DTM, input: string): bool =
+ return tm.load(input).test(false)
diff --git a/mt.nim b/mt.nim
new file mode 100644
index 0000000..8055921
--- /dev/null
+++ b/mt.nim
@@ -0,0 +1,41 @@
+import uuid
+import sets
+import os
+import tables
+import strutils
+
+import lib
+
+proc accept(
+ this: var ttable,
+ initialState: state,
+ input: string,
+ u: string
+): state {.discardable.} =
+ var cs = initialState
+ for c in input:
+ if not this.hasKey((cs, c)):
+ this[(cs, c)] = (u, '_', Inc)
+ cs = this[(cs, c)].newState
+ return cs
+
+proc esarp(content: string): description =
+ var tt = initTable[input, transition]()
+ var ac = initSet[state]()
+ var i = 0
+ const initialState = "S"
+ for line in content.splitLines:
+ if line.len <= 0: continue
+ let split = line.split(' ')
+ if split[1].parseBool():
+ ac.incl tt.accept(initialState, split[0], $i)
+ i += 1
+ return (initialState, ac, tt)
+
+const tmname {.strdefine.}: string = "addition"
+const desc = esarp(slurp(tmname & ".tmt"))
+
+if paramCount() >= 1:
+ echo makeDTM(desc, paramStr(1)).test(true)
+else:
+ echo desc.toFile()
diff --git a/palgen.sh b/palgen.sh
new file mode 100755
index 0000000..d5daddc
--- /dev/null
+++ b/palgen.sh
@@ -0,0 +1,12 @@
+#!/bin/sh
+
+function rndm {
+ for i in {1..100} ; do
+ echo -n $(($RANDOM % 3 ))
+ done
+}
+
+for i in {1..1000} ; do
+ woa=`rndm`
+ echo "$woa`echo $woa | rev` true"
+done
diff --git a/palindrome.tm b/palindrome.tm
new file mode 100644
index 0000000..692b70d
--- /dev/null
+++ b/palindrome.tm
@@ -0,0 +1,35 @@
+states 8
+A +
+B0
+B1
+B2
+C0
+C1
+C2
+D
+alphabet 3 0 1 2
+A 0 B0 _ R
+A 1 B1 _ R
+A 2 B2 _ R
+B0 0 B0 0 R
+B0 1 B0 1 R
+B0 2 B0 2 R
+B0 _ C0 _ L
+C0 0 D _ L
+C0 _ A _ S
+B1 0 B1 0 R
+B1 1 B1 1 R
+B1 2 B1 2 R
+B1 _ C1 _ L
+C1 1 D _ L
+C1 _ A _ S
+B2 0 B2 0 R
+B2 1 B2 1 R
+B2 2 B2 2 R
+B2 _ C2 _ L
+C2 2 D _ L
+C2 _ A _ S
+D 0 D 0 L
+D 1 D 1 L
+D 2 D 2 L
+D _ A _ R
diff --git a/report.md b/report.md
new file mode 100644
index 0000000..43848f4
--- /dev/null
+++ b/report.md
@@ -0,0 +1,133 @@
+# CS3052 Practical 2 - Turing Machines
+## Report
+
+## Overview
+The task provided for this practical was to implement a Turing machine
+emulator in a llnguage of choice, and design Turing machines to solve
+specific problems given.
+
+The language chosen to implement the emulator was Nim, a high-level systems
+language similar in syntax to Python, but with powerful compile-time
+functionality.
+
+## Running the Emulator
+To run the emulator, Nim must be installed. A script, `get-nim.sh`, is
+provided in the root of the submission. Running it will install Nim in a single
+directory (which can easily be removed when done), and add said directory to
+the `PATH` environment variable, for this session.
+
+The source provided can be compiled in two separate ways: _interpreter_ and
+_crunched_.
+
+### _Interpreter_ Mode
+_Interpreter_ is the recommended method for viewing the emulator's
+features, and is used as so:
+```bash
+nim c tm.nim
+```
+This line produces the executable `tm` as an _interpreter_, used as such:
+```bash
+./tm DESCRIPTION INPUT
+```
+where `DESCRIPTION` is the name of a Turing machine description file (less the
+`.tm` extension) and `INPUT` the string to test in the described TM.
+The emulator will print, for each transition: the tape contents around the
+selected cell; the name of the current state; and the number of iterations
+since initialisation. If the emulation halts, `true` is printed if it halted
+in an accepting state, and `false` is printed otherwise.
+
+### _Crunched_ Mode
+_Crunched_ mode reads in a selected TM description file and creates an
+executable binary file capable of checking input strings for the described TM.
+
+Crunching is done like so:
+```bash
+nim c -d:tmname=DESCRIPTION tm.nim
+```
+Alternatively, a utility script `compile` has been included in the submission.
+The following line crunches a TM description file `woa.tm` and produces
+executable `woa`:
+```bash
+./compile woa
+```
+Using the cruched executable `woa` would be done like so:
+```bash
+./woa INPUT
+```
+Crunched executables only output a `true`/`false`, and are
+designed with testing and long-running emulation in mind.
+
+### Testing
+A bash script `test.sh` is provided. It searches the current working directory
+for files ending in `.tmt`, which it assumes is a list of test input strings
+followed by the expected `true`/`false` output of the TM associated by name.
+Tests that take a long time are assumed to be non-halting, and so are terminated
+prematurely with an assumption that the input is rejected.
+
+More bash scripts are used to generate passing tests for the provided TMs:
+`bingen.sh` and `palgen.sh`. Running these will print 1000 randomly-generated
+validation tests to the console. More tests, such as exceptional contexts, were
+tested manually.
+
+### enihcaM gniruT
+A second program, `mt.nim`, is provided. It can read in the validation tests,
+and create a TM that passes only on the input strings provided as `true` in the
+test files. It can then output the description of this TM (if passed no
+arguments), or run it against an input string. This program takes in the
+validation test file at compile-time, like so:
+```bash
+nim c -d:tmname=VALIDATION mt.nim
+```
+where `VALIDATION` is the name of the validation test file to be crunched, less
+the file extension.
+
+## Emulator Design
+The emulator written in Nim takes any valid TM description file, as specified in
+the project specification, and creates an internal representation of the
+described TM in memory.
+
+Originally, the approach was much more object-oriented, with `State`s having
+their own internal transition-table. This was found to be quite slow,
+and a rearrangement into `string` representations of states proved to speed
+processing dramatically.
+
+Improving on performance still, the emulator was rewritten a second time to
+be able to 'crunch' TM descriptions into the binary itself. This was the
+largest increase to speed - this can be accredited to Nim's incorporation of C
+compilers (in the case of the lab machines, `gcc`).
+
+Given more time, the next step would be to measure this performance change: in
+particular, looking for any changes in time complexity produced by the
+compiler/optimiser.
+
+`mt.nim` was written with the idea of comparing its running time to that of
+`tm.nim`: the thinking was that `mt` would produce the fastest possible
+TM that sees all of the input, and accepts the strings found in the validation
+tests. Given more time, `tm` and `mt` could have their complexities compared
+for a number of languages.
+
+## Complexity
+### Palindrome
+The palindrome checker compares _n_/2 pairs of characters, and in doing so
+walks across the input and back again. However, each comparision reduces the
+length of the input by 2, meaning the number of transitions must be
+approximately (_n_)+(_n_-1)+(_n_-2)+...+1 = _n_(_n_+1)/2. This gives an
+approximate complexity of _n_-squared.
+
+### Binary
+There are a lot of complications that can arise in this algorithm, such as
+differing lengths of numbers, but again this algorithm relies on walking
+across the input and back. It only walks to to first remaining digit of the last
+number (a fraction of _n_ less than 1) and only walks back to the first
+remaining digit of the first number (also less than _n_). This cycle is
+repeated once for every digit that exists in the longer of the first two numbers
+whose length depends on n. The number of required steps then is roughly
+(_an_+_bn_)._cn_, so the complexity of this algorithm approximately is
+_n_-squared.
+
+## Conclusion
+I am disappointed that I got so little done for this practical: I throughly
+enjoy puzzles similar to that of designing Turing machines, and also enjoy
+thinking in the mentality of simple machines. Given more time, I would have
+produced experiments and results, and investigated the optimisations provided
+by compiling through `nim` and `gcc`.
diff --git a/test.sh b/test.sh
new file mode 100755
index 0000000..7e0ab99
--- /dev/null
+++ b/test.sh
@@ -0,0 +1,14 @@
+#!/bin/bash
+function test {
+ diff <(timeout 20s ./$1 $2 || "false") <(echo $3)
+}
+
+for file in *.tmt ; do
+ name=$(echo $file | cut -f 1 -d '.')
+ echo $name
+ ./compile "$name"
+ while read -r line ; do
+ echo $name $line
+ test $name $line
+ done < "$file"
+done
diff --git a/test.tm b/test.tm
new file mode 100644
index 0000000..da79405
--- /dev/null
+++ b/test.tm
@@ -0,0 +1,10 @@
+states 3
+s0
+s1
+s2 +
+alphabet 2 a b
+s0 a s0 a R
+s0 b s1 b R
+s0 _ s2 _ S
+s1 b s1 b R
+s1 _ s2 _ S
diff --git a/tm.nim b/tm.nim
new file mode 100644
index 0000000..26c97f2
--- /dev/null
+++ b/tm.nim
@@ -0,0 +1,18 @@
+import os
+
+import lib
+
+const tmname {.strdefine.}: string = ""
+
+when tmname.len > 0:
+ const tmd = parse(slurp(tmname & ".tm"))
+ if paramCount() >= 1:
+ echo makeDTM(tmd, paramStr(1)).test(false)
+ else:
+ echo "please specify a single string argument"
+else:
+ if paramCount() >= 2:
+ let tmd = parse(readFile(paramStr(1) & ".tm"))
+ echo makeDTM(tmd, paramStr(2)).test(true)
+ else:
+ echo "please specify a description and string input"