TuringMachine.sql

test3.txt

     A   B   C   D 
0 : 2<D 1>D 2>C 0>C
1 : 5>C 3>B 2>D 0<D
2 : 1<C 0<C 1>A 1<B
3 : 6>A 2>D 0>C 6<D
4 : 3<C 3># 2>D 0<B
5 : 4<A 6<A 5>A 0>D
6 : 5<A 5<C 6<C 4<D

TuringMachine.sql

/*
 * Turing Machine Simulator for SQLite3
 * (requires version >= 3.8.3)
 */

-- .headers on
.separator \t

DROP TABLE IF EXISTS stdin;
CREATE TABLE stdin(line);

-- http://golf.shinh.org/p.rb?Turing+Machine#test3
.import test3.txt stdin

WITH RECURSIVE
tmp(buf, col) AS (
  SELECT (SELECT trim(line)
    FROM stdin
    WHERE substr(line, 1, 1)=' '), 5
  UNION ALL SELECT substr(tmp.buf, 5), tmp.col+4
    FROM tmp
    WHERE length(tmp.buf)>2
),
program(state, num, pnum, move, nextstate) AS (
  SELECT
    substr(t.buf, 1, 1),
    substr(line, 1, 1),
    substr(line, t.col, 1),
    substr(line, t.col+1, 1),
    substr(line, t.col+2, 1)
  FROM stdin, tmp t
  WHERE substr(line, 1, 1) <> ' '
),
machine(step, state, tape, cur) AS (
  SELECT 0, 'A', '0', 1
  UNION ALL SELECT
    m.step+1,
    p.nextstate,
    CASE WHEN m.cur = 1 AND p.move = '<' THEN '0'
         ELSE substr(m.tape, 1, m.cur-1) END
    || p.pnum
    || CASE WHEN m.cur = length(m.tape) AND p.move = '>' THEN '0'
            ELSE substr(m.tape, m.cur+1) END,
    CASE p.move WHEN '<' THEN max(1, m.cur-1) ELSE m.cur+1 END
  FROM machine m INNER JOIN program p
    ON m.state = p.state AND substr(m.tape, m.cur, 1) = p.num
  WHERE m.state <> '#' AND m.step < 100000
)
SELECT tape FROM machine WHERE state = '#';