Машина Тьюринга на формулах Excel

В статье кратко рассказывается о машине Тьюринга и приводится ее реализация на Exсel.
image

Что такое Машина Тьюринга

Машина Тьюринга представляет собой бесконечную ленту с ячейками. В каждой ячейке записан один символ. В частности, пустая ячейка – это ячейка с записанным в ней символом пустой ячейки. Символы в ячейках принадлежат алфавиту этой машины.
По ленте ездит головка, которая может пребывать в нескольких состояниях, причем одно из состояний – окончание работы машины. Головка считывает текущую ячейку и, в зависимости от значения этой ячейки и своего текущего состояния, меняет значение в текущей ячейке, а затем либо перемещается вправо, либо перемещается влево, либо остается на месте.
Для запуска машины нужно указать начальные состояние ленты, состояние головки и положение головки. И, естественно должен быть определен алфавит машины, состояния головки и правила.
Всего правил для головки должно быть определено N=(число символов в алфавите)*(число состояний -1). Число состояний-1 так как для конечного состояния правил нет – машина останавливается.

Простой пример: прибавление единицы к двоичному числу

Для такой машины потребуется алфавит из трех символов (0,1, х) – где 0 и 1 будут для числа, а х для пустой ячейки. То есть пустая лента вся заполнена символами «х».
У головки будет 4 состояния: q1,q2,q3 и q4 – остановка машины.
Правила для машины выпишем в виде матрицы:
image

Нетрудно проверить, что такая машина при помещении головки на старший разряд двоичного числа, при начальном состоянии q1, увеличит это число на 1.

Быстро и «грязно»: excel to html

Реализация на Excel

Создадим таблицу правил, как в примере выше. Выделим всю эту таблицу и назовем ее «rules». Жмем Enter.

image

Структура таблицы такая же, как в примере выше, c небольшими изменениями:
• состояния машины названы просто цифрами (без q)
• пустую ячейку означает символ «2»
• движение головки задано 1 – вправо, -1 – влево, 0 – на месте

Зададим начальное состояние ленты:
image

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

Описание формул Excel для машины Тьюринга

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

 

Заключение

Если бы Эксель поддерживал сколь угодно большое число строк и столбцов, то это автоматически означало бы, что используя формулы экселя можно реализовать любую вычислимую функцию, так как Excel был бы Тьюринг-полным.

Assembler в 30 строк на Excel

                                

Понравилась статья? Поделиться с друзьями: