Skip to content
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="http://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?
Want to become a high value JavaScript expert?

Here's how it works 👇

Leave your email and I'll send you an Interactive Modern JavaScript Cheatsheet 📖right away. After that you'll get thoughtfully written emails every week about React, JavaScript, and your career. Lessons learned over my 20 years in the industry working with companies ranging from tiny startups to Fortune5 behemoths.

Start with an interactive cheatsheet 📖

Then get thoughtful letters 💌 on mindsets, tactics, and technical skills for your career.

"Man, love your simple writing! Yours is the only email I open from marketers 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 over 10,000 engineers just like you already improving their JS careers with my letters, workshops, courses, and talks. ✌️

Have a burning question that you think I can answer? I don't have all of the answers, but I have some! Hit me up on twitter or book a 30min ama for in-depth help.

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

Curious about Serverless and the modern backend? Check out Serverless Handbook, modern backend for the frontend engineer.

Ready to learn how it all fits together and build a modern webapp from scratch? Learn how to launch a webapp and make your first 💰 on the side with ServerlessReact.Dev

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 ❤️