# Difference between revisions of "Cyclic Tag System"

m (link to wikipedia) |
Markuswinand (talk | contribs) (Changed the expression "(r.iter % 3)" to the "mod(r.iter, 3)". The "%" operator is not part of ISO SQL (see "modulus expression" in the standard). Now the statement validates as SQL:2003 on http://developer.mimer.se/validator/parser200x/) |
||

Line 2: | Line 2: | ||

− | This SQL query (requires PostgreSQL 8.4) forms a cyclic tag system ([http://en.wikipedia.org/wiki/Cyclic_Tag_System#Cyclic_tag_systems wikipedia]), which is sufficient to demonstrate that SQL is Turing-complete. It is written entirely in SQL: | + | This SQL query (requires PostgreSQL 8.4) forms a cyclic tag system ([http://en.wikipedia.org/wiki/Cyclic_Tag_System#Cyclic_tag_systems wikipedia]), which is sufficient to demonstrate that SQL is Turing-complete. It is written entirely in SQL:2003-conformant SQL. |

Thanks to Andrew (RhodiumToad) Gierth, who came up with the concept and wrote the code. | Thanks to Andrew (RhodiumToad) Gierth, who came up with the concept and wrote the code. | ||

Line 16: | Line 16: | ||

The initial state is encoded in the non-recursive union arm, in this case just '1' | The initial state is encoded in the non-recursive union arm, in this case just '1' | ||

− | The (r.iter | + | The mod(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: | Parameters: | ||

the content of "p" | the content of "p" | ||

the content of the non-recursive branch | the content of the non-recursive branch | ||

− | the 3 in (r.iter | + | the 3 in mod(r.iter, 3) |

"p" encodes the production rules; the non-recursive branch is the initial state, and the 3 is the number of rules | "p" encodes the production rules; the non-recursive branch is the initial state, and the 3 is the number of rules | ||

Line 51: | Line 51: | ||

r | r | ||

LEFT JOIN p | LEFT JOIN p | ||

− | ON (r.rnum=0 and r.tag=1 and p.iter=(r.iter | + | ON (r.rnum=0 and r.tag=1 and p.iter=mod(r.iter, 3)) |

WHERE | WHERE | ||

r.rnum>0 | r.rnum>0 |

## Latest revision as of 07:54, 20 February 2015

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:2003-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 mod(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 mod(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=mod(r.iter, 3))
WHERE
r.rnum>0
OR p.iter IS NOT NULL
)
SELECT iter, rnum, tag
FROM r
ORDER BY iter, rnum;
```