# Turing Machine in SQL (1)

This is the first of five posts [1, 2, 3, 4, 5] on this subject.

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 `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!)*

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

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

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