20 August 2013

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

In a previous post I presented how to implement a Turing Machine (TM) with an ARRAY to store the tape contents. This solution is not really relational, so in this post I’ll show how to build a TM with SQL-only functions.

## Turing Machine with SQL functions

In this post the TM is built from the following SQL features: WITH RECURSIVE to iterate till the machine stops, INNER JOIN to get transition and state informations, a TABLE to store the evolving tape contents, SQL functions with a LATERAL join to INSERT into and UPDATE and SELECT from the tape.

A SEQUENCE and an ORDER clause is used in the code, but they are not strictly necessary. Also, an ARRAY is used to record the tape state as the machine is executed, but is not strictly necessary either, it is there for displaying the TM execution summary at the end.

### Turing Machine tape

The TM tape will be stored in a TABLE:

This running tape will be updated and accessed through two SQL functions:

In the first function, a blank symbol is inserted on each iteration so as to ensure that we do not try to access the tape out of its defined content. Note that the second function which returns the current symbol is necessary because of the peculiar behavior of WITH RECURSIVE which is discussed later.

### Turing Machine execution

Let us now record a run with a recursive query:

Note that on each iteration, the next iterations seems to be recomputed over and over, which would result in bad results as the side effects on RunningTape would be cumulated… However this is not actually the case, as WITH RECURSIVE only iterates on new tuples, those that have just been generated by the previous iteration, and ignores those of other preceding iterations.

A more surprising behavior, ISTM undocumented, is that RunningTape contents is not seen to change from the recursive query as iterations are processed, as if it was in a SERIALIZABLE transaction, but the contents seen through the upd and get functions does change over time. The effect of this behavior is that if the get function is replaced with a straightforward JOIN the values fetched are those of the initial table, that is they are not updated, thus both function are really necessary. From a transaction perspective, it seems that the functions are executed in a different realm outside of the WITH query. It really looks like a bug to me, but I was told that it is a feature. Hmmm.

You can try this self-contained SQL script which implements a Turing Machine for accepting the AnBnCn language using the above method. PostgreSQL 9.3 is required because of the LATERAL join.

In the next post, I show how to put the tape directly in the recursive table and get rid of functions, so that the TM is really relational and does not use SQL functions with side effects.