PostgreSQL implementation of SQL is Turing Complete, as show by Andrew Gierth on PostgreSQL wiki, where a Cyclic Tag System (CTS), which is proven Turing-complete, is implemented using
WITH RECURSIVE, a
CASE conditional expressions and an
OUTER JOIN. Although the proof is sound, there is a long path from a CTS to an actual Turing Machine (TM).
The first question I want to answer is: how to build a Turing Machine with SQL only?
The second question I would like to investigate is: what SQL features are actually required to build a relational Turing Machine. For instance, can it be done without
WINDOW functions and
OUTER JOIN? (Teaser for later posts: yes!)
Turing Machine with Arrays
In this post I will show how to build a TM in SQL with the following features:
WITH RECURSIVE to iterate till the machine stops,
INNER JOIN to get transition and state informations,
ARRAY operations to build and store the tape, one
COALESCE function to deal with the end of the tape, and a sub-
SELECT with an
ORDER clause to initiate the tape.
Obviously the use of
ARRAYs make this solution not really relational, so this is cheating, but it is in SQL, it works, and allows to introduce the general setup that I will use for other more relational solutions.
Turing Machine description
First, the TM will be reprensented by a set of relations for the states, symbols, transitions, and the initial tape contents.
CREATE TABLE State( -- TM states sid INTEGER PRIMARY KEY, -- 0 is always the initial state isFinal BOOLEAN NOT NULL, sname TEXT UNIQUE NOT NULL -- just for show ); CREATE TABLE Symbol( -- TM symbols cid INTEGER PRIMARY KEY, -- 0 is always the blank symbol cname TEXT UNIQUE NOT NULL ); CREATE TABLE Transition( -- TM transition function sid INTEGER NOT NULL REFERENCES State, -- initial state symbol INTEGER NOT NULL REFERENCES Symbol, -- & symbol UNIQUE(sid, symbol), new_state INTEGER NOT NULL REFERENCES State, new_symbol INTEGER NOT NULL REFERENCES Symbol, move INTEGER NOT NULL CHECK(move=-1 OR move=1) ); CREATE TABLE Tape( -- TM initial tape contents tid INTEGER PRIMARY KEY, symbol INTEGER REFERENCES Symbol );
The TM run will be recorded in the following table:
CREATE TABLE Run( rid INTEGER PRIMARY KEY, -- machine iteration sid INTEGER NOT NULL REFERENCES State, -- current state tape INTEGER NOT NULL, -- full tape stored as an array pos INTEGER NOT NULL -- current position on tape );
Turing Machine execution
Let us now record a run with a recursive query:
WITH RECURSIVE running(rid, sid, tape, pos) AS ( -- first store initial tape contents SELECT 0, 0, ARRAY(SELECT symbol FROM Tape ORDER BY tid), 1 UNION -- then proceed to compute iterations SELECT p.rid+1, t.new_state, -- build updated tape as an array p.tape[1:p.pos-1] || -- prefix t.new_symbol || -- updated cell p.tape[p.pos+1:array_length(p.tape,1)], -- suffix -- move cursor position p.pos+t.move FROM running AS p -- get state details, to know whether to stop JOIN State AS s ON (p.sid=s.sid) -- get corresponding state transition JOIN Transition AS t ON (t.sid=p.sid AND -- coalesce defaults to blank t.symbol=COALESCE(p.tape[p.pos],0)) WHERE -- stop on a final state NOT s.isFinal ) -- just store the computed table INSERT INTO Run SELECT * FROM running;
Note that on each iteration, the next iterations of all rows seems to be recomputed over and over. This is not really the case because of the peculiar behavior of
WITH RECURSIVE discussed in the next post. Basically, only just-generated tuples are used to compute the next iteration.
COALESCE call creates implicit blanks at the end of the tape.
You can try this self-contained SQL script which implements a Turing Machine for accepting the AnBnCn language using the above method.
In the next post, I show how to put the tape in a separate
TABLE so that the TM is really relational, although it is at the price of using SQL functions.