Машина Тьюринга По Формулам Excel

Каждая ячейка содержит один символ.

В частности, пустая ячейка — это ячейка, в которой записан символ пустой ячейки.

Символы в ячейках принадлежат алфавиту этой машины.

По ленте едет головка, которая может находиться в нескольких состояниях, одно из состояний — окончание работы машины.

Головка считывает текущую ячейку и в зависимости от значения этой ячейки и ее текущего состояния меняет значение в текущей ячейке и затем либо перемещается вправо, либо перемещается влево, либо остается на месте.

Для запуска машины необходимо указать исходное состояние ленты, состояние головки и положение головки.

И, естественно, должен быть определен алфавит машины, состояние головы и правила.

Общее количество правил для головы должно быть определено N=(количество символов в алфавите)*(количество состояний -1).

Число состояний равно 1, поскольку правил для конечного состояния нет — машина останавливается.

То есть пустая лента вся заполнена символами «х».

Головка будет иметь 4 состояния: q1, q2, q3 и q4 – остановка машины.

Давайте выделим всю эту таблицу и назовем ее «правилами».

Нажмите Ввод.



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



Это значит, что на ленте записано число 10111, а головка находится в состоянии 1, и в ячейке, соответствующей старшей цифре.

Excel поддерживает условное форматирование, которое используется для большей ясности.

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

Описание формул Excel для машины Тьюринга Формула для ленточной ячейки: =ЕСЛИ(K14<> 0, ИНДЕКС(правила,К14+1,2+К13*3),К13) Это формула для значения ячейки ленты на следующем этапе (K17).

Это означает, что если головка (К14) расположена под ячейкой (т.е.

ячейка К14 не равна нулю), то в эту ячейку значение должно быть записано по правилам (из массива правил).

Если в ячейке под ячейкой ленты стоит ноль (а значит, под ней нет головки), то значение не меняется.

Формула состояния головы (для удобства чтения добавлены переносы строк): =ЕСЛИ(K14<> 0; ЕСЛИ(ИНДЕКС(правила,К14+1,4+К13*3)=0, ИНДЕКС(правила,К14+1,3+К13*3);0); ЕСЛИ(J14<> 0; ЕСЛИ(ИНДЕКС(правила,J14+1,4+J13*3)=1, ИНДЕКС(правила,J14+1,3+J13*3);0); ЕСЛИ(L14<> 0; ЕСЛИ(ИНДЕКС(правила,L14+1,4+L13*3)=-1, ИНДЕКС(правила,L14+1,3+L13*3),0),0))) Ээта формула 1) сначала проверяет, находится ли головка в этой ячейке (К14) - потом если в правилах написано оставаться на месте, в эту ячейку записывается состояние машины по правилам 2) Если голова находится на одну клетку левее (J14) и в правилах сказано двигаться вправо - то в этой ячейке записывается состояние машины по правилам 3) Если голова находится на одну клетку вправо (L14) и в правилах сказано двигаться влево - то в эту ячейку записывается состояние машины по правилам 4) Во всех остальных случаях пишите ноль Эта формула имитирует движение головы.

В формулах используется функция Индекс ( массив, строка, столбец ).

Рассчитаем значение ИНДЕКС(правила;К14+1;4+К13*3) - фрагмент формулы состояния головы.

Как видно из рисунка, К14=1, К13=1. Это значит, что нам нужно найти ИНДЕКС(правила;1+1;4+1*3), то есть ИНДЕКС(правила;2;7) — значение в массиве «правила» на пересечении 2-й строки и 7-й.

столбец (строки и столбцы нумеруются с 1, а не с 0).

В нашей таблице это значение равно «1».

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

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