Turing Machine in SQL (1/5)

This is the first of five posts on this subject.

Postgres implementation of SQL is Turing Complete, as show by Andrew Gierth on Postgres wiki, where a Cyclic Tag System (CTS), which is proven Turing-complete, is implemented using WITH RECURSIVE, a WINDOW function, 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 WITH RECURSIVE, WINDOW functions and OUTER JOIN? (Teaser for later posts: yes!)

TM 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.

TM Description

First, the TM will be reprensented by a set of relations for the states, symbols, transitions, and the initial tape contents.

CREATE SCHEMA Turing;

CREATE TABLE Turing.State(
  sid INTEGER PRIMARY KEY,
  sname TEXT UNIQUE NOT NULL, -- just for show
  isFinal BOOLEAN NOT NULL,
  scomment TEXT DEFAULT NULL
);

CREATE TABLE Turing.Symbol(
  cid INTEGER PRIMARY KEY,
  cname TEXT UNIQUE NOT NULL,
  ccomment TEXT DEFAULT NULL
);

CREATE TABLE Turing.Transition(
  -- initial state & symbol
  sid INTEGER NOT NULL REFERENCES Turing.State,
  symbol INTEGER NOT NULL REFERENCES Turing.Symbol,
  UNIQUE(sid, symbol),
  -- new state, symbol and move
  new_state INTEGER NOT NULL REFERENCES Turing.State,
  new_symbol INTEGER NOT NULL REFERENCES Turing.Symbol,
  move INTEGER NOT NULL CHECK(move=-1 OR move=1),
  -- explanation
  tcomment TEXT DEFAULT NULL
);

CREATE TABLE Turing.Tape(
  tid INTEGER PRIMARY KEY,
  symbol INTEGER REFERENCES Turing.Symbol,
  scomment TEXT DEFAULT NULL
);

The TM run will be recorded in the following table:

CREATE TABLE Turing.Run(
  rid INTEGER PRIMARY KEY,
  sid INTEGER NOT NULL REFERENCES Turing.State,
  tape INTEGER[] NOT NULL,
  pos INTEGER NOT NULL CHECK(pos BETWEEN 0 AND array_length(tape, 1)+1)
);

TM 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 Turing.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
  -- p is previous state thanks to WHERE condition hack below
  FROM running AS p
  -- get state details, to know whether to stop
  JOIN Turing.State AS s ON (p.sid=s.sid)
  -- get corresponding state transition
  JOIN Turing.Transition AS t ON (p.sid=t.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 Turing.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.

The 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 \(A^nB^nC^n\) 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.