Created
April 7, 2018 09:24
-
-
Save JustinSDK/12bf9696cf5dc557d339db7e2ce12d54 to your computer and use it in GitHub Desktop.
Turing Machine
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function println(v) { | |
console.log(v.toString()); | |
} | |
class List { | |
constructor(array) { | |
this.array = array; | |
} | |
get first() { | |
return this.array[0]; | |
} | |
get tail() { | |
return new List(this.array.slice(1)); | |
} | |
get init() { | |
return new List(this.array.slice(0, -1)); | |
} | |
get last() { | |
return this.array[this.array.length - 1] ; | |
} | |
prepend(elem) { | |
return new List([elem].concat(this.array)); | |
} | |
append(elem) { | |
return new List(this.array.concat([elem])); | |
} | |
toString() { | |
return this.array.join(' '); | |
} | |
} | |
class Head { | |
constructor(left, current, right, defaultValue) { | |
this.left = left; | |
this.current = current; | |
this.right = right; | |
this.defaultValue = defaultValue; | |
} | |
moveLeft() { | |
return new Head( | |
this.left.init, | |
this.left.last === undefined ? this.defaultValue : this.left.last, | |
this.right.prepend(this.current), | |
this.defaultValue | |
); | |
} | |
moveRight() { | |
return new Head( | |
this.left.append(this.current), | |
this.right.first === undefined ? this.defaultValue : this.right.first, | |
this.right.tail, | |
this.defaultValue | |
); | |
} | |
write(data) { | |
return new Head(this.left, data, this.right, this.defaultValue); | |
} | |
toString() { | |
let l = this.left.toString(); | |
let r = this.right.toString(); | |
return `[${l}](${this.current})[${r}]`; | |
} | |
} | |
class Context { | |
constructor(state, head) { | |
this.state = state; | |
this.head = head; | |
} | |
isAcceptable(acceptables) { | |
return acceptables.includes(this.state); | |
} | |
get data() { | |
let larr = this.head.left.array; | |
let carr = [this.head.current]; | |
let rarr = this.head.right.array; | |
return larr.concat(carr).concat(rarr); | |
} | |
} | |
const LEFT = Symbol('move head left'); | |
const RIGHT = Symbol('move head right'); | |
class Rule { | |
constructor({state, data, writeData, headDir, nextState}) { | |
this.state = state; | |
this.data = data; | |
this.writeData = writeData; | |
this.headDir = headDir; | |
this.nextState = nextState; | |
} | |
isApplicableTo(context) { | |
return this.state === context.state && | |
this.data === context.head.current; | |
} | |
next_context(context) { | |
head = context.head.write(this.writeData); | |
switch(this.headDir) { | |
case LEFT: | |
return new Context(this.nextState, head.moveLeft()); | |
case RIGHT: | |
return new Context(this.nextState, head.moveRight()); | |
} | |
} | |
} | |
class Manual { | |
constructor(rules) { | |
this.rules = rules; | |
} | |
next_context(context) { | |
return this.rules | |
.find(rule => rule.isApplicableTo(context)) | |
.next_context(context); | |
} | |
} | |
class Machine { | |
constructor(manual, context, acceptables) { | |
this.manual = manual; | |
this.context = context; | |
this.acceptables = acceptables; | |
} | |
execute() { | |
return this.runUntilHalt(this.context).data; | |
} | |
runUntilHalt(context) { | |
return context.isAcceptable(this.acceptables) ? | |
context : | |
this.runUntilHalt(this.manual.next_context(context)); | |
} | |
} | |
let manual = new Manual([ | |
new Rule({ | |
state : 1, | |
data : 0, | |
writeData : 1, | |
headDir : RIGHT, | |
nextState : 2 | |
}), | |
new Rule({ | |
state : 1, | |
data : 1, | |
writeData : 0, | |
headDir : LEFT, | |
nextState : 1 | |
}), | |
new Rule({ | |
state : 1, | |
data : '\0', | |
writeData : 1, | |
headDir : RIGHT, | |
nextState : 2 | |
}), | |
new Rule({ | |
state : 2, | |
data : 0, | |
writeData : 0, | |
headDir : RIGHT, | |
nextState : 2 | |
}), | |
new Rule({ | |
state : 2, | |
data : 1, | |
writeData : 1, | |
headDir : RIGHT, | |
nextState : 2 | |
}), | |
new Rule({ | |
state : 2, | |
data : '\0', | |
writeData : '\0', | |
headDir : LEFT, | |
nextState : 3 | |
}) | |
]); | |
let head = new Head(new List([1, 0, 1]), 1, new List([]), '\0'); | |
let context = new Context(1, head); | |
let machine = new Machine(manual, context, [3]); | |
let r = machine.execute(); | |
console.log(r); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment