Skip to content

Instantly share code, notes, and snippets.

@plmrry
Created March 15, 2016 20:24
Show Gist options
  • Save plmrry/99dd54144e37de771b11 to your computer and use it in GitHub Desktop.
Save plmrry/99dd54144e37de771b11 to your computer and use it in GitHub Desktop.
Turing Machine Painting

On the right is an interactive force-directed representation of a Turing Machine. The turing machine reads a tape and writes decimal values such as "0.6." At each step, a copy of the tape is made, where each value on the tape is mapped to a hue angle in HSL space.

<html>
<head>
<link href='http://fonts.googleapis.com/css?family=Lato:100,400' rel='stylesheet' type='text/css'>
<style>
body {
width: 100%;
height: 100%;
margin: 0;
}
main {
display: flex;
flex-direction: row;
width: 80%;
height: 90%;
margin: 0 auto;
padding-top: 10px;
padding-bottom: 10px;
}
svg {
width: 100%;
height: 100%;
}
#tape {
flex: 1 1 0;
/*border: 1px solid black;*/
}
#turing {
flex: 4;
/*border: 1px solid black;*/
}
.square rect {
/*fill: none;*/
stroke: #ddd;
}
.square text {
fill: #999;
text-anchor: middle;
font-family: 'Lato', sans-serif;
font-weight: 100;
font-size: 4em;
}
.node circle {
fill: #ddf;
/*stroke: black;
stroke-opacity: 0;*/
}
.node text, .link text {
fill: #333;
text-anchor: middle;
font-family: "Helvetica", sans-serif;
font-weight: 100;
}
.node text {
font-size: 0.4em;
}
.link text {
font-size: 0.5em;
}
.link path {
fill: none;
/*stroke: #999;*/
}
#end path {
/*fill: #ccc;*/
}
</style>
</head>
<body>
<main>
<svg id="tape">
</svg>
<svg id="turing">
</svg>
</main>
<script src="//cdnjs.cloudflare.com/ajax/libs/d3/3.5.3/d3.min.js"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js"></script>
<script>
var _tape_length = 30;
var states = d3.range(7).map(function(d, i) {
var obj = { id: i };
if (obj.id === 1) obj.initial = true;
if (obj.id === 3) obj.accept = true;
return obj;
});
var tape = d3.range(_tape_length).map(function(d, i) {
var obj = { position: i, symbol: "_" };
if (i === 0) obj.symbol = 0;
if (i === _tape_length - 1) obj.symbol = 1;
return obj;
});
var transitions = [
{ source: getState(0), target: getState(1) },
{ source: getState(1), target: getState(4), inputs: [0, "_"], write: 0.9, move: "R" },
{ source: getState(4), target: getState(1), inputs: [0, "_"], write: 0.75, move: "R" },
{ source: getState(4), target: getState(2), inputs: [1], write: 0.6, move: "L" },
{ source: getState(1), target: getState(2), inputs: [1], write: 0.6, move: "L" },
{ source: getState(2), target: getState(5), inputs: [0.9, 0.75, 0.4, 0.6], write: 0.6, move: "L" },
// { source: getState(2), target: getState(3), inputs: [0], move: "R"},
{ source: getState(5), target: getState(6), inputs: [0.9, 0.75, 0.6], write: 0.4, move: "R"},
{ source: getState(6), target: getState(2), inputs: [0.9, 0.75], write: 0.3, move: "L" },
{ source: getState(6), target: getState(2), inputs: [0.4, 0.6], write: 0.1, move: "L" },
{ source: getState(5), target: getState(3), inputs: ["_"], move: "R"},
{ source: getState(6), target: getState(3), inputs: ["_"], move: "R"},
{ source: getState(2), target: getState(3), inputs: ["_"], move: "R"},
]
var head = tape[0];
var width = height = 300;
var svg = d3.select("#turing")
.attr({
viewBox: "0 0 " + width + " " + height
});
svg.append("svg:defs").selectAll("marker")
.data(["end"])
.enter().append("svg:marker")
.attr("id", String)
.attr("viewBox", "0 -5 10 10")
.attr("refX", 20)
.attr("refY", 0)
.attr("markerWidth", 6)
.attr("markerHeight", 6)
.attr("orient", "auto")
.append("svg:path")
.attr("d", "M0,-5L10,0L0,5");
var line = d3.svg.line()
.x(function(d) { return d.x; })
.y(function(d) { return d.y; })
.interpolate("basis");
var links = [];
var paths = [];
var nodes = [].concat(states);
transitions.forEach(function(link) {
var s = link.source,
t = link.target,
i1 = {},
i2 = {};
nodes.push(i1, i2);
links.push({source: s, target: i1}, {source: i1, target: i2}, {source: i2, target: t});
paths.push({ transition: link, path: [s, i1, i2, t] });
});
var force = d3.layout.force()
.size([width, height])
.nodes(nodes)
.links(links)
.on("tick", tick)
.charge(-50)
.start();
var links = svg.append("g").classed("links", true)
.selectAll(".link").data(paths);
links.enter().append("g").classed("link", true)
.call(function(g) {
g.each(function(d) {
d._id = "link-" + d.path[0].id + "-" + d.path[3].id;
})
g.append("path")
.attr("id", function(d) { return d._id; })
.attr("marker-end", "url(#end)")
.style("stroke", "#ddd")
g.append("text")
.style("fill", "#ddd")
.text(function(d) {
var t = d.transition;
var i = (t.inputs) ? t.inputs.join(",") + " -> " : "";
var write = (t.write) ? t.write + ", " : "";
var move = t.move || "";
return i + write + move;
})
})
var nodes = svg.append("g").classed("nodes", true)
.selectAll(".node").data(states);
nodes.enter().append("g").classed("node", true)
.each(function(d, i) {
if (i === 0) d3.select(this).remove();
})
.call(force.drag)
.call(function(g) {
g.append("circle")
.attr({
r: 7
})
.style({
stroke: "black", "stroke-opacity": 0
})
g.append("text")
.text(function(d) { return "q" + d.id; })
.attr({
y: 3
})
})
function tick() {
links.select("path").attr("d", function(d) {
return line(d.path);
});
links.select("text")
.attr("x", function(d) {
return (d.path[1].x + d.path[2].x) / 2;
})
.attr("y", function(d) {
return (d.path[1].y + d.path[2].y) / 2;
})
nodes.call(setTransform);
}
function setTransform(selection) {
selection.attr("transform", function(d) { return translate(d.x, d.y); })
}
function translate(x, y) {
return "translate(" + x + "," + y + ")";
}
var initial_state = _.find(states, function(d) { return d.initial === true; });
var current_state = initial_state;
var tape_svg = d3.select("#tape")
.attr("viewBox", "0 0 1000 4000");
var square_size = 1000 / _tape_length;
var x = d3.scale.ordinal();
var y = d3.scale.ordinal();
var tapes = [];
tapes.push(tape);
function run() {
var _tape = tape.sort(function(a, b) { return d3.ascending(a.position, b.position) });
var tape_length = _tape.length;
x.domain(d3.range(tape_length))
.rangeBands([0, tape_length * square_size]);
y.domain(d3.range(tapes.length))
.rangeBands([0, tapes.length * square_size]);
var _tapes = tape_svg.selectAll(".tape-container").data(tapes);
_tapes.enter().append("g").classed("tape-container", true)
.attr("transform", function(d,i) { return translate(0, y(i)); })
.call(function(g) {
var squares = g.selectAll(".square").data(function(d) { return d; });
squares.enter().append("g").classed("square", true)
.attr("transform", function(d) { return translate(x(d.position), 0); })
.call(function(g) {
g.append("rect")
.attr({
width: x.rangeBand(), height: x.rangeBand()
})
.style({
fill: function(d) {
var val = parseFloat(d.symbol);
if (val > 0) {
var color = d3.hsl(val * 360 + 200 % 360, 1, 0.7).toString();
return color;
} else {
return "white";
}
}
})
g.append("text")
.attr({
x: x.rangeBand()/2, y: x.rangeBand()/2, dy: "0.3em"
})
});
})
var duration = 50;
console.info("Current state: %s", current_state.id);
if (current_state.accept === true) {
console.info("Accepted.");
d3.transition().duration(duration).selectAll(".node circle")
.filter(function(d) {
return d === current_state;
})
.duration(duration)
.style("stroke-opacity", 1)
.style("fill", "#cfc");
return;
}
var current_symbol = head.symbol;
var transitions_for_state = getStateTransitions(current_state);
var matching_transition = getMatchingTransition(current_symbol, transitions_for_state);
if (_.isUndefined(matching_transition)) {
var e = "No matching transition for symbol " + current_symbol + " at state " + current_state.id;
throw new Error(e)
}
var write_value = matching_transition.write;
if (! _.isUndefined(write_value)) {
head.symbol = write_value;
var old_tape = tape.map(function(d) {
return _.extend({}, d);
});
tapes.push(old_tape);
}
var direction = matching_transition.move;
var current_position = head.position;
var next_position = (direction === "L") ? current_position - 1 : current_position + 1;
var next_square = getSquare(next_position);
if (_.isUndefined(next_square)) {
tape.push({ position: next_position, symbol: "_" });
next_square = getSquare(next_position);
}
var t1 = d3.transition().duration(duration);
t1.selectAll(".node circle")
.filter(function(d) {
return d === current_state;
})
.duration(duration)
.style("stroke-opacity", 1)
.transition().duration(duration)
.style("stroke-opacity", 0);
var t_square = t1.transition().duration(duration);
var t_path = t_square.transition().duration(duration);
t_path.selectAll(".link path")
.filter(function(d) {
return d.transition === matching_transition;
})
.duration(duration)
.style("stroke", "red")
.transition().duration(duration)
.style("stroke", "#ddd");
t_path.selectAll(".link text")
.filter(function(d) {
return d.transition === matching_transition;
})
.duration(duration)
.style("fill", "black")
.transition().duration(duration)
.style("fill", "#ddd");
var t_tape = t_path.transition().duration(duration);
t_tape.each("end", function(d) {
console.info("Head: %s", head.position);
head = next_square;
current_state = matching_transition.target;
run();
})
}
run();
function getMatchingTransition(symbol, transitions) {
return _.find(transitions, function(t) { return _.contains(t.inputs, symbol); });
}
function getStateTransitions(state) {
return transitions.filter(function(t) { return t.source === state; });
}
function getSquare(position) {
return _.find(tape, function(d) { return d.position === position; });
}
function getState(id) {
return _.find(states, function(d) { return d.id === id; });
}
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment