Cyclic Tag System
From PostgreSQL wiki
(Cyclic Tag System)
Revision as of 11:44, 6 August 2011
This SQL query (requires PostgreSQL 8.4) forms a cyclic tag system, which is sufficient to demonstrate that SQL is Turing-complete. It is written entirely in SQL:2008-conformant SQL.
Thanks to Andrew (RhodiumToad) Gierth, who came up with the concept and wrote the code.
The productions are encoded in the table "p" as follows:
"iter" is the production number; "rnum" is the index of the bit; "tag" is the bit value.
This example uses the productions:
110 01 0000
The initial state is encoded in the non-recursive union arm, in this case just '1'
The (r.iter % n) subexpression encodes the number of productions, which can be greater than the size of table "p", because empty productions are not included in the table.
the content of "p" the content of the non-recursive branch the 3 in (r.iter % 3)
"p" encodes the production rules; the non-recursive branch is the initial state, and the 3 is the number of rules
The result at each level is a bitstring encoded as 1 bit per row, with rnum as the index of the bit number.
At each iteration, bit 0 is removed, the remaining bits shifted up one, and if and only if bit 0 was a 1, the content of the current production rule is appended at the end of the string.
WITH RECURSIVE p(iter,rnum,tag) AS ( VALUES (0,0,1),(0,1,1),(0,2,0), (1,0,0),(1,1,1), (2,0,0),(2,1,0),(2,2,0),(2,3,0) ), r(iter,rnum,tag) AS ( VALUES (0,0,1) UNION ALL SELECT r.iter+1, CASE WHEN r.rnum=0 THEN p.rnum + MAX(r.rnum) OVER () ELSE r.rnum-1 END, CASE WHEN r.rnum=0 THEN p.tag ELSE r.tag END FROM r LEFT JOIN p ON (r.rnum=0 AND r.tag=1 AND p.iter=(r.iter % 3)) WHERE r.rnum>0 OR p.iter IS NOT NULL ) SELECT iter, rnum, tag FROM r ORDER BY iter, rnum;