Pure SQL Turing Machine

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

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

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

However, I managed to get around these limitations.

For a start, I wrote a Turing machine on a regular stored procedure. I don’t know why ksuha used recursion, I did it in an ordinary loop and on an endless loop on both sides. There is nothing remarkable in that code, so I immediately proceeded to the implementation on “bare” SQL.
')
To solve the first problem in Firebird 2.1, there are already two constructs: MERGE and UPDATE OR INSERT.
At first I planned to use the second one, but with its help you can only modify or insert one record. MERGE allows you to "glue" the table with a random selection.

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

For the storage of the program and the tape, a table structure similar to the original post was used.

That's 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 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 sample with one row without any table at all.
Thus, we can assume that DML SQL in the Firebird 2.1 implementation can be considered a programming language that is Turing complete. Theoretically, such a query can be performed on any DBMS that supports recursive queries and constructions like MERGE, taking into account the differences in syntax.

instead of the afterword

Initially, it was planned to store the state in the generator, aka SEQUENCE. However, 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" I could not. Nevertheless, this experiment allowed finding some interesting solutions when working with generators:

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

   GEN_ID(POS, <increment>)=GEN_ID(POS, 0) 

  For any increment, it returns true;
• 2) you can reset the generator design
  

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

  Using together with 1) you can reset the generator in the condition WHERE.

I must say that the nesting of recursive queries of Firebird is limited to 1024 levels, so if I can still do it 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 of

Firebird 2.1 Release Notes