Turing Machine in SQL (4)

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, 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.

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.

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

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

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:

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

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

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.

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

The 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.