version 1.3
Original idea by http://swizec.com/blog/a-turing-machine-in-133-bytes-of-javascript/swizec/3069#
Demo http://jsfiddle.net/WcjZ5/6/
Thx @subzey, @Kambfhase, @tsaniel for help!
-
-
Save azproduction/1400509 to your computer and use it in GitHub Desktop.
A turing machine in 79! bytes of javascript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 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 | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "name": "turing_machine", | |
| "description": "A turing machine implementation", | |
| "keywords": [ | |
| "turing_machine" | |
| ] | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!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> |
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.
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}
Hah, with is nasty. I like that.
I just don't understand why the start state is q5 ... isn't it q0?
Oh, yeah. The comments in the annotated.js are wrong. Good finding!
Just updated gist. Guess it's final version :) Thx for help!
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).
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!
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
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
http://jsfiddle.net/WcjZ5/6/