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.

The TM run will be recorded in the following table:

### Turing Machine execution

Let us now record a run with a recursive query:

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.