Turing Machine (recursive SQL function)

Fun Snippets

Turing Machine

Works with PostgreSQL

7.3

Written in

SQL

Depends on

Nothing

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;