Turing Machine in SQL (5/5)

This is the last of five posts on this subject.

In a previous post I have shown how to build a Turing Machine (TM) in SQL with Postgres using a recursive SQL function. I claimed that this would work with versions of Postgres older than 8.4. In this post, I actually investigate this claim, porting the script down to version 7.3 on a Debian Linux. Testing the relatively simple SQL script with older versions reminds us of all the goodies that have been added over the years.

Moving Back in Postgres Time…

The initial SQL script works with current Postgres 9.2.

Postgres 8.4 (2009)

Easy installation from the Postgres APT repository.

However we lose the function parameter names in SQL, although they work with PL/pgSQL, thus I must revert to $n parameter style, that is to switch:

CREATE FUNCTION recRun(ite INTEGER, sta INTEGER, pos INTEGER) ...
  ... WHERE tr.sid=sta AND tp.tid=pos ...

to the less readable:

CREATE FUNCTION recRun(INTEGER, INTEGER, INTEGER) ...
  ... WHERE tr.sid=$2 AND tp.tid=$3 ...

Postgres 8.2 (2006)

Easy installation of this unsupported version thanks to the APT repository. The Postgres 8.4 script with SQL function parameters referenced by their number works fine.

Postgres 8.1 and 8.0 (2005)

Manual installation with configure, make, initdb, pg_ctl works fine.

However, we lose the UPDATE ... AS ... aliasing, which for our query generates unsolvable attribute name ambiguities, so I had to rename tape attributes so that they do not interfere with transaction attributes. If the query had required to UPDATE and FROM the same table, I think it would not have been possible to write it, or maybe with an artificial VIEW to hide the renamings… We also lose VALUES lists which must be converted to repeated INSERTs or to a COPY syntax, and IF EXISTS in DROP SCHEMA.

Postgres 7.4 (2003)

Manual installation as above works fine.

However we lose $$ dollar quoting, so the function definition must be put inside a string, which is much less readable under emacs or vi. Compare the nice syntax coloring by pygments:

CREATE FUNCTION recRun(...) ... $$
  INSERT INTO Run(rid, ...) VALUES(...);
$$ LANGUAGE SQL;

To the older style:

CREATE FUNCTION recRun(...) ... '
  INSERT INTO Run(rid, ...) VALUES(...);
' LANGUAGE SQL;

Postgres 7.3 (2002)

Manual installation works fine.

However we lose ARRAY integration, so that I had to remove the display of the tape along the run and a related CHECK. The final tape state can still be shown.

Postgres 7.2.8 (2005)

Manual installation worked.

Easily fixed syntactic issues: no SCHEMA support, COPY does not accept an attribute list.

Nevertheless, I could not make the recursive SQL function work with 7.2.8, as the server complains that the function does not exist yet while creating it.

Conclusion

This final Postgres 7.3 compatible SQL script implements a Turing machine with a recursive SQL function. If you accept this trick, then it seems that Postgres SQL is Turing complete since version 7.3, released on November 27, 2002. The key feature is listed in Section 3.10 of the release notes: Allow recursive SQL function (Peter). It was added on May 22, 2002 by Peter Eisentraut:

commit d60f10b0e74173653d17c09750a791afe6f56404
Author: Peter Eisentraut <*>
Date:   Wed May 22 17:21:02 2002 +0000

Add optional "validator" function to languages that can validate the
function body (and other properties) as a function in the language
is created.  This generalizes ad hoc code that already existed for
the built-in languages.

The validation now happens after the pg_proc tuple of the new function
is created, so it is possible to define recursive SQL functions.

Add some regression test cases that cover bogus function definition
attempts.

In the next post I report unsuccessful attempts at compiling old versions of Postgres on modern Debian-based systems.