Составление имитационной модели программы автомата Тьюринга.

 

Для моделирования задачи используем средства программы Excel Microsoft Office.

Необходимо построить модель на листе табличного редактора, используя возможности встроенных функций и условного форматирования.

Возможный вариант модели представлен на рисунке 23. (адреса ячеек не менять иначе неправильно будет работать программа).

Необходимо выполнить следующее:

1. Оформить таблицу машины Тьюринга согласно рисунка.(обязательно в заданных ячейках)(рис 11).Исходные данные таблицы взяты из задачи 1 и сведены в таблицу (рисунок 24) (см выше теоретическую часть).

 

Для других задач количество строк и столбцов может быть больше или меньше. Поэтому для решения новых задач необходимо таблицу откорректировать.

Для повышения наглядности необходимо выделить контуры ячеек таблицы толщиной и цветом по своему вкусу. Это делается командой Меню-Главная-Шрифт-Границы.

2. Оформить поясняющие ячейки программы согласно рисунка 23.

Ячейка A11-содержимое “ Пуск”

Ячейка A13-содержимое “ Шаг”

Ячейка A16-содержимое “ Исходная лента”

Ячейка A17-содержимое “ Головка”

Ячейка A20-содержимое “ Головка”

Ячейка A21-содержимое “Движение”

Ячейка A2-содержимое “Ячейка”

Ячейка I15 -содержимое “Исходные данные”

Ячейка I19 -содержимое “Машина Тьюринга”

Для повышения наглядности необходимо выделить контуры ячеек таблицы толщиной и цветом по своему вкусу. Это делается командой Меню→Главная→Шрифт→Границы.

3. Заполнить формулами управляющие ячейки (ОШИБКИ НЕДОПУСТИМЫ!!!):

3.1 Ячейка Пуск (ячейка B11) →управляющие формулы не нужны (в нее будем вносит 0 или 1 вручную).

3.2. Ячейка Шаг (ячейка B13)→вносим формулу.

=ЕСЛИ(D11=2;"конец";ЕСЛИ(D11;ЕСЛИ(C11=1;СУММ(B13;1);B13);"начало"))

3.3. Изображение ленты с заданным на ней числом→ указываем вручную заданное число в любом месте ленты (ячейки B16-AH16).

3.4. Изображение начального положения головки (обязательно над числом в любом месте) цифрой “1”(указываем вручную) (ячейки B17-AH17).

3.5. Изображение действующей ленты с ячейками состояния (для ячейки B20)

=ЕСЛИ($D$11=2;B20;ЕСЛИ($D$11;ЕСЛИ($C$11=4;;ЕСЛИ($C$11=1;ЕСЛИ(B24;ВПР(B24;$A$3:$J$5;ПОИСКПОЗ(B23;$A$1:$J$1;)+1;);B20);B20));))

Необходимо заполнить формулами ячейки B20-AH20.

Для упрощения ввода используем метод протаскивания.

Для этого необходимо к заполненной формулой ячейке B20 подвести мышку к правому нижнему углу ячейки. После появления крестика нажать левую клавишу мышки и протащить вправо до ячейки AH20 и отпустить кнопку мышки. Ячейки будут заполнены.

У адресов ячеек где проставлен знак $ при протаскивании адреса не изменяться.

3.6. Изображение действующей ленты с ячейками движения(для ячейки B21)

=ЕСЛИ($D$11=2;B21;ЕСЛИ($D$11;ЕСЛИ($C$11=4;;ЕСЛИ($C$11=1;ЕСЛИ(B24;ВПР(B24;$A$3:$J$5;ПОИСКПОЗ(B23;$A$1:$J$1;)+2;);B21);B21));))

Необходимо заполнить формулами ячейки ячейки B21-AH21 методом протаскивания.

3.7. Изображение действующей ленты с ячейками числа (для ячейки B22)

=ЕСЛИ($D$11=2;B22;ЕСЛИ($D$11;ЕСЛИ($C$11=4;B22;ЕСЛИ($C$11=1;ЕСЛИ(B24;ВПР(B24;$A$3:$J$5;ПОИСКПОЗ(B23;$A$1:$J$1;););B22);B22));ЕСЛИ(B16="";"x";B16)))

Необходимо заполнить формулами ячейки B22-AH22 методом протаскивания.

3.8. Изображение действующей ленты с ячейками текущего числа ленты (для ячейки B23)

=ЕСЛИ($D$11=2;B23;ЕСЛИ($D$11;ЕСЛИ($C$11=3;B22;B23);B22))

Необходимо заполнить формулами ячейки B23-AH23 методом протаскивания.

3.9.Ячейки номера состояния головки (для ячейки B24)

=ЕСЛИ($D$11=2;B24;ЕСЛИ($D$11=1;ЕСЛИ($C$11=2;ЕСЛИ(A21=1;A20;ЕСЛИ(C21=-1;C20;));B24);B17))

Необходимо заполнить формулами ячейки B24-AH24 методом протаскивания.

3.10. Ячейка для промежуточной информации о положении программы (ячейка D11) =ЕСЛИ(B11;ЕСЛИ(МАКС(B24:AH24)=МАКС($A$3:$A$7)+1;2;B11);)

3.11. Ячейка для промежуточной информации о шаге выполнения (ячейка С11) =ЕСЛИ(D11;ЕСЛИ(C11=4;1;C11+1);1)

Ячейки D11 и C11 являются служебными, поэтому информацию желательно скрыть. Для этого выделяем ячейки → правая клавиша мышки до появления всплывающего меню (контекстное меню)→ Формат ячеек → Шрифт → Белый.

Также в дальнейшем можно скрыть вспомогательную информацию ячеек (головки, движения и ячейки).Для этого выделяем вертикальные ячейки левого края листа Excel с номерами 20,21,22 и нажав левую клавишу мышки в контекстом меню выбираем Скрыть. Обратно можно восстановить информацию, выделив граничные ячейки левого края листа Excel и в контекстном меню активировать Показать.

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