Turing Machine (with recursive)

Fun Snippets

Turing Machine

Works with PostgreSQL

8.4

Written in

SQL

Depends on

Nothing

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;