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:
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 INSERT
s 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:
To the older style:
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.