Difference between revisions of "Cyclic Tag System"

From PostgreSQL wiki
Jump to: navigation, search
m (link to wikipedia)
(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:2008-conformant 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 % 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 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 % 3)
+
     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 % 3))
+
         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

Fun Snippets

Cyclic Tag System

Works with PostgreSQL

8.4

Written in

SQL

Depends on

Nothing


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;