Turing Machine (with recursive)

A Turing Machine in SQL
using the with recursive construct, very similar in structure to
the Cyclic Tag System
by Andrew Gierth.
Query initially published on this
blog post
by Fabien Coelho.
Note: actually running this query with PostgreSQL 8.4 may require minor
syntactic changes.
See also
another version
using a recursive SQL function.
--
-- AnBnCn Turing Machine in SQL with only relations
--
DROP SCHEMA IF EXISTS Turing CASCADE;
CREATE SCHEMA Turing;
-- list of states
-- 0 is always the initial state
CREATE TABLE Turing.State(
 sid INTEGER PRIMARY KEY,
 sname TEXT UNIQUE NOT NULL, -- just for show
 isFinal BOOLEAN NOT NULL,
 scomment TEXT DEFAULT NULL
);
-- list of symbols (not really useful)
CREATE TABLE Turing.Symbol(
 cid INTEGER PRIMARY KEY,
 cname TEXT UNIQUE NOT NULL,
 ccomment TEXT DEFAULT NULL
);
-- initial tape contents
CREATE TABLE Turing.Tape(
 tid INTEGER PRIMARY KEY,
 symbol INTEGER REFERENCES Turing.Symbol,
 scomment TEXT DEFAULT NULL
);
-- TM Transition Function
CREATE TABLE Turing.Transition(
 -- initial state & symbol
 sid INTEGER NOT NULL REFERENCES Turing.State,
 symbol INTEGER NOT NULL REFERENCES Turing.Symbol,
 UNIQUE(sid, symbol),
 -- new state, symbol and move
 new_state INTEGER NOT NULL REFERENCES Turing.State,
 new_symbol INTEGER NOT NULL REFERENCES Turing.Symbol,
 move INTEGER NOT NULL CHECK(move=-1 OR move=1),
 -- explanation
 tcomment TEXT DEFAULT NULL
);
-- record state/tape/pos of TM while running
CREATE TABLE Turing.Run(
 rid INTEGER PRIMARY KEY,
 -- current state
 sid INTEGER NOT NULL REFERENCES Turing.State,
 -- full tape stored in an array
 tape INTEGER[] NOT NULL,
 -- next position on tape
 pos INTEGER NOT NULL CHECK(pos BETWEEN 0 AND array_length(tape, 1)+1)
);
-- display a tape with its symbols and head as:
-- AAaBBbCcc
-- ^
CREATE FUNCTION Turing.ShowTape(tape INTEGER[], pos INTEGER) RETURNS TEXT
IMMUTABLE STRICT AS $$
 SELECT array_to_string(
 ARRAY(SELECT s.cname
 FROM generate_series(1, array_length(tape, 1)) AS i
 JOIN Turing.Symbol AS s ON (tape[i]=s.cid)
 WHERE tape[i]<>0
 ORDER BY i ASC),
	 ) || E'\n' || repeat(' ', pos-1) || '^' ;
$$ LANGUAGE SQL;
--
-- define AnBnCn Turing Machine
--
COPY Turing.State(sid, sname, isFinal, scomment) FROM STDIN;
0	a?	FALSE	look for 'a'
1	>b	FALSE	look for 'b' once 'a' was seen
2	>c	FALSE	look for 'c' once 'b' was seen
3	A<	FALSE	look back for 'A' marker
4	>0	FALSE	check scan at the end
5	Y	TRUE	input matches a^nb^nc^n
6	N	TRUE	input does not match a^nb^nc^n
\.
COPY Turing.Symbol(cid, cname, ccomment) FROM STDIN;
0	 	special blank symbol
1	a	'a' input symbol
2	b	'b' input symbol
3	c	'c' input symbol
4	A	marker when 'a' is seen
5	B	marker when 'b' is seen
6	C	marker when 'c' is seen
\.
-- mark a as A, b as B, c as C, and loop back
COPY Turing.Transition(sid,symbol,new_state,new_symbol,move,tcomment) FROM STDIN;
0	1	1	4	+1	a -> A
0	5	4	5	+1	B -> check end
0	0	5	0	+1	blank => n=0 => ok
1	1	1	1	+1	skipping a
1	5	1	5	+1	skipping B
1	2	2	5	+1	b -> B
2	2	2	2	+1	skipping b
2	3	3	6	-1	c -> C, return
2	6	2	6	+1	skipping C
3	1	3	1	-1	return, skip a
3	2	3	2	-1	return, skip b
3	4	0	4	+1	stop return on A
3	5	3	5	-1	return, skip B
3	6	3	6	-1	return, skip C
4	0	5	0	+1	check end, blank => ok
4	4	4	4	+1	check end, skip A
4	5	4	5	+1	check end, skip B
4	6	4	6	+1	check end, skip C
0	2	6	2	+1	KO
0	3	6	2	+1	KO
0	4	6	4	+1	KO
0	6	6	6	+1	KO
1	0	6	0	+1	KO
1	3	6	3	+1	KO
1	4	6	4	+1	KO
1	6	6	6	+1	KO
2	0	6	0	+1	KO
2	1	6	1	+1	KO
2	4	6	4	+1	KO
2	5	6	5	+1	KO
3	0	6	0	+1	KO
3	3	6	3	+1	KO
4	1	6	1	+1	KO
4	2	6	2	+1	KO
4	3	6	3	+1	KO
\.
-- initial tape contents for test run: aabbcc
INSERT INTO Turing.Tape(tid, symbol) VALUES
 (1, 1),
 (2, 1),
 (3, 2),
 (4, 2),
 (5, 3),
 (6, 3);
--
-- Run TM
--
TRUNCATE Turing.Run;
-- iter: iteration number of the TM
-- sid: current state
-- len: initial tape length
-- pos: current position in the tape
-- psym: current symbol to consider in tape
-- tid, tsym: current tape[tid] = tsym
WITH RECURSIVE running(iter, sid, len, pos, psym, tid, tsym) AS (
 -- set first iteration at state 0, position 1
 SELECT
 0, 0,
 (SELECT COUNT(*)::INTEGER FROM Turing.Tape),
 1, (SELECT symbol FROM Turing.Tape WHERE tid=1),
 tid, symbol
 FROM Turing.Tape
 UNION
 -- compute next iteration
 SELECT
 pr.iter + 1,
 tr.new_state,
 pr.len,
 pr.pos + tr.move,
 -- recover next iteration symbol
 -- this hack because 'running' cannot be used twice
 MAX(CASE WHEN pr.pos+tr.move=pr.tid THEN pr.tsym ELSE NULL END) OVER (),
 CASE
 -- tape index
 WHEN hk.keep THEN pr.tid
 -- append a new index
 ELSE pr.len + pr.iter + 1
 END,
 CASE
 -- update symbol
 WHEN hk.keep AND pr.tid=pr.pos THEN tr.new_symbol
 -- or keep previous symbol
 WHEN hk.keep THEN pr.tsym
 -- append a blank
 ELSE 0
 END
 FROM running AS pr
 JOIN -- corresponding transition
 Turing.Transition AS tr ON (pr.sid=tr.sid AND pr.psym=tr.symbol)
 JOIN -- state information, necessary to know whether to stop
 Turing.State AS st ON (tr.sid=st.sid)
 CROSS JOIN -- hack to append a 0 at the end of the tape
 (VALUES (TRUE), (FALSE)) AS hk(keep)
 WHERE -- stop on a final state
 NOT st.isFinal
)
-- just stores the computed iterations
INSERT INTO Turing.Run(rid, sid, pos, tape)
 SELECT
 -- iteration, current state, tape head position
 iter, sid, pos,
 -- build an array from tape symbols for easier display
 ARRAY_AGG(tsym ORDER BY tid ASC)
 FROM running
 GROUP BY iter, sid, pos
 ORDER BY iter;
-- show results
SELECT
 r.rid AS n, s.sname,
 Turing.ShowTape(r.tape, r.pos) AS tape,
 s.isFinal AS fin, r.sid, r.pos
FROM Turing.Run AS r
JOIN Turing.State AS s USING (sid)
ORDER BY rid ASC;