Машина Тьюринга на чистом 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
    Поделиться публикацией

    Комментарии 17

      0
      Красивый код
        +3
        Красиво, но заголовок вводит в заблуждение. Это не «чистый SQL», а SQL для Firebird. «WITH RECURSIVE», «GEN_ID», «RDB$DATABASE» и т.п. в стандартном SQL нет.
        • НЛО прилетело и опубликовало эту надпись здесь
            +1
            Строго говоря — решение с WITH RECURSIVE — тоже не обладает, число шагов конечное и очень небольшое. Решение более «в лоб» — запускать бесконечно много раз запрос, но это уже требует процедурного SQL и какого-то подобия цикла (точнее, перехода).
              0
              1024 шага в Firebird
            +3
            Конструкция USING в том числе с поддержкой рекурсии введена в SQL-1999 (SQL3) ( en.wikipedia.org/wiki/SQL ). Если какие-то СУБД не поддерживают этот стандарт, то это не проблемы шерифа.
            RDB$DATABASE имеет аналог в каждой СУБД (DUAL в Oracle, SELECT без FROM в MS SQL и т.п.). Операции манипуляции с генераторами или последовательностями есть так же во всех уважающих себя СУБД. Так что указанный код вполне себе «SQL», с небольшими особенностями синтаксиса, которые не влияют на суть.
              –2
              Хотя правильней, конечно, было бы написать «Машина Тьюринга на чистом SQL-1999» :)
                0
                мне все-таки кажется, в заголовке эти подробности лишние :)
                  +1
                  тогда это была бы неправда, «чистой» реализации любого из стандартов sql не существует. а «чистый sql» это правда, как правда и то, что sql-ы бывают разные
                    0
                    правильнее было бы написать, конечно, DML, а не sql, но эту аббревиатуру мало кто помнит.
            +3
            Однозначный вин. Но считаю идею ненормальности раскрытой не полностью. Теперь напишите интерпретатор sql для получившегося интерпретатора машины Тьюринга. И запустите интерпритатор Тьюринга на получившемся интерпретаторе sql. (Тем не менее извращение заслуживает всяческих похвал)
              +1
              А я надеялся, что смогу спать теперь спокойно :(
              Эти бесконечные ленты мне уже снятся, два месяца думал над решением
              0
              А что если хранить состояние в пользовательских переменных при помощи RDB$SET_CONTEXT и RDB$GET_CONTEXT?
                0
                можно, наверное, но без рекурсии все равно, боюсь, не получится
                +1
                Может быть, кому-то будет интересно: есть решатель судоку, написанный одним-единственным стейтментом Oracle SQL.
                  0
                  Это не чистый SQL, если я не ослепла.
                    0
                    а что такое чистый SQL?

                    PS: Я имел ввиду DML

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое