# 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 `ARRAY`

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