Машина Тьюринга на чистом SQL

Пару месяцев назад прочитал пост, в котором уважаемая ksusha написала эмулятор машины Тьюринга используя MySQL и хранимые процедуры. Статья дала толчок к идее сделать машину Тьюринга на чистом SQL, без использования хранимых процедур. Для реализации был использован знакомый и любимый Firebird версии 2.1.

Существует две принципиальные проблемы при создании машины Тьюринга на голом SQL:

• 1) лента машины может быть и модифицирована и дописана, что требует операторов INSERT и UPDATE в одной конструкции;
• 2) машина Тьюринга требует как минимум одной переменной для состояния. Обычные SQL(DML)-запросы не могут хранить промежуточных переменных, по крайней мере в Firebird.

Тем не менее, мне удалось обойти эти ограничения

Для начала я написал машину Тьюринга на обычной хранимой процедуре. Не знаю, зачем ksuha использовала рекурсию, я сделал обычным циклом и на бесконечной в обе стороны ленте. Ничего примечательного в том коде нет, поэтому сразу приступил к реализации на «голом» SQL.

Для решения первой проблемы в Firebird 2.1 имеется аж две конструкции: MERGE и UPDATE OR INSERT.
Сначала планировал воспользоваться второй, однако с ее помощью можно модифицировать или вставить только 1 запись. MERGE позволяет «склеить» таблицу с произвольной выборкой.

Для хранения состояний после ряда экспериментов было решено использовать рекурсивные запросы, которые тоже появились в версии 2.1.

Для хранения программы и ленты использовалась структура таблиц, аналогичная исходному посту.

Вот что в итоге у меня получилось:

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)

в вычисляемом поле state храним состояние, pos — позиция на ленте.
конструкция «FROM RDB$DATABASE» — это такая «особенность» Firebird, используется когда нужно сформировать выборку с одной строчкой без какой-либо таблицы вообще.
Таким образом, можно считать, что DML SQL в реализации Firebird 2.1 можно считать языком программирования, полным по Тьюрингу. Теоретически, подобный запрос можно выполнить на любой СУБД, поддерживающей рекурсивные запросы и конструкции вроде MERGE, с учетом отличий синтаксиса.

вместо послесловия

Первоначально, планировалось хранить состояние в генераторе, он же SEQUENCE. Однако написать такой запрос — источник новых данных для ленты, чтобы он мог бегать по программе и ленте «туда-сюда» мне не удалось. Тем не менее, этот эксперимент позволил найти несколько интересных решений при работе с генераторами:

• 1) чтобы подвинуть генератор в секции WHERE можно воспользоваться конструкцией
  

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

  При любом значении increment она возвращает истину;
• 2) обнулить генератор можно конструкцией
  

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

  Используя совместно с 1) можно обнулить генератор в условии WHERE.

Надо сказать, что вложенность рекурсивных запросов Firebird огранична 1024 уровнями, поэтому если мне все-таки удастся сделать это на генераторах — ограничение будет снято.

структура таблиц

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
); 

источники

Firebird 2.1 Release Notes