# Turing Machine (recursive SQL function)

### From PostgreSQL wiki

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;