Turing Machine in SQL (3)

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-SELECTs 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:

WITH RECURSIVE running(iter, sid, len, pos, psym, tid, tsym) AS (
  -- set first iteration at state 0, position 1
    SELECT
      -- first, common part is repeated over and over
      0, 0,
      -- tape length needed to know where to insert blanks
      (SELECT COUNT(*)::INTEGER FROM Tape),
      -- position and next symbol to consider
      1, (SELECT symbol FROM Tape WHERE tid=1),
      -- then the tape contents
      tid, symbol
    FROM Tape
  UNION
  -- compute next iteration
    SELECT
       pr.iter + 1,
       tr.new_state,
       pr.len, -- the initial length could also be recomputed with a sub-query
       pr.pos + tr.move,
       -- recover next iteration symbol
       -- this "hack" because 'running' cannot be used twice in the query
       MAX(CASE WHEN pr.pos+tr.move=pr.tid THEN pr.tsym ELSE NULL END) OVER (),
       CASE
         WHEN hack.keep THEN pr.tid   -- tape index
         ELSE pr.len + pr.iter + 1    -- append a new index
        END,
       CASE
         WHEN hack.keep AND pr.tid=pr.pos THEN tr.new_symbol    -- update symbol
         WHEN hack.keep THEN pr.tsym                  -- or keep previous symbol
         ELSE 0                                      -- or append a blank symbol
       END
    FROM running AS pr
    JOIN -- corresponding transition
         Transition AS tr ON (pr.sid=tr.sid AND pr.psym=tr.symbol)
    JOIN -- state information, necessary to know whether to stop
         State AS st ON (tr.sid=st.sid)
    CROSS JOIN -- hack to append a 0 at the end of the tape
         (VALUES (TRUE), (FALSE)) AS hack(keep)
    WHERE -- stop on a final state
          NOT st.isFinal
)
-- just stores the computed iterations
INSERT INTO Run(rid, sid, pos, tape)
  SELECT
    -- iteration, current state, tape head position
    iter, sid, pos,
    -- build an array from tape symbols for easier display
    ARRAY_AGG(tsym ORDER BY tid ASC)
  FROM running
  GROUP BY iter, sid, pos
  ORDER BY iter;

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…