This is the fourth of five posts [1, 2, 3, 4, 5] on this subject.
In previous posts [1 2 3], I have presented different ways of implementing a Turing Machine (TM) in SQL with PostgreSQL. All three techniques rely on
WITH RECURSIVE to iterate till the TM stops, so as to provide some kind of while construct.
In this post, I get rid of this construct, so that the solution does not require PostgreSQL 8.4 or later. Obviously there is a trick: I will use a recursive SQL function with side effects on a
TABLE to execute the TM.
Turing Machine with a recursive SQL function
In this post the TM is built from the following SQL features: one recursive SQL function to iterate the TM,
INNER JOIN to get transition and state informations, a
CASE expression to stop or recurse, a separate
TABLE to store the tape contents,
UPDATE commands to update the tape. A
SEQUENCE is also used implicitely, but could be avoided.
ORDER and a sub-
SELECT are also used to record the tape state, but is not strictly necessary, it is just there for displaying the TM execution summary at the end.
Turing Machine tape setup
The tape is stored in a standard
TABLE which stores the current symbols, and possibly temporarily the previous symbol at this position.
This tape will be used and modified by the next query while the TM is executed.
Turing Machine execution
Let us now execute a run with a recursive SQL function:
INSERT records the TM execution and could be removed without affecting the end result of the Turing machine. The second
INSERT extends the tape with a blank symbol, so that the TM cannot run out of the tape. The
UPDATE modifies the tape contents based on the transition and state, but keep track of the changed symbol which is needed for the next statement. Finally, the
SELECT either stops or recurses, depending on whether the state is final.
Then the recursive SQL function can be simply invoked by providing the initial state and tape position:
You can try this self-contained SQL script which implements a Turing Machine for accepting the AnBnCn language using the above method.
As the version does not require
WITH RECURSIVE and
WINDOW functions, it should work, possibly with some adaptation, with version of PostgreSQL before 8.4 which initially provided these features. See the next post for a version which works with PosgreSQL 7.3.
For any pratical system, all Turing completness proofs really deal with memory bounded Turing completeness, as the number of data is necessary finite, so we are really only talking about a (possibly) big automaton. For instance, our implementations rely on the
INTEGER type for tape addresses, which implicitely imply that the tape, hence memory, is finite. It would be a TM if we could use a mathematical integer instead, but that in itself would require an unbounded memory.
WITH RECURSIVE feature comes with with SQL:1999, but
WINDOW functions come with SQL:2003.
See the Cyclic Tag System (CTS) implementation in SQL by Andrew Gierth, which seems to be Turing complete although the proof of that is quite complex.
There is a post by Jens Schauder which builds a TM with Oracle SQL, however the iteration loop is finite, so it seems to me that this is not really Turing completeness.
Since the SQL:1999 standard includes an actual programming language (SQL/PSM), one could consider that SQL is Turing complete because of that, but this is cheating!
This interesting page by Andreas Zwinkau lists various accidentally Turing complete systems.