Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A turing machine in 79! bytes of javascript
// added some curly braces for readability
function(
a, // {Object} program @see test.html for details
b, // {Number[]} tape
c, // {String} end state
d, // {String} start state
e // [{Number} = 0] caret position
) {
while(
d < c // while ! eof program
) {
/* 'e |= 0' - if e is undefined - reset to 0 else leave as is */
with (/* q = */a[d][b[e |= 0] || "B"]) { // push current program statement aka "q" to the top of current scope
b[e] = w, // chenge symbol under caret, w is the item of "q"
e += m, // move caret by ..., m is the item of "q"
d = n; // jump to next state, n is the item of "q"
}
}
return b
}
function(a,b,c,d,e){while(d<c)with(a[d][b[e|=0]||"B"])b[e]=w,e+=m,d=n;return b}
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
Version 2, December 2004
Copyright (C) 2011 YOUR_NAME_HERE <YOUR_URL_HERE>
Everyone is permitted to copy and distribute verbatim or modified
copies of this license document, and changing it is allowed as long
as the name is changed.
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
0. You just DO WHAT THE FUCK YOU WANT TO.
{
"name": "turing_machine",
"description": "A turing machine implementation",
"keywords": [
"turing_machine"
]
}
<!DOCTYPE html>
<title>Foo</title>
<div>Expected value: <b>1,1,1,0,1,1,1</b></div>
<div>Actual value: <b id="ret"></b></div>
<script>
var tm = function(a,b,c,d,e){while(d<c)with(a[d][b[e|=0]||"B"])b[e]=w,e+=m,d=n;return b};
var program = {"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"}}};
var tape = [1,1,1];
document.getElementById("ret").innerHTML = tm(program, tape, "q5", "q0", 0);
</script>
@azproduction

This comment has been minimized.

Copy link
Owner Author

@azproduction azproduction commented Nov 28, 2011

@Kambfhase

This comment has been minimized.

Copy link

@Kambfhase Kambfhase commented Nov 28, 2011

Totally cool. you can get rid of the g though:
function(a,b,c,d,e,f){for(e=0;d<c;b[e]=(f=(f=a[d])[b[e]]||f.B).w,e+=f.m,d=f.n);return b}

even shorter:
function(a,b,c,d,e,f){for(e=0;d<c;f=a[d][b[e]||"B"],b[e]=f.w,e+=f.m,d=f.n);return b}

even shorterer:
function(a,b,c,d,e,f){for(e=0;d<c;b[e]=f.w,e+=f.m,d=f.n)f=a[d][b[e]||"B"];return b}

I'd prefer using != instead of < because it doesn't break if you swap q0 and q5.

@subzey

This comment has been minimized.

Copy link

@subzey subzey commented Nov 28, 2011

Can't we use dirty with?

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}

@Kambfhase

This comment has been minimized.

Copy link

@Kambfhase Kambfhase commented Nov 28, 2011

Hah, with is nasty. I like that.

@tsaniel

This comment has been minimized.

Copy link

@tsaniel tsaniel commented Nov 30, 2011

I just don't understand why the start state is q5 ... isn't it q0?

@Kambfhase

This comment has been minimized.

Copy link

@Kambfhase Kambfhase commented Nov 30, 2011

Oh, yeah. The comments in the annotated.js are wrong. Good finding!

@azproduction

This comment has been minimized.

Copy link
Owner Author

@azproduction azproduction commented Dec 1, 2011

Just updated gist. Guess it's final version :) Thx for help!

@tsaniel

This comment has been minimized.

Copy link

@tsaniel tsaniel commented Dec 1, 2011

function(a,b,c,d,e){for(;d<c;)with(a[d][b[e|=0]||"B"])b[e]=w,e+=m,d=n;return b}

The above uses the same bytes and allows we to decide the starting position(default 0).

@bjuergens

This comment has been minimized.

Copy link

@bjuergens bjuergens commented Jun 28, 2016

when you change the final state in a to something falsy (e.g. "") you can drop c and save 4 symbols:
so
function(a,b,d,e){while(d)with(a[d][b[e|=0]||"B"])b[e]=w,e+=m,d=n;return b} becomes:
function(a,b,c,d,e){while(d<c)with(a[d][b[e|=0]||"B"])b[e]=w,e+=m,d=n;return b}

note: as of 2016 this still seems to be the shortest JS.TM out there. Good Job!

@zsarge

This comment has been minimized.

Copy link

@zsarge zsarge commented Oct 4, 2020

Not to revive a thread from 2016, but the introduction of arrow functions would help here.

(Without Falsy A)

(a,b,c,d,e)=>{while(d<c)with(a[d][b[e|=0]||"B"])b[e]=w,e+=m,d=n;return b}

73 Chars

jsfiddle modified from the original author

@brixdan

This comment has been minimized.

Copy link

@brixdan brixdan commented Mar 1, 2021

Might well happen (b[e|=0]) = 0, then ||"B" will cause absolutely wrong course of actions. It's a pure bug. Sorry.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment