Turing Machine in SQL (4/5)

This is the fourth of five posts on this subject.

In previous posts, I have presented different ways of implementing a Turing Machine (TM) in SQL with Postgres. 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 Postgres 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.

TM 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, INSERT and UPDATE commands to update the tape. A SEQUENCE is also used implicitely, but could be avoided.

An ARRAY with 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.

TM Tape Setup

The tape is stored in a standard TABLE which stores the current symbols, and possibly temporarily the previous symbol at this position.

-- create initial tape contents
CREATE TABLE Turing.RunningTape(
  tid SERIAL PRIMARY KEY,
  symbol INTEGER NOT NULL REFERENCES Turing.Symbol,
  -- previous symbol needed temporarily between an update & its recursion
  psymbol INTEGER REFERENCES Turing.Symbol DEFAULT NULL
);

INSERT INTO Turing.RunningTape(symbol)
  SELECT symbol FROM Turing.Tape ORDER BY tid;

This tape will be used and modified by the next query while the TM is executed.

TM Execution

Let us now execute a run with a recursive SQL function:

-- update tape as a recursive SQL function side effect
CREATE OR REPLACE FUNCTION
  Turing.recRun(ite INTEGER, sta INTEGER, pos INTEGER) RETURNS INTEGER
VOLATILE STRICT AS $$
  -- keep a trace for later display
  INSERT INTO Turing.Run(rid, sid, pos, tape)
  VALUES (ite, sta, pos,
          ARRAY(SELECT symbol FROM Turing.RunningTape ORDER BY tid));
  -- ensure that the tape is long enough, symbol 0 is blank
  INSERT INTO Turing.RunningTape(symbol) VALUES(0);
  -- update tape contents
  UPDATE Turing.RunningTape AS tp
  SET
    -- update the tape symbol
    symbol = tr.new_symbol,
    -- but keep a copy as we need it again for the recursion
    psymbol = tr.symbol
  FROM Turing.Transition AS tr
  WHERE tr.sid = sta
    AND tr.symbol = tp.symbol
    AND tp.tid = pos;
  -- now the recursion
  SELECT
    CASE
      -- stop recursion on a final state
      WHEN st.isFinal THEN st.sid
      -- or do *recurse*
      ELSE Turing.recRun(ite+1, tr.new_state, pos+tr.move)
    END
  FROM Turing.Transition AS tr
  JOIN Turing.RunningTape AS tp ON (tp.psymbol = tr.symbol)
  JOIN Turing.State AS st USING (sid)
  WHERE st.sid = sta AND tp.tid = pos;
$$ LANGUAGE SQL;

The first 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 keeps 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:

-- start Turing Machine
SELECT Turing.recRun(0, 0, 1);

You can try this self-contained SQL script which implements a Turing Machine for accepting the \(A^nB^nC^n\) language using the above method.

As the version does not require WITH RECURSIVE nor WINDOW functions, it should work, possibly with some adaptation, with version of Postgres before 8.4 which initially provided these features. See the next post for a version which works with PosgreSQL 7.3.

Final note

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.

Links

WITH RECURSIVE feature comes with SQL:1999
WINDOW functions come with SQL:2003.

There is a post by Jens Schauder who 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.