QuantumGhost
8/9/2015 - 4:51 PM

## A tweetable turing machine

A tweetable turing machine

``````/**
* Here's a turing machine that fits into a tweet with an example program.
* Original tweet: https://twitter.com/mrrrgn/status/630419814666780673
* Gif: http://i.imgur.com/4t31zA2.gif
* Turing machines: https://www.youtube.com/watch?v=dNRDvLACg5Q
*
* Think this is neat? Consider following me for more computer silliness:
* twitter.com/mrrrgn or rss my blog linuxpoetry.com
**/

// Tweetable Version
t=(c,k)=>{for(i=0, s='q0';;){p=c[s+k[i]||''];if(p[0]=='t'||p[0]=='f')return p[0];k[i]=p[0];i=p[1]=='R'?i+1:i-1;s=p[2]+p[3]}}

//Non-tweetable Version
var t = (code, input) => {
var i = 0; // tape position
var s = 'q0' // machine state, always begins in q0
while (true) {
var p = code[s+input[i]||'']; // our current instruction is the machine state + the current tape value
if(p[0]=='t'){return true}; if(p[0]=='f'){return false}; // check for halt states
input[i] = p[0] // always write something (this simplifies our eval logic)
if(p[1]=='R'){i++}else{i--};// move the tape left or right
s=p[2]+p[3]; // change to the appropriate state
}
};

// EXAMPLE PROGRAM: Test the evenness of a number
// instruction format: state (qn) + input value => write: x + move tape {R,L} + new state (qn)
var evenTest = {
q00: '0Rq0', // in state zero, if you read a zero, write a zero and move right one: remain in state zero
q01: '1Rq0', // in state zero, if you read a one, write a one, and move right one: remain in state zero
q0_: '_Lq1', // in state zero, if you read a blank, write a blank, move left one: change to state q1
q10: 't', // in state one (end of number), if you read a zero return true -> the number is even
q11: 'f' // in state one (end of number), if you read a one return false -> the number is odd
};

console.log(t(evenTest, [1, 0, '_'])); // should return true (the number is even)
console.log(t(evenTest, [1, 1, '_'])); // should return false (now the number is odd)``````