# Cyclic Tag System

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