This is the third of five posts [1, 2, 3, 4, 5] on this subject.
In previous posts [1, 2], I have presented how to implement a Turing Machine (TM) with the tape stored as an ARRAY
or in a separate TABLE
accessed through SQL functions. In this post the solution is more cleanly relational, with the tape contents stored in a column of the recursive query, very like Andrew Gierth’s CTS implementation.
Turing Machine with a window function
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, WINDOW
functions and CASE
expression to extract the next symbol from the recursive table, two sub-SELECT
s to initialize the recursion, another CASE
expression to copy, update and extend the tape, a CROSS JOIN
to append blanks at the end of the tape.
An ARRAY
, GROUP BY
and ORDER
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 execution
Let us now execute a run with a recursive query:
Some comments about this query:
The motivation for the WINDOW
function is that PostgreSQL forbids using the recursive table twice in the query, so this function allows to hide the additional reference needed to extract the next symbol. I do not really understand the motivation for this restriction, which seems a little bit artificial. Possibly it allows some optimisation when iterating on the query, but is also impairs what can be done with the WITH RECURSIVE
construct.
There is also a CROSS JOIN
hack for appending a blank symbol to the tape at each iteration, so that a tape symbol is always found when moving the TM head.
This query basically uses the same tricks as the CTS one, but for the OUTER JOIN
or other NULL
handling which are avoided (well, there is a NULL
, but putting -1 would work as well). ISTM that they are needed for CTS because of the specifics of CTS, namely that a rule must only be applied when a tape contains 1, or ignored otherwise.
You can try this self-contained SQL script which implements a Turing Machine for accepting the AnBnCn language using the above method.
In the next post, I show how to get rid of both WITH RECURSIVE
and WINDOW
function…