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/">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>
Continue reading about A turing machine in 133 bytes of javascript
Semantically similar articles hand-picked by GPT-4
- Fun javascript feature
- Nondeterministic turing machine simulator in 23 lines of JavaScript
- When your brain is breaking, try XState
- JavaScript's native map reduce and filter are wrong
- Strangest line of python you have ever seen
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. 👌"
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
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 ❤️