Turing Machine (recursive SQL function)

A Turing Machine in SQL
using a recursive SQL function.
Query initially published on this
blog post
by Fabien Coelho.
See also
another version
using the with recursive construct.
--
-- AnBnCn Turing Machine in SQL with SQL functions
--
-- 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
);
--
-- 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
COPY Turing.Tape(tid, symbol) FROM STDIN;
1	1
2	1
3	2
4	2
5	3
6	3
\.
-- create initial tape contents
CREATE TABLE Turing.RunningTape(
 tid SERIAL PRIMARY KEY,
 sym INTEGER NOT NULL REFERENCES Turing.Symbol,
 -- previous symbol needed temporarily between an update & its recursion
 psym INTEGER REFERENCES Turing.Symbol DEFAULT NULL
);
-- the initial tape must be without "holes"
-- the sequence is updated as a side effects
INSERT INTO Turing.RunningTape(sym)
 SELECT symbol FROM Turing.Tape ORDER BY tid;
-- new run
TRUNCATE Turing.Run;
-- update tape as a recursive SQL function side effect
CREATE OR REPLACE FUNCTION
 Turing.recRun(INTEGER, INTEGER, INTEGER) RETURNS INTEGER
VOLATILE STRICT AS '
 -- keep a trace for later display
 INSERT INTO Turing.Run(rid, sid, pos, tape)
 VALUES ($1, $2, $3, {});
 -- ensure that the tape is long enough, symbol 0 is blank
 INSERT INTO Turing.RunningTape(sym) VALUES(0);
 -- update tape contents
 UPDATE Turing.RunningTape
 SET
 -- update the tape symbol
 sym = tr.new_symbol,
 -- but keep a copy as we need it again for the recursion
 psym = tr.symbol
 FROM Turing.Transition AS tr
 WHERE tr.sid = $2
 AND tr.symbol = sym
 AND tid = $3;
 -- now the recursion
 SELECT
 CASE
 -- stop recursion on a final state
 WHEN st.isFinal THEN st.sid
 -- or do *recurse*
 ELSE Turing.recRun($1+1, tr.new_state, $3+tr.move)
 END
 FROM Turing.Transition AS tr
 JOIN Turing.RunningTape AS tp ON (tp.psym = tr.symbol)
 JOIN Turing.State AS st USING (sid)
 WHERE st.sid = $2 AND tp.tid = $3;
' LANGUAGE SQL;
-- start Turing Machine
SELECT Turing.recRun(0, 0, 1);
-- show run
SELECT * FROM Turing.Run ORDER BY rid;
-- show final tape contents
SELECT tid, sym FROM Turing.RunningTape ORDER BY tid;