diff options
author | Tom Harley | 2018-05-13 23:13:04 +0100 |
---|---|---|
committer | Tom Harley | 2018-05-13 23:13:04 +0100 |
commit | 36872f5c2e65ffe1570e0f1758833e0253dee9ed (patch) | |
tree | 4d6ef61df030fbf86f148d9a4f4c67f05fba2ec5 | |
download | machines-36872f5c2e65ffe1570e0f1758833e0253dee9ed.tar.gz machines-36872f5c2e65ffe1570e0f1758833e0253dee9ed.zip |
Initial commit
-rw-r--r-- | addition.tm | 65 | ||||
-rwxr-xr-x | bingen.sh | 12 | ||||
-rwxr-xr-x | compile | 2 | ||||
-rwxr-xr-x | get-nim.sh | 5 | ||||
-rw-r--r-- | lib.nim | 222 | ||||
-rw-r--r-- | mt.nim | 41 | ||||
-rwxr-xr-x | palgen.sh | 12 | ||||
-rw-r--r-- | palindrome.tm | 35 | ||||
-rw-r--r-- | report.md | 133 | ||||
-rwxr-xr-x | test.sh | 14 | ||||
-rw-r--r-- | test.tm | 10 | ||||
-rw-r--r-- | tm.nim | 18 |
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 @@ -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" @@ -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) @@ -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`. @@ -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 @@ -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 @@ -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" |