Multiply turing machine

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>”?

Food for thought.

PS: the shortest solution by subzey in 79 bytes

function(a,b,c,d,e){for(e=0;d<c;)with(a[d][b[e]||"B"])b[e]=w,e+=m,d=n;return b}
Enhanced by Zemanta
  • http://www.invoicefox.com J M

    why do you pass in i, cell, current if you (re)set them in func before anything? (I guess you wanted to use recursion and you left these in by mistake)

  • http://www.invoicefox.com J M

    Again me… I was able to run it in chrome console ant it works with different inputs! nice :)

    Btw .. looking at code wouldn’t recursive solution be even shorter?

  • Alistair

    I assume because otherwise i, cell and current would be globally scoped.
    Having them as undefined parameters is cheaper in terms of characters than defining each with var inside the function.

  • http://swizec.com Swizec

    Precisely. It’s cheaper to pass undefined variables as parameters than using var and even for a codegolf globally scoped variables just aren’t nice.

  • http://swizec.com Swizec

    Not really because there’s an extra return.

  • Anonymous

    You could minify it further by removing unnecessary spaces, unnecessary semi-colons, the parenthesis on the ternary if condition and renaming the function to a single character.
    Saving: 6 characters [127 long]

    Forcing the caller to pass in 0 for the i parameter would save 4 more characters at which point it’s tweetable as:
    “Turing Machine: function tm(I,t,e,s,i,c,k){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}”

    Feels a bit like flogging a dead horse.

  • http://swizec.com Swizec

    Agreed about those 6 characters, but forcing the caller to pass 0 is going a bit far. That is very much an implementation detail and I don’t think it should be up to the caller to tell where to start looking at the tape.

  • http://twitter.com/zidarsk8 Miha Zidar

    One liner; in the old days it would be 80 chars long, but lately people seem to go towards 100 chars in a line. Your code is still slightly longer, but one tweeter (140) still sounds nice.

  • Dan Bentley

    function t(d,c,e,a,b){b=b||0;if(a==e)return c;a=c[b]?d[a][c[b]]:d[a].B;c.splice(b,1,a.w);return a?t(d,c,e,a.n,b+a.m):!1};
    Uncompiled:

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

  • http://twitter.com/_sebastienp Sebastien P.

    Does this work for you ?

    
    function tm(I, tape, end, state, i, current) {	for (		i = 0;		state != end;		tape.splice(i, 1, current.w),		i += current.m,		state = current.n	)		if (!(current = I[state][tape[i] || "B"])) return;	return tape}
    

    109 bytes : function tm(a,b,c,d,e,f){for(e=0;d!=c;b.splice(e,1,f.w),e+=f.m,d=f.n)if(!(f=a[d][b[e]||"B"]))return;return b}

  • http://www.invoicefox.com J M

    ahhh, haven’t thought of that at all .. gotta change all my codebase now :)

  • http://twitter.com/robinhouston Robin Houston

    “return false” can be shortened to “return!1”, saving four characters.

    That crosses the Tweet Barrier:

    Turing machine: 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!1;t.splice(i,1,k.w);i+=k.m;s=k.n}return t}

  • http://twitter.com/robinhouston Robin Houston

    Down to 114 chars just by reorganising a couple of expressions and eliminating the redundant variable ‘c’:

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

  • http://twitter.com/azproduction Mikhail Davydov

    function(a,b,c,d,e,f,g){for(e=0;d

  • http://twitter.com/azproduction Mikhail Davydov

    99b function(a,b,c,d,e,f,g){for(e=0;d<c;b.splice(e,1,(g=(f=a[d])[b[e]]||f.B).w),e+=g.m,d=g.n);return b}

  • Alejandro Varela

    really nice work man!

  • http://victorypoints.com Pete Mancini

    That is really interesting. Shouldn’t the final true measure be the resulting bytecode though?

  • Alan Mathison

    The whole concept is ridiculous
    function t(s){eval(s);}

    nuff said.

  • http://id.zvxrl.co.uk/ Michael

    This inspired me to write an interpreter for the Lambda calculus in ML. Sadly so far it only fits in 261 chars (clearly could get this down a bit)…

    datatype E=l of string*E|a of E*E|s of string;datatype R=v of string*E*R|N;fun lu (v(n1,e,r)) (s(n2))=if n1=n2 then e else (lu r (s(n2)))|lu (N) n2=n2;fun ev r (s(k))=lu r (s(k))|ev r (l(k,e))=(l(k,(ev (v(k,s(k),r)) e)))|ev r (a(l(k,e1),e2))=ev (v(k,e2,r)) e1;

    More verbose version is at http://pastebin.devhat.net/14

    Supposing it works 100% as expected, I find it pretty neat that every function computable using your Turing machine is computable with my Lambda interpreter! :) However, that’s unlikely as I haven’t tried anything difficult like the Y combinator as writing out ASTs is a pain and a parser would easily add another 200-500 chars.

  • http://swizec.com Swizec

    Hey that’s really awesome! Too bad it didn’t work out :)

    Perhaps that’s a good indicator why turing machines “won” out against lambda calculus as the default computation model, they are very very simple.

  • http://twitter.com/edulan edulan

     Recursive approach:

    function M(I,q,f,t,i){if(q!=f){with(I[q][t[i]||’B']){t[i]=w;M(I,n,f,t,i+m);}}}

    You don’t actually need to return anything, because you’re modifying tape parameter (as its passed by reference)

    This approach takes only 78 characters.

  • Sandycd354

    In the 70′s, when 2k RAM and 2k ROM were all you could afford…  It was cute.  Now, though, we can do things much better. nism?

  • Pingback: Very small Turing machines | cartesian product

  • http://swizec.com Swizec

    But then how would you know the machine has stopped? The halting problem is difficult enough as it is even when the machine tells you if it stopped in a non-end state …

  • http://swizec.com Swizec

    Some things aren’t meant to be useful, they’re just supposed to be fun and/or interesting.

  • http://twitter.com/edulan edulan

    You’re right, I forgot those cases when the machine does not accept the input word.

    Recursive approach is considerably longer than iterative one because of return as you say, but it’s another approach to consider.

  • Pingback: The craziest Javascript implementations on the web - Yeblon

  • jack33w

    This is why I never studied computer science.

  • http://swizec.com Swizec

    I don’t get it, why? This stuff is fun!