Turing Machine in SQL (5)
In a previous post I have shown how to build a Turing Machine (TM) in SQL with PostgreSQL using a recursive SQL function. I claimed that this would work with versions of PostgreSQL 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 PostgreSQL time…
The initial SQL script works with current PostgreSQL 9.2.
PostgreSQL 8.4 (2009)
Easy installation from the PostgreSQL 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 ...
PostgreSQL 8.2 (2006)
Easy installation of this unsupported version thanks to the APT repository. The PostgreSQL 8.4 script with SQL function parameters referenced by their number works fine.
PostgreSQL 8.1 and 8.0 (2005)
Manual installation with
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
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
PostgreSQL 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
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;
PostgreSQL 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.
PostgreSQL 7.2.8 (2005)
Manual installation worked.
Easily fixed syntactic issues: no
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.
This final PostgreSQL 7.3 compatible SQL script implements a Turing machine with a recursive SQL function. If you accept this trick, then it seems that PostgreSQL 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.