Nondeterministic turing machine simulator in 23 lines of JavaScript

Felt like doing some coding last night and since my friends were just trolling me about codegolfing a turing machine simulator(they need it for a term paper), I decided to do just that.

At first I wanted to make it super simple, 10 lines of code max ... and I failed.

What better way to embrace failure than to implement a simulator of nondeterministic turing machines in as little lines of code as possible?

Adding "eps" to the alphabet of course - basically a means for the machine to know when it's gone off either end of the tape and that it can also write nothing to the tape. Both very useful features!

And here's the code in all its glory. You can also view it on github if that's your thing.

// transition format: {from: 'q1', to: 'q2', via: 'A', put: 'B', move: 1/-1}
// spits out whether end state was reached
// basic way to run:  node turing.js machine.json 101 q4
// node turing.js

var _ = require("underscore"),
  states = {};

var delta = function (states, step, end) {
  if (_.keys(step).indexOf(end) >= 0) return true;
  var _step = {},
    foo = _.keys(step).map(function (k) {
      var i = step[k][0],
        t = step[k][1],
        cur = i < 0 || i >= t.length ? states[k]["esp"] : states[k][t[i]];
      if (cur)
        cur.map(function (cur) {
          if (cur.put != "eps") t.splice(i, 1, cur.put);
          _step[cur.to] = [i + cur.move, t];
        });
    });
  return _.size(_step) ? delta(states, _step, end) : false;
};

JSON.parse(require("fs").readFileSync(process.argv[2], "utf-8")).map(function (
  i
) {
  states[i.from] = states[i.from] || {};
  states[i.from][i.via] = states[i.from][i.via] || [];
  states[i.from][i.via].push(i);
});

console.log(
  delta(states, { q0: [0, process.argv[3].split("")] }, process.argv[4])
);

Basically what you're doing is performing a breadth-first-search on a graph, looking for the end state and a pinch of complications with observing contents the tape as well. You should make sure not to accidentally implement a depth-first search since some branches might never terminate.

The above implementation could probably be codegolfed some more, but I don't like codegolfing by just compating lines beyond what is reasonable. I much prefer doing it with languages features and perhaps algorithmic improvements.

One of the biggest hindrances to making this much shorter is that a lot of operations on javascript arrays affect state, but don't return the new object as well. Lost at least three lines because of this!

An approach worth trying would be to perform a reduce on the tree of states and if the start and end state ever overlap, you know to return a truthy value, otherwise you go with something falsy. But I wasn't sure how to go about that.