# Cyclic Tag System

### From PostgreSQL wiki

This SQL query (requires PostgreSQL 8.4) forms a cyclic tag system (wikipedia), 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.

Parameters:

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;