All examples By author By category About

plmrry

Full window Github gist

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='https://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>

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>

https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.3/d3.min.js

https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js