# Turing Machine in SQL (4/5)

This is the fourth of five posts on this subject.

In previous posts,
I have presented different ways of implementing a Turing Machine (TM) in SQL
with Postgres.
All three techniques rely on `WITH RECURSIVE`

to iterate till the TM stops, so
as to provide some kind of while construct.

In this post, I get rid of this construct, so that the solution does not require
Postgres 8.4 or later.
Obviously there is a trick: I will use a recursive SQL function with side
effects on a `TABLE`

to execute the TM.

## TM with a Recursive SQL Function

In this post the TM is built from the following SQL features: one recursive SQL
function to iterate the TM, `INNER JOIN`

to get transition and state
informations, a `CASE`

expression to stop or recurse, a separate `TABLE`

to
store the tape contents, `INSERT`

and `UPDATE`

commands to update the tape.
A `SEQUENCE`

is also used implicitely, but could be avoided.

An `ARRAY`

with `ORDER`

and a sub-`SELECT`

are also used to record the tape
state, but is not strictly necessary, it is just there for displaying the TM
execution summary at the end.

## TM Tape Setup

The tape is stored in a standard `TABLE`

which stores the current symbols, and
possibly temporarily the previous symbol at this position.

```
-- create initial tape contents
CREATE TABLE Turing.RunningTape(
tid SERIAL PRIMARY KEY,
symbol INTEGER NOT NULL REFERENCES Turing.Symbol,
-- previous symbol needed temporarily between an update & its recursion
psymbol INTEGER REFERENCES Turing.Symbol DEFAULT NULL
);
INSERT INTO Turing.RunningTape(symbol)
SELECT symbol FROM Turing.Tape ORDER BY tid;
```

This tape will be used and modified by the next query while the TM is executed.

## TM Execution

Let us now execute a run with a recursive SQL function:

```
-- update tape as a recursive SQL function side effect
CREATE OR REPLACE FUNCTION
Turing.recRun(ite INTEGER, sta INTEGER, pos INTEGER) RETURNS INTEGER
VOLATILE STRICT AS $$
-- keep a trace for later display
INSERT INTO Turing.Run(rid, sid, pos, tape)
VALUES (ite, sta, pos,
ARRAY(SELECT symbol FROM Turing.RunningTape ORDER BY tid));
-- ensure that the tape is long enough, symbol 0 is blank
INSERT INTO Turing.RunningTape(symbol) VALUES(0);
-- update tape contents
UPDATE Turing.RunningTape AS tp
SET
-- update the tape symbol
symbol = tr.new_symbol,
-- but keep a copy as we need it again for the recursion
psymbol = tr.symbol
FROM Turing.Transition AS tr
WHERE tr.sid = sta
AND tr.symbol = tp.symbol
AND tp.tid = pos;
-- now the recursion
SELECT
CASE
-- stop recursion on a final state
WHEN st.isFinal THEN st.sid
-- or do *recurse*
ELSE Turing.recRun(ite+1, tr.new_state, pos+tr.move)
END
FROM Turing.Transition AS tr
JOIN Turing.RunningTape AS tp ON (tp.psymbol = tr.symbol)
JOIN Turing.State AS st USING (sid)
WHERE st.sid = sta AND tp.tid = pos;
$$ LANGUAGE SQL;
```

The first `INSERT`

records the TM execution and could be removed without
affecting the end result of the Turing machine.
The second `INSERT`

extends the tape with a blank symbol, so that the TM cannot
run out of the tape.
The `UPDATE`

modifies the tape contents based on the transition and state, but
keeps track of the changed symbol which is needed for the next statement.
Finally, the `SELECT`

either stops or recurses, depending on whether the state
is final.

Then the recursive SQL function can be simply invoked by providing the initial state and tape position:

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.

As the version does not require `WITH RECURSIVE`

nor `WINDOW`

functions, it
should work, possibly with some adaptation, with version of Postgres before 8.4
which initially provided these features.
See the next post for a version which works with PosgreSQL 7.3.

## Final note

For any pratical system, all Turing completness proofs really deal with memory
bounded Turing completeness, as the number of data is necessary finite, so we
are really only talking about a (possibly) big automaton.
For instance, our implementations rely on the `INTEGER`

type for tape
addresses, which implicitely imply that the tape, hence memory, is finite.
It would be a TM if we could use a mathematical integer instead, but that in
itself would require an unbounded memory.

## Links

`WITH RECURSIVE`

feature comes with SQL:1999`WINDOW`

functions come with SQL:2003.

There is a post by Jens Schauder who builds a TM with Oracle SQL, however the iteration loop is finite, so it seems to me that this is not really Turing completeness.

Since the SQL:1999 standard includes an actual programming language (SQL/PSM), one could consider that SQL is Turing complete because of that, but this is cheating!

This interesting page by Andreas Zwinkau lists various accidentally Turing complete systems.