Практическая часть лабораторной работы.
1. Создать имитационную модель машины Тьюринга.
1.1. Выбираем задачу:
Прибавить единицу к существующему целому положительному двоичному числу.
Решение этой задачи рассмотрено в примере 1 теоретической части (см. выше).
По условиям задачи число может быть любой размерности в пределах ограничения
ленты автомата (у нас ограничения в пределах листа программы Excel).
Поэтому необходимо задаться определенной длиной ленты по своему усмотрению, чтобы задача решалась.
Сама задача решена, то есть составлена таблица автомата Тьюринга.
Нам осталось создать имитационную модель с помощью программы Excel.
Сложность реализации будет заключаться в отказе от встроенного языка программирования VBA.Поставленную задачу необходимо реализовать с помощью встроенных функций и условного форматирования ячеек электронной таблицы Excel Microsoft Office.
Но даже ограниченные средства реализации позволяют построить действующую имитационную модель автомата Тьюринга.
1.2. Составляем текстовый алгоритм выполнения задачи по шагам:
1. Начальное положение программы “0” →вводим исходные данные на ленту и определяем положение головки цифрой “1” в клетке под записанными данными на ленте .
2. Запускаем программу →положение программы “1”.
3. Оцениваем содержимое ячейки ленты над головкой и состояние головки.
4. По результатам оценки находим в таблице автомата Тьюринга данные о новом состоянии, новом движении головки и новом содержимом ячейки над головкой.
5. Сдвигаем головку в нужном направлении, одновременно изменяя ее состояние. При этом записываем нужную информацию в ячейку ленты.
6. Если состоянии головки равно наибольшей строке таблицы+1, то изменяем положение программы на “2” и останавливаем программу выполнения.
Остается уточнить детали алгоритма и составить формулы для нужных ячеек электронной таблицы.
Составим подробный текстовый алгоритм по минимальным шагам выполнения программы, так как некоторые описанные выше пункты не решаются за один шаг в силу ограниченности формул Excel:
1. Начальное положение программы “0” →вводим исходные данные на ленту и определяем положение головки цифрой “1” (Ручной ввод информации).
2. Запускаем программу →положение программы “1”.(добавляем в определенную ячейку “1” вместо “0”)
3. Оцениваем содержимое ячейки ленты над головкой, состояние головки и находим в таблице автомата Тьюринга данные о новом состоянии головки, новом движении головки и новом содержимом ячейки числа (“0” или “1” или пустота (обозначим ее “х”) над головкой (добавляем три новых ячейки информации для каждого положения головки, помимо ячеек информации ленты) (это Шаг 1)
4. Сдвигаем головку в нужном направлении, одновременно изменяя ее состояние. (это Шаг 2).
5. Переписываем содержимое новой ячейки числа в ячейку ленты там, где была головка.
6. Обнуляем ячейки состояния головки и состояния движения. Ячейки состояния числа сохраняем(там остаточная информация (ее не обнуляем)).
7. Далее повторяем пункты 3÷6 пока состояние головки не станет максимальным (равным наибольшей строке таблицы автомата Тьюринга +1).
8. Если состоянии головки равно наибольшей строке таблицы+1, то изменяем положение программы на “2” и останавливаемся.
 |
1.3 Определимся (ориентировочно) с информационными ячейками на листе Excel и добавим управляющие формулы. Должно быть следующее:
1. Таблица автомата Тьюринга для всех элементов алфавита и всех состояний головки (кроме состояния останова программы - обычно его не пишут ввиду повторяемости ячеек с одинаковым содержимым). (ячейки A1-J5(по диагонали)) управляющие формулы не нужны (мы будем ссылаться на эту таблицу) (рис 8).
2. Ячейка Пуск (ячейка B11) →управляющие формулы не нужны (в нее будем вносит 0 или 1 вручную).
3. Ячейка Шаг (ячейка B13)→вносим формулу.
=ЕСЛИ( D11=2;"конец";ЕСЛИ(D11;ЕСЛИ(C11=1;СУММ(B13;1);B13);"начало"))
Блок-схема действия формулы представлена на рисунке 9:
4. Изображение ленты с заданным на ней числом→ указываем вручную заданное число в любом месте ленты (ячейки B16-AH16).
5. Изображение начального положения головки (обязательно над числом в любом месте) цифрой 1-указываем вручную. (ячейки B17-AH17)
6. Изображение действующей ленты с ячейками состояния (для ячейки 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));))
Блок-схема действия формулы представлена на рисунке 10:
Необходимо заполнить подобными формулами ячейки B20-AH20с учетом их относительных адресов.
У адресов ячеек где проставлен знак $ при протаскивании адреса не изменяться.
7. Изображение действующей ленты с ячейками движения(для ячейки 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));))
Блок-схема действия формулы представлена на рисунке 11:
Необходимо заполнить подобными формулами ячейки B21-AH21 с учетом их относительных адресов .
8. Изображение действующей ленты с ячейками числа (для ячейки 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)))
Блок-схема действия формулы представлена на рисунке 12.
Необходимо заполнить подобными формулами ячейки B22-AH22с учетом их относительных адресов.
9. Изображение действующей ленты с ячейками текущего числа ленты (для ячейки B23)
=ЕСЛИ($D$11=2;B23;ЕСЛИ($D$11;ЕСЛИ($C$11=3;B22;B23);B22))
Блок-схема действия формулы представлена на рисунке 13:
Необходимо заполнить подобными формулами ячейки B23-AH23 с учетом их относительных адресов.
10.Ячейки номера состояния головки (для ячейки B24)
=ЕСЛИ($D$11=2;B24;ЕСЛИ($D$11=1;ЕСЛИ($C$11=2;ЕСЛИ(A21=1;A20;ЕСЛИ(C21=-1;C20;));B24);B17))
Блок-схема действия формулы представлена на рисунке 14:
Необходимо заполнить подобными формулами ячейки B24-AH24 с учетом их относительных адресов.
11. Ячейка для промежуточной информации о положении программы (ячейка D11) =ЕСЛИ(B11;ЕСЛИ(МАКС(B24:AH24)=МАКС($A$3:$A$7)+1;2;B11);)
Блок-схема действия формулы представлена на рисунке 15:
12. Ячейка для промежуточной информации о шаге выполнения (ячейка С11) =ЕСЛИ(D11;ЕСЛИ(C11=4;1;C11+1);1)
Блок-схема действия формулы представлена на рисунке 16:
1.4 Применим условное форматирование для выделения ячеек цветом и придание анимационного эффекта работы действующей модели.
1.4.1 Ячейка B11(старт)- Условное форматирование → Создать правило→ Использовать формулу для определения форматируемых ячеек.
В поле Измените описание правила задаем условия и формат правила:
=$B$13="конец"
В разделе “Применяется к” добавим:=$B$13:$C$13;$B$11
В качестве формата выбираем красную заливку.
Создаем здесь второе правило→Создать правило→Использовать формулу для определения форматируемых ячеек.
В поле Измените описание правила задаем условия и формат правила.
В нашем случае, условием будет формула: =$B$13="начало"
В разделе “Применяется к” добавим:=$B$13:$C$13;$B$11
В качестве формата выбираем желтую заливку.
1.4.2.Ячейка B13 (Счетчик тактов) Условное форматирование → Создать правило→ Использовать формулу для определения форматируемых ячеек.
В поле Измените описание правила задаем условия и формат для правила.
В нашем случае, условием будет формула: =$B$13="конец"
В разделе “Применяется к” добавим:=$B$13:$C$13;$B$11
В качестве формата выбираем красную заливку.
Создаем здесь второе правило→Создать правило→Использовать формулу для определения форматируемых ячеек.
В поле Измените описание правила задаем условия и формат для нашего правила.
В нашем случае, условием будет формула: =$B$13="начало"
В разделе “Применяется к” добавим:=$B$13:$C$13;$B$11
В качестве формата выбираем желтую заливку.
3. Ячейка B23 (лента)→ Условное форматирование → Создать правило→ Форматировать только ячейки, которые содержат.
В поле Измените описание правила задаем условия и формат для правила.
В первом разделе выберем: Значение ячейки
Во втором разделе выберем: Равно
В нашем случае, условием будет формула: ="x"
В качестве формата выбираем серую заливку.
В разделе “Применяется к” добавим:=$B$23:$AH$23
4. Ячейка B24 (головка). Условное форматирование → Создать правило→ Использовать формулу для определения форматируемых ячеек.
В поле Измените описание правила задаем условия и формат для правила.
В нашем случае, условием будет формула: =B24=МАКС($A$3:$A$10)+1
В разделе “Применяется к” добавим:=$B$24:$AH$24
В качестве формата выбираем красную заливку.
Создаем второе правило→Создать правило→Форматировать только ячейки, которые содержат.
В поле Измените описание правила задаем условия и формат для правила.
В первом разделе выберем: Значение ячейки
Во втором разделе выберем: Больше
В нашем случае, условием будет формула: =0
В качестве формата выбираем темно-красную заливку.
В разделе “Применяется к” добавим:=$B$24:$AH$24