图灵机（递归）

趣味片段

图灵机

适用于 PostgreSQL

8.4

用

SQL

依赖于

无

使用with recursive结构的 SQL 实现的图灵机，其结构与 Andrew Gierth 的循环标签系统非常相似。查询最初发表在 Fabien Coelho 的博客文章上。注意：使用 PostgreSQL 8.4 实际运行此查询可能需要进行一些语法更改。另请参见使用递归 SQL 函数的另一个版本。

--
-- 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;