Что такое Машина Тьюринга
Машина Тьюринга представляет собой бесконечную ленту с ячейками. В каждой ячейке записан один символ. В частности, пустая ячейка – это ячейка с записанным в ней символом пустой ячейки. Символы в ячейках принадлежат алфавиту этой машины.
По ленте ездит головка, которая может пребывать в нескольких состояниях, причем одно из состояний – окончание работы машины. Головка считывает текущую ячейку и, в зависимости от значения этой ячейки и своего текущего состояния, меняет значение в текущей ячейке, а затем либо перемещается вправо, либо перемещается влево, либо остается на месте.
Для запуска машины нужно указать начальные состояние ленты, состояние головки и положение головки. И, естественно должен быть определен алфавит машины, состояния головки и правила.
Всего правил для головки должно быть определено 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 поддерживает условное форматирование, что и применено для большей наглядности.
Новый шаг машины будет моделироваться новыми строками эксель, а формулы будут имитировать состояние машины согласно правилам.
Формулы относительные – то есть при копировании их на новые ячейки эксель берет данные из ячеек соответствующий предыдущему состоянию машины.
В итоге, выполнив все шаги, машина «останавливается» — достигнуто состояние «4», к числу прибавлена единица.
Заключение
Если бы Эксель поддерживал сколь угодно большое число строк и столбцов, то это автоматически означало бы, что используя формулы экселя можно реализовать любую вычислимую функцию, так как Excel был бы Тьюринг-полным.
