Pull to refresh

Эмулятор машины Тьюринга на MySQL

Reading time 8 min
Views 12K
Недавно на одном из собеседований мне задали задачку на разбор строки только средствами MySQL.
После этого я задумалась: а вообще, насколько сложные задачи такого рода можно решить с помощью одной лишь СУБД? Ответ нашелся быстро: средствами MySQL можно решить вообще любую задачу на распознавание строк. А чтобы делать это более удобным и универсальным способом, достаточно написать примитивный эмулятор конечного автомата, а еще лучше — машины Тьюринга, разумеется используя только лишь конструкции, любезно предоставляемые MySQL. Итак, начнем эксперимент.

Проектируем

Любая программа начинается с проекта. Так будет и в этот раз. Прежде всего, что такое машина Тьюринга, что она делает, что умеет? Умеет она, прямо скажем, немного. Имея в распоряжении бесконечную ленту и управляющее устройство (каретку) машина может:
  1. Двигаться по ленте влево и вправо
  2. Читать с ленты символ
  3. Писать на ленту символ
  4. Переходить в различные состояния

Инструкция для машины Тьюринга, переведенная на русский язык, звучит примерно так: «Находясь в состоянии 1 и считывая символ «а», двигайся вправо и переходи в состояние 2».
Разумеется, таким образом давать указания машине Тьюринга не очень удобно, поэтому формализуем наши инструкции следующим образом:
'>' — двигаться вправо
'<' — двигаться влево
'#' — остановиться
Вот примерный набор инструкций для машины:
0,1,>,1
1,0,>,2
2,0,>,3
3, ,>, 4
4, ,1, 4
4,1,#,4

Эта довольно-таки бесполезная программа проверяет, является ли двоичное число, записанное на ленте, числом 4, и если да, то пишет через пробел цифру 1.
Данная машина подразумевает некоторые допущения.
Во-первых, исходная позиция управляющего устройства вполне может находиться слева, а не справа от исходных данных.
Во-вторых, лента «бесконечна» только в одну сторону.
В-третьих, как вы могли заметить, вышеприведенная машина Тьюринга после считывания символа может сделать только одно действие: либо записать символ, либо сдвинуться по ленте. Будем проектировать эмулятор с учетом этих допущений.

Весь проект будет состоять из следующих частей:

  1. Таблица, призванная имитировать ленту, состоящая из одного поля
  2. Таблица для вывода ошибок, также с одним полем
  3. Таблица для самих инструкций, из 4-х полей (исходное состояние, считываемый символ, действие, результирующее состояние).
  4. Хранимая рекурсивная процедура, содержащая логику работы эмулятора.


Для чего нужна таблица вывода ошибок? Ну это же все-таки какой-никакой, а интерпретатор примитивнейшего языка. Поэтому информация о том, почему программа споткнулась, была бы не лишней.
Итак, как будет происходить работа с эмулятором? Вы вставляете текст программы в предназначенную для нее таблицу по правилу одна инструкция — одна строка, вставляете в таблицу-ленту исходные данные и запускаете процедуру. В зависимости от того что вы в своей программе понапишете, то и будет в итоге на ленте. А если будет что-то уж совсем неожиданное можно будет посмотреть в таблицу ошибок.
Ну что же, самое время приступать к кодерской части.

Разрабатываем

Для начала создадим БД и таблицы.

CREATE DATABASE turing;

CREATE TABLE program (

	in_state INT NOT NULL ,

	sread VARCHAR( 1 ) NOT NULL ,

	actions VARCHAR( 1 ) NOT NULL ,

	out_state INT NOT NULL

	) 
	ENGINE = MYISAM CHARACTER SET utf8 COLLATE utf8_unicode_ci;



CREATE TABLE output_string (

	output TEXT NOT NULL

	) 
	ENGINE = MYISAM ;

CREATE TABLE ribbon (

	sinput TEXT NOT NULL

	) 
	ENGINE = MYISAM ;


В таблице для вывода ошибок output_string нужно создать одну пустую строчку и более ее не трогать.

Теперь приступаем к самому главному — созданию процедуры. Но перед этим нужно разрешить в конфиге MySQL рекурсию, поскольку она нам сильно понадобится.
Для этого пропишем max_sp_recursion_depth = 255 в my.cnf.

Я сначала приведу код процедуры полностью, а ниже дам расшифровку, дабы не портить вид комментариями.

delimiter //

CREATE procedure turing(IN sstate INT(11), IN pos INT(11)) 

BEGIN

	turing:BEGIN

	SET @p=pos;

	SET @sstate=sstate;

	SELECT @inread:=SUBSTRING(sinput, @p, 1) FROM ribbon;

	SELECT @instate:=in_state, @sread:=sread, @actions:=actions, @out_state:=out_state, @numrows:=count(in_state) 

	FROM program 

	WHERE in_state = @sstate AND sread = @inread;

	

	IF @numrows > 1 THEN

		UPDATE output_string SET output= 'Confused :(';

		LEAVE turing;	

	ELSEIF @numrows = 0 THEN

		UPDATE  output_string SET output='Do not understand what to do next :(';

		LEAVE turing;	

	ELSE

		SELECT @lin:= LENGTH(sinput) FROM ribbon; 

		SELECT @input:=sinput FROM ribbon; 

		IF @actions = '>' THEN

			IF @lin = pos THEN 

				SELECT @new_input:=CONCAT(sinput, '     ') FROM ribbon; 

				UPDATE ribbon SET sinput=@new_input;

			END IF;

			SET @pos=pos+1;

		ELSEIF @actions = '<' THEN

			IF pos>1 THEN

				SET @pos=pos-1;

			ELSE 

				UPDATE output_string SET output='Carriage has left the ribbon';	

				LEAVE turing;

			END IF;

		ELSEIF @actions = '#' THEN

			LEAVE turing;	

		ELSE 

			SELECT @head:=SUBSTRING(sinput, 1, pos-1) FROM ribbon;

			SELECT @tail:=SUBSTRING(sinput, pos+1, @lin) FROM ribbon;

			SELECT @inp:=CONCAT(@head, @actions, @tail);

			UPDATE ribbon SET sinput=@inp;

			SET @pos=pos;

		END IF;

	CALL turing(@out_state, @pos);

	END IF;

END;

END //

Начало понятно, создаем процедуру и передаем ей два параметра — состояние машины state и позицию управляющего устройства pos.

Далее помечаем наш блок BEGIN...END меткой turing, чтобы можно было использовать ее для выхода.

После этого считываем в переменную @inread символ, на котором в данный момент находится каретка.

Выбираем из таблицы program строки, в которых состояние равно переданному в параметре, а поле sread — считываемый символ равен фактическому символу, на котором находится наше управляющее устройство. Эти два параметра однозначно определяют инструкцию для машины Тьюринга, поэтому строчка, удовлетворяющая условию, должна быть единственной.

Обрабатываем ситуацию, когда нет соответствующих инструкций — эмулятор завершает свою работу с ошибкой — он просто не знает что делать дальше.

Обрабатываем ситуацию, когда инструкций, удовлетворяющих условию, больше чем одна. В таком случае машина также не знает что делать дальше, и эмулятор завершает работу с ошибкой, сообщая, что запутался.

Если же все в порядке, то есть количество строк равно 1, то считаем длину входной строки и начинаем обрабатывать действия.Тут также есть несколько нюансов. Во-первых, мы должны помнить, что лента должна быть бесконечна в одну сторону, а длина входных данных отнюдь не бесконечна. Поэтому, если управляющее устройство находится в конце входной строки, а программа дает указание двигаться вправо, добавляем несколько пробелов и выполняем инструкцию, увеличивая позицию на 1.

В случае с движением влево обрабатываем ситуацию, когда каретка выходит за пределы ленты. Тут уж ничего не поделаешь. Извините, лента «бесконечна» только в одну сторону.

При подаче программой сигнала «стоп», обозначаемого символом #, выходим из процедуры.

Если символ не соответствует ни одному из вышеприведенных, то есть это не >, < или #, это значит, что его нужно записать на ленту, затерев текущий. Проворачиваем этот трюк с помощью нехитрой встроенной функции CONCAT().

Далее продолжаем в том же духе, передавая уже модифицированные значения параметров. @out_state в данном случае — выходное состояние, которое является входным для следующей инструкции.

Тестируем

Итак, подходим к заключительной стадии — тестированию. Мне захотелось сделать что-то значительное на этом эмуляторе, чтобы доказать, что MySQL на самом деле всемогущий. Поэтому мы будем решать довольно-таки нетривиальную, хоть и распространенную задачку — валидировать римские числа.
Программа будет работать достаточно просто — на вход принимать строку символов и, если эта строка является корректным римским числом, печатать через пробел на ленте «Ok».
Несмотря на кажущуюся сложность, задача простая. Нужно для каждого символа, используемого для записи римского числа, определить, какие не могут следовать за ним. К примеру, за L не может следовать С, то есть запись LC не может считаться римским числом. Число 50 записывается просто как L. Или, к примеру, максимальное число идущих подряд I — 3, следовательно IIII — не римское число, и т.д. Не буду подробно останавливаться на этих правилах, ибо это тема отдельной статьи.
Входной алфавит у нас состоит из следующих символов: M, D, C, L, X, V и I. Я решила обозвать начальное состояние номером 47, потому что мне нравится число 47 и еще для того, чтобы продемонстрировать, что состояния можно использовать любые, и не обязательно начинать с 0 (по крайней мере в этом эмуляторе нулевое состояние вовсе не обязательно).
Вставим нашу программу в БД:

insert into program values
(47,' ','#',47), (48,' ','>',64),(49,' ','>',64),
(50,' ','>',64),(51,' ','>',64),(52,' ','>',64),
(53,' ','>',64), (54,' ','>',64),(55,' ','>',64),
(56,' ','>',64), (57,' ','>',64),(58,' ','>',64),
(59,' ','>',64), (60,' ','>',64), (61,' ','>',64),
(62,' ','>',64), (63,' ','>',64),(65,' ','>',64),
(66,' ','>',64), (64,' ','O',64),(64,'O','>',70),
(70,' ','k',70),(70,'k','>',71),

(47,'I','>',48),(48,'V','>',51),(48,'X','>',51),
(51,'V','#',51),(51,'C','#',51),(51,'L','#',51),
(51,'D','#',51), (51,'M','#',51), (51,'X','#',51),

(48,'C','#',48),(48,'L','#',48),(48,'D','#',48),
(48,'M','#',48),(48,'I','>',49), (49,'I','>',50),
(50,'I','#',50),(50,'V','#',50), (50,'C','#',50),
(50,'L','#',50),(50,'D','#',50), (50,'M','#',50),
(50,'X','#',50),

(47,'V','>',52),(52,'I','>',48),(52,'V','#',48),
(52,'X','#',48),(52,'C','#',48),(52,'M','#',48),
(52,'D','#',48),(52,'L','#',48),(47,'X','>',53),
(53,'V','>',52),(53,'I','>',48),(53,'D','#',53),

(53,'M','#',53),(53,'L','>',53),(53,'C','>',53),
(53,'X','>',55),(55,'D','#',55),(55,'M','#',55),
(55,'C','#',55),(55,'L','#',55),(55,'V','>',52),
(55,'I','>',48),(55,'X','>',56),(56,'X','#',56),
(56,'D','#',56),(61,'C','>',62),(56,'M','#',56),
(56,'C','#',56),(56,'L','#',56),(56,'V','>',52),
(56,'I','>',48),

(47,'L','>',54),(54,'X','>',53),(54,'V','>',52),
(54,'I','>',48),(54,'D','#',54),(54,'C','#',54),
(54,'M','#',54),(54,'L','#',54),

(47,'C','>',59),(59,'X','>',53),(59,'I','>',48),
(59,'L','>',54),(59,'V','>',52),(59,'M','>',65),
(65,'M','#',65),(65,'V','>',59),(65,'X','>',59),
(65,'I','>',59),(65,'L','>',59),(65,'C','#',65),

(59,'D','>',66),(66,'D','#',66),(66,'M','#',65),
(66,'V','>',59),(66,'X','>',59),(66,'I','>',59),
(66,'L','>',59),(66,'C','#',65),(59,'C','>',61),
(61,'C','>',62),(61,'I','>',47),(62,'X','>',53),
(62,'I','>',48),(62,'L','>',54),(62,'V','>',52),
(62,'C','#',62),(61,'M','#',59),(61,'D','#',59),
(62,'M','#',62),(62,'D','#',62),

(47,'D','>',60),(60,'M','#',60),(60,'C','>',59),
(60,'D','#',60),(60,'X','>',53),(60,'I','>',48),
(60,'L','>',54),(60,'V','>',52),

(47,'M','>',63),(63,'M','>',63),(63,'C','>',59),
(63,'D','>',60),(63,'X','>',53),(63,'I','>',48),
(63,'V','>',52),(63,'L','>',54)

Первый блок программы отвечает за заключительный этап — сюда мы попадаем, когда число успешно прошло валидацию, и каретка дошла до пробела. С этого момента начинаем печатать «Ok».

Последующие блоки представляют собой инструкции из разных комбинаций состояний машины и букв входного алфавита. Большинство кусков кода используются множество раз. К примеру, когда мы написали все правила для символа I, и пишем для символа V, то мы можем написать (47,'V','>',52), (52,'I','>',48), где состояние 48 уже описано нами ранее.

И каков же результат? Вставим в качестве входной строки, скажем CCCXXIV (корректное число). Теперь набираем в консоли:

mysql> call turing(47,1) //

47 — начальное состояние, 1 — позиция управляющего устройства.

Получаем:

+--------------------------------------+

| CCCXXIV Ok |

+--------------------------------------+

Теперь попробуем некорректное число, скажем, MXXLC.
Получаем:

+----------------+

| MXXLC |

+----------------+

Все!

Подводим итоги

Данный вариант реализации эмулятора не идеален и может бесконечно дорабатываться и совершенствоваться. Это лишь прототип, демонстрирующий далеко не очевидные возможности применения MySQL. Ну и, разумеется, данная реализация создана исключительно ради спортивного интереса и веселого времяпрепровождения. Надеюсь, что вы также получили удовольствие от чтения этой статьи.

Побольше вам ненормальных идей и удачного программирования!
Tags:
Hubs:
+51
Comments 23
Comments Comments 23

Articles