Pure SQL Turing Machine

A couple of months ago I read a post in which the respected ksusha wrote a Turing machine emulator using MySQL and stored procedures. The article gave impetus to the idea of ​​making a Turing machine in pure SQL, without using stored procedures. For implementation, the familiar and beloved Firebird version 2.1 was used.

There are two fundamental problems when creating a Turing machine on bare SQL:

• 1) the tape of the machine can be modified and added, which requires the INSERT and UPDATE statements in the same design;
• 2) a Turing machine requires at least one state variable. Regular SQL (DML) queries cannot store intermediate variables, at least in Firebird.

However, I managed to get around these limitations.

First, I wrote a Turing machine on a regular stored procedure. I don’t know why ksuha used recursion, I did it in a regular loop and on an endless ribbon on both sides. There is nothing remarkable in that code, so I immediately started to implement it on bare SQL.

To solve the first problem in Firebird 2.1, there are already two constructions: MERGE and UPDATE OR INSERT.
At first I planned to use the second, but with its help you can modify or insert only 1 record. MERGE allows you to "glue" a table with an arbitrary selection.

To store states after a series of experiments, it was decided to use recursive queries, which also appeared in version 2.1.

To store the program and the tape, a table structure similar to the original post was used.

Here is what I ended up with:

MERGE INTO ribbon r
USING (
  WITH RECURSIVE data AS (
  SELECT 0 AS state, 1 AS pos, (SELECT sinput FROM ribbon WHERE id = 1) AS val FROM RDB$DATABASE
  UNION ALL
  SELECT
    p.out_state AS STATE,
    CASE
      WHEN p.actions = '<' THEN data.pos - 1
      WHEN p.actions = '>' THEN data.pos + 1
      ELSE data.pos
    END AS pos,
    CASE
      WHEN p.actions = '<' THEN COALESCE((SELECT sinput FROM ribbon WHERE id = (data.pos - 1)), ' ')
      WHEN p.actions = '>' THEN COALESCE((SELECT sinput FROM ribbon WHERE id = (data.pos + 1)), ' ')
      ELSE p.actions
    END AS val
    FROM program p
    JOIN data ON data.state = p.in_state
    WHERE p.sread = COALESCE((SELECT sinput FROM ribbon WHERE id = data.pos), ' ') 
                AND p.actions != '#'
  )
  SELECT * FROM data
) data ON data.pos = r.id
WHEN MATCHED THEN
  UPDATE SET sinput = data.val
WHEN NOT MATCHED THEN
  INSERT (id, sinput) VALUES (data.pos, data.val)

in the calculated state field we store the state, pos is the position on the tape.
the “FROM RDB $ DATABASE” construct is such a “feature” of Firebird that is used when you need to create a single-row selection without any table at all.
Thus, we can assume that DML SQL in the implementation of Firebird 2.1 can be considered a Turing-complete programming language. Theoretically, a similar query can be performed on any DBMS supporting recursive queries and constructs like MERGE, taking into account the differences in syntax.

instead of an afterword

Initially, it was planned to store the state in the generator, aka SEQUENCE. However, I was not able to write such a request - a source of new data for the tape so that it could run around the program and the tape back and forth. Nevertheless, this experiment made it possible to find several interesting solutions when working with generators:

• 1) to move the generator in the WHERE section, you can use the design
  

  GEN_ID(POS, )=GEN_ID(POS, 0)

  For any increment, it returns true;
• 2) the generator can be reset to zero
  

  GEN_ID(POS, -GEN_ID(POS, 0))

  Using together with 1) it is possible to reset the generator in the WHERE clause.

I must say that the nesting of recursive Firebird queries is limited to 1024 levels, so if I still manage to do this on generators, the restriction will be removed.

table structure

CREATE TABLE PROGRAM (
   IN_STATE   INTEGER NOT NULL,
   SREAD      CHAR(1) NOT NULL,
   ACTIONS    CHAR(1) NOT NULL,
   OUT_STATE  INTEGER NOT NULL
);
CREATE TABLE RIBBON (
   SINPUT  CHAR(1) NOT NULL,
   ID      INTEGER NOT NULL
); 

sources

Firebird 2.1 Release Notes