Swizec Teller - a geek with a hatswizec.com

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

    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}="" <="" pre="">
    <h6 class="zemanta-related-title" style="font-size: 1em;">Related articles</h6>
    <ul class="zemanta-article-ul">
    <li class="zemanta-article-ul-li"><a href="https://swizec.com/blog/nondeterministic-turing-machine-simulator-in-23-lines-of-javascript/swizec/3047">Nondeterministic turing machine simulator in 23 lines of JavaScript</a> (swizec.com)</li>
    <li class="zemanta-article-ul-li"><a href="http://stackoverflow.com/questions/7366513/is-turing-machine-is-a-real-device-or-an-imaginary-concept">Is turing machine is a real device or an imaginary concept?</a> (stackoverflow.com)</li>
    <li class="zemanta-article-ul-li"><a href="http://shebang.ws/turing-completeness-bullshit.html">Turing completeness bullshit</a> (shebang.ws)</li>
    <li class="zemanta-article-ul-li"><a href="http://work.damow.net/random/bf-turing/">The Brainfu*k Turing Machine (Javascript)</a> (work.damow.net)</li>
    </ul>
    <div class="zemanta-pixie" style="margin-top: 10px; height: 15px;"><a class="zemanta-pixie-a" title="Enhanced by Zemanta" href="http://www.zemanta.com/"><img class="zemanta-pixie-img" style="border: none; float: right;" src="http://img.zemanta.com/zemified_e.png?x-id=01ad0c53-59aa-4646-b7dd-ad6f892a820f" alt="Enhanced by Zemanta"></a></div></c;)with(a[d][b[e]||"b"])b[e]=w,e+=m,d=n;return>

    Did you enjoy this article?

    Published on November 28th, 2011 in Languages, Programming, Turing machine, Uncategorized,

    Learned something new?
    Read more Software Engineering Lessons from Production

    I write articles with real insight into the career and skills of a modern software engineer. "Raw and honest from the heart!" as one reader described them. Fueled by lessons learned over 20 years of building production code for side-projects, small businesses, and hyper growth startups. Both successful and not.

    Subscribe below 👇

    Software Engineering Lessons from Production

    Join Swizec's Newsletter and get insightful emails 💌 on mindsets, tactics, and technical skills for your career. Real lessons from building production software. No bullshit.

    "Man, love your simple writing! Yours is the only newsletter I open and only blog that I give a fuck to read & scroll till the end. And wow always take away lessons with me. Inspiring! And very relatable. 👌"

    ~ Ashish Kumar

    Join 15,883+ engineers learning lessons from my "raw and honest from the heart" emails.

    ⭐️⭐️⭐️⭐️✨
    4.5 stars average rating

    Have a burning question that you think I can answer? Hit me up on twitter and I'll do my best.

    Who am I and who do I help? I'm Swizec Teller and I turn coders into engineers with "Raw and honest from the heart!" writing. No bullshit. Real insights into the career and skills of a modern software engineer.

    Want to become a true senior engineer? Take ownership, have autonomy, and be a force multiplier on your team. The Senior Engineer Mindset ebook can help 👉 swizec.com/senior-mindset. These are the shifts in mindset that unlocked my career.

    Curious about Serverless and the modern backend? Check out Serverless Handbook, for frontend engineers 👉 ServerlessHandbook.dev

    Want to Stop copy pasting D3 examples and create data visualizations of your own? Learn how to build scalable dataviz React components your whole team can understand with React for Data Visualization

    Want to get my best emails on JavaScript, React, Serverless, Fullstack Web, or Indie Hacking? Check out swizec.com/collections

    Want to brush up on modern JavaScript syntax? Check out my interactive cheatsheet: es6cheatsheet.com

    Did someone amazing share this letter with you? Wonderful! You can sign up for my weekly letters for software engineers on their path to greatness, here: swizec.com/blog

    Want to brush up on your modern JavaScript syntax? Check out my interactive cheatsheet: es6cheatsheet.com

    By the way, just in case no one has told you it yet today: I love and appreciate you for who you are ❤️

    Created by Swizec with ❤️