Skip to content

Instantly share code, notes, and snippets.

@danielmewes
Created August 23, 2016 16:44
Show Gist options
  • Save danielmewes/69a1833cd11f66e5a611c5b20e96e42b to your computer and use it in GitHub Desktop.
Save danielmewes/69a1833cd11f66e5a611c5b20e96e42b to your computer and use it in GitHub Desktop.
Turing machine in ReQL example
var machine = {
blank_symbol: 0,
transitions: [
{
from_state: "A",
read_symbol: 0,
to_state: "A",
write_symbol: 0,
move_head: "R"
},
{
from_state: "A",
read_symbol: 1,
to_state: "A",
write_symbol: 0,
move_head: "R"
},
{
from_state: "A",
read_symbol: 2,
to_state: "B",
write_symbol: 2,
move_head: "R"
}
],
initial_state: "A",
final_states: ["B"]
};
var input = [1,0,1,1,2,1,2,2,0,1];
var initialState = { tape: input, state: machine.initial_state, head_position: 0 };
// Reads the current symbol from the tape.
var readSymbol = function(state) {
return state('tape').nth(state('head_position')).default(machine.blank_symbol);
};
// Tests whether the given transition applies to the current state.
var checkRule = function(state, rule) {
return state('state').eq(rule('from_state')).and(readSymbol(state).eq(rule('read_symbol')));
};
// Selects an applicable transition.
var selectRule = function(state) {
return r.expr(machine.transitions)
.concatMap(function(rule) {
return r.branch(checkRule(state, rule), [rule], []);
})
.nth(0)
.default(r.error("No applicable rule. Input rejected."));
};
// Writes `newSymbol` to the current head position and returns the new tape.
var writeTape = function(state, newSymbol) {
// Note that head_position is never larger than the current tape length
var mustAppend = state('tape').count().eq(state('head_position'));
return r.branch(
mustAppend,
state('tape').append(newSymbol),
state('tape').changeAt(state('head_position'), newSymbol));
};
// Applies the given transition to the given state, and returns a new state.
var applyRule = function(state, rule) {
return {
tape: writeTape(state, rule('write_symbol')),
state: rule('to_state'),
head_position: state('head_position').add(r.branch(rule('move_head').eq("L"), -1, 1))
};
};
r.range()
.fold(
initialState,
function(state, _ignored) {
// Select a transition and compute the new state by applying it.
var selectedRule = selectRule(state);
return applyRule(state, selectedRule);
},
{
emit: function(_ignored, _ignored2, state) {
// Check if we have reached a final state. If yes, accept the input by emitting the current tape.
return r.branch(
r.expr(machine.final_states).contains(state('state')),
[state('tape')],
[]);
}
}
)
.limit(1) // Stop as soon as we get to an accepted state
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment