В статье кратко рассказывается о машине Тьюринга и приводится ее реализация на Exсel. Полезна статья будет и тем, кто хочет познакомиться с машиной Тьюринга, и тем, кто хочет повысить свой кругозор в функционале Excel.
Что такое Машина Тьюринга
Машина Тьюринга представляет собой бесконечную ленту с ячейками. В каждой ячейке записан один символ. В частности, пустая ячейка – это ячейка с записанным в ней символом пустой ячейки. Символы в ячейках принадлежат алфавиту этой машины.
По ленте ездит головка, которая может пребывать в нескольких состояниях, причем одно из состояний – окончание работы машины. Головка считывает текущую ячейку и, в зависимости от значения этой ячейки и своего текущего состояния, меняет значение в текущей ячейке, а затем либо перемещается вправо, либо перемещается влево, либо остается на месте.
Для запуска машины нужно указать начальные состояние ленты, состояние головки и положение головки. И, естественно должен быть определен алфавит машины, состояния головки и правила.
Всего правил для головки должно быть определено N=(число символов в алфавите)*(число состояний -1). Число состояний-1 так как для конечного состояния правил нет – машина останавливается.
Простой пример: прибавление единицы к двоичному числу
Для такой машины потребуется алфавит из трех символов (0,1, х) – где 0 и 1 будут для числа, а х для пустой ячейки. То есть пустая лента вся заполнена символами «х».
У головки будет 4 состояния: q1,q2,q3 и q4 – остановка машины.
Правила для машины выпишем в виде матрицы:
Нетрудно проверить, что такая машина при помещении головки на старший разряд двоичного числа, при начальном состоянии q1, увеличит это число на 1.
Реализация на Excel
Создадим таблицу правил, как в примере выше. Выделим всю эту таблицу и назовем ее «rules». Жмем Enter.
Структура таблицы такая же, как в примере выше, c небольшими изменениями:
• состояния машины названы просто цифрами (без q)
• пустую ячейку означает символ «2»
• движение головки задано 1 – вправо, -1 – влево, 0 – на месте
Зададим начальное состояние ленты:
Оно означает, что на ленте записано число 10111, а головка находится в состоянии 1, и в ячейке, соответствующей старшему разряду. Excel поддерживает условное форматирование, что и применено для большей наглядности.
Новый шаг машины будет моделироваться новыми строками эксель, а формулы будут имитировать состояние машины согласно правилам.
=ЕСЛИ(K14<>0; ИНДЕКС(rules;K14+1;2+K13*3);K13)
Эта формула для значения ячейки ленты на следующем шаге (K17). Она означает, что если головка (K14) находится под ячейкой (то есть в клетке K14 не ноль), то следует записать в эту ячейку значение согласно правилам (из массива rules). Если же в клетке под ячейкой ленты ноль (что значит, под ней нет головки), то значение не меняется.
Формула для состояния головки (для удобства чтения сделаны переносы строки):
=ЕСЛИ(K14<>0; ЕСЛИ(ИНДЕКС(rules;K14+1;4+K13*3)=0; ИНДЕКС(rules;K14+1;3+K13*3);0);
ЕСЛИ(J14<>0; ЕСЛИ(ИНДЕКС(rules;J14+1;4+J13*3)=1; ИНДЕКС(rules;J14+1;3+J13*3);0);
ЕСЛИ(L14<>0; ЕСЛИ(ИНДЕКС(rules;L14+1;4+L13*3)=-1; ИНДЕКС(rules;L14+1;3+L13*3);0);0)))
Эта формула
1) сначала проверяет, находится ли головка в этой ячейке (K14) – тогда если правила говорят оставаться на месте, в эту клетку пишется состояние машины согласно правилам
2) Если головка находится на одну ячейку влево (J14) и правила говорят сдвинуться вправо – тогда в эту клетку пишется состояние машины согласно правилам
3) Если головка находится на одну ячейку справа (L14) и правила говорят сдвинуться влево – тогда в эту клетку пишется состояние машины согласно правилам
4) Во всех остальных случаях пишется ноль
Такая формула имитирует движение головки.
В формулах использована функция Индекс(массив, строка, столбец). Вычислим значение ИНДЕКС(rules;K14+1;4+K13*3) – кусочка формулы состояния головки.
Как видно из рисунка, K14=1, K13=1. Значит надо найти ИНДЕКС(rules;1+1;4+1*3) то есть ИНДЕКС(rules;2;7) – значение в массиве «rules» на пересечении 2й строки и 7го столбцы (нумеруются строки и столбцы начиная с 1, а не 0). В нашей табличке это значение «1».
Формулы относительные – то есть при копировании их на новые ячейки эксель берет данные из ячеек соответствующий предыдущему состоянию машины.
В итоге, выполнив все шаги, машина «останавливается» — достигнуто состояние «4», к числу прибавлена единица.
Вот ссылка на файл Excel
Заключение
Если бы Эксель поддерживал сколь угодно большое число строк и столбцов, то это автоматически означало бы, что используя формулы экселя можно реализовать любую вычислимую функцию, так как Excel был бы Тьюринг-полным
P.S. Задача на смекалку: измените правила описанной в статье машины Тьюринга так, чтобы она уменьшала двоичное число на 1.
Автор: ITguru
