Skip to content

Instantly share code, notes, and snippets.

@gliese1337
Last active January 5, 2016 09:08
Show Gist options
  • Save gliese1337/423371081a11da152ab7 to your computer and use it in GitHub Desktop.
Save gliese1337/423371081a11da152ab7 to your computer and use it in GitHub Desktop.
Basic Turing Machine simulator in JS
function TM(tape, alphabet, states, start){
var state, transition, symbol,
counter = 0, stateId = start, pos = 0;
while(true){
symbol = tape[pos];
if(typeof symbol === 'undefined'){
symbol = alphabet[0];
tape[pos] = symbol;
}
state = states[stateId];
transition = state?state[symbol]:void 0;
console.log(++counter, stateId+'['+tape.slice(0,pos).join('')+'('+symbol+')'+ tape.slice(pos+1).join('')+']');
debugger;
if(!transition){
return {
accept: !!state.accept,
tape: tape
};
}
(transition.o||[]).forEach(function(op){
if(op.hasOwnProperty('p')){
tape[pos] = op.p
}else if(op.hasOwnProperty('m')){
pos += op.m == "R"? 1:-1;
if(pos < 0){
pos = 0;
tape.unshift(alphabet[0]);
}else if(tape[pos] == void 0){
tape[pos] = alphabet[0];
}
}
});
stateId = transition.s;
}
}
/* Run the 3-state Busy Beaver Machine on an empty tape */
TM([], ['0', '1'], {
A: {
0: {o: [{p: '1'}, {m: "R"}], s: "B"},
1: {o: [{p: '1'}, {m: "L"}], s: "C"}
},
B: {
0: {o: [{p: '1'}, {m: "L"}], s: "A"},
1: {o: [{p: '1'}, {m: "R"}], s: "B"}
},
C: {
0: {o: [{p: '1'}, {m: "L"}], s: "B"},
1: {o: [{p: '1'}], s: "HALT"}
},
HALT: {accept:true}
}, "A");
TM([], [' ', 'e', 'x', '0', '1'], {
b: {
' ': {o: [{p:'e'},{m:"R"},{p:'e'},{m:"R"},{p:'0'},{m:"R"},{m:"R"},{p:'0'},{m:"L"},{m:"L"}], s: "o"}
},
o: {
1: {o: [{m:"R"},{p:'x'},{m:"L"},{m:"L"},{m:"L"}], s: "o"},
0: {o: [], s: "q"}
},
q: {
0: {o: [{m:'R'},{m:'R'}], s: "q"},
1: {o: [{m:'R'},{m:'R'}], s: "q"},
' ': {o: [{p:'1'},{m:"L"}], s: "p"},
},
p: {
x: {o: [{p:' '},{m:"R"}], s: "q"},
e: {o: [{m:'R'}], s: "f"},
' ': {o: [{m:"L"},{m:"L"}], s: "p"}
},
f: {
0: {o: [{m:'R'},{m:'R'}], s: "f"},
1: {o: [{m:'R'},{m:'R'}], s: "f"},
x: {o: [{m:'R'},{m:'R'}], s: "f"},
e: {o: [{m:'R'},{m:'R'}], s: "f"},
' ': {o: [{p:'0'},{m:"L"},{m:"L"}], s: "o"}
}
}, "b");
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment