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

In previous posts [1 2 3], I have presented different ways of implementing a Turing Machine (TM) in SQL with PostgreSQL. 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 PostgreSQL 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.

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

### Turing Machine tape setup

The tape is stored in a standard `TABLE`

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

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

### Turing Machine execution

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

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 keep 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 *AnBnCn* language using the above method.

As the version does not require `WITH RECURSIVE`

and `WINDOW`

functions, it should work, possibly with some adaptation, with version of PostgreSQL *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

The `WITH RECURSIVE`

feature comes with with SQL:1999, but `WINDOW`

functions come with SQL:2003.

See the Cyclic Tag System (CTS) implementation in SQL by Andrew Gierth, which seems to be Turing complete although the proof of that is quite complex.

There is a post by Jens Schauder which 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.