A turing machine in 133 bytes of javascript

Multiply turing machine

The fact it took me 20 lines of javascript to implement a nondeterministic turing machine simulatorlast week kept me up at night. All weekend. Too much code for something so simple and I kept having this gut feeling implementing a basic version shouldn’t take more than 140 bytes.

Sunday afternoon I sat down for about an hour, collected my thoughts, and started pumping out code with cryptic variable names. It was beautiful, first version was around 250 bytes, then 170, then 156, then bam! 133. Oh yeah baby!

function tm(I,t,e,s,i,c,k) {i=0;while(s!=e){c=t[i];k=(c)?I[s][c]:I[s].B;if(!k)return false;t.splice(i,1,k.w);i+=k.m;s=k.n;}return t;}

I was left with a horribly looking yet simple function. All it needs are some instructions, the initial state of the tape as a list, an end state and a start state. It will return either the final tape state or false if the end state is never reached. ‘B’ is considered a blank state and the tape behaves as infinite in both directions.

If you want a file ready-made to run in node, go to my github.

Here’s a far less interesting but readable version of the same code (324 bytes):

function tm(I,tape,end,state,i,cell,current) {
    i = 0;
    while(state != end) {
        cell = tape[i];
        current = (cell) ? I[state][cell] : I[state].B;
        if(!current)
            return false;
        tape.splice(i, 1, current.w);
        i += current.m;
        state = current.n;
    }
    return tape;
}

For testing I used a simple multiply program that basically turns 111 into 1110111. For any length string of one’s. I decided to be pretty strict about inputs this time because I didn’t have the room to transform anything, so this is what the algorithm’s implementation ends up looking like

{"q0": {"1": {"w": "B", "m": 1, "n": "q1"}},
 "q1": {"1": {"w": "1", "m": 1, "n": "q1"},
        "0": {"w": "0", "m": 1, "n": "q2"},
        "B": {"w": "0", "m": 1, "n": "q2"}},
 "q2": {"1": {"w": "1", "m": 1, "n": "q2"},
        "B": {"w": "1", "m": -1, "n": "q3"}},
 "q3": {"1": {"w": "1", "m": -1, "n": "q3"},
        "0": {"w": "0", "m": -1, "n": "q3"},
        "B": {"w": "1", "m": 1, "n": "q4"}},
 "q4": {"1": {"w": "B", "m": 1, "n": "q1"},
        "0": {"w": "0", "m": 1, "n": "q5"}}}

Solving this little puzzle was heaps of fun and the result is code that I would never ever want to see in production (if you code like that there is a special circle of hell for you) … now I’m just left wondering if there’s a smaller solution in a less verbose language. Can it be made so small I could tweet “Turing Machine: <code>”?

Source: http://swizec.com/blog/a-turing-machine-in-133-bytes-of-javascript/swizec/3069