3512
.pdf
31
ж) 11а0а0111111; з) 11a0111.
Решение:
д) Выписываем последовательность конфигураций машины при переработке ею слова 111 из начального стандартного положения:
1) |
|
|
|
q1 |
||
|
|
1 |
1 |
1 |
|
|
2) |
|
|
q2 |
|
|
|
|
|
1 |
1 |
1 |
|
|
3) |
|
q3 |
|
|
|
|
|
|
1 |
1 |
1 |
|
|
4) |
q1 |
|
|
|
|
|
|
|
1 |
1 |
1 |
|
|
5) |
|
q4 |
|
|
|
|
|
|
1 |
1 |
1 |
|
|
6) |
|
q5 |
|
|
|
|
|
|
|
1 |
1 |
|
|
7) |
|
|
q4 |
|
|
|
|
|
|
1 |
1 |
|
|
8) |
|
|
q5 |
|
|
|
|
|
|
|
1 |
|
|
9) |
|
|
|
q4 |
||
|
|
|
|
1 |
|
|
10) |
|
|
|
q5 |
||
|
|
|
|
|
|
|
11) |
|
|
|
|
q4 |
|
|
|
|
|
|
|
|
12) |
|
|
|
|
q0 |
|
|
|
|
|
|
1 |
|
Итак, слово 111 из начального стандартного положения перерабатывается машиной в слово 1.
Задачи и упражнения для самостоятельного решения
1. Машина Тьюринга определяется следующей функциональной схемой:
Q |
q1 |
q2 |
q3 |
q4 |
A |
|
|
|
q0a0Л |
a0 |
q4a0П |
q3a0Л |
q1a0П |
|
1 |
q2α |
q1β |
q11П |
q11Л |
α |
q1αЛ |
q2αП |
q31Л |
q4a0П |
β |
q1βЛ |
q2βП |
q3a0Л |
q41П |
32
Для следующих слов определите, в какое слово переработается каждое из них данной машиной, исходя из начального положения, при котором машина находится в состоянии q1 и обозревается указываемая ячейка:
а) 11111 (обозревается ячейка 2, считая слева); б) 111 (обозревается ячейка 1); в) 1111111111 (обозревается ячейка 4); г) 111111 (обозревается ячейка 2);
д) 111111111111111 (обозревается ячейка 6).
Какова общая закономерность работы машины?
2.Машина Тьюринга с внешним алфавитом А = {а0, 1} определяется следующей программой:
Q |
q1 |
q2 |
q3 |
A |
|
|
q0a0 |
a0 |
q2a0П |
q2a0П |
|
1 |
q11П |
q31П |
q31П |
Остановится ли когда-нибудь эта машина, если она начнет перерабатывать следующее слово (в начальный момент, в состоянии q1 машина обозревает ячейку, в которой записана самая левая буква перерабатываемого слова):
a) 111a0 a01; б) 11а0a011a01; в) 111111;
г) 1a0a0a0a01; д) 11a0a011; е) 1;
ж) 1a01a01a01; з) 111;
и) 1a01a01; к) 11a011.
Если остановка происходит, то какое слово получается в результате, какая ячейка и в каком (перед остановкой) состоянии обозревается?
33
Библиографический список
Основная литература
1.Игошин, В. И. Математическая логика и теория алгоритмов [Текст] : учеб. пособие для студ. высш. учеб. заведений / В. И. Игошин. – 2-е изд., стер. – М. : Издательский центр «Академия», 2008. – 448 с.
2.Набебин А. А. Математическая логика и теория алгоритмов [Текст] : доп. УМО вузов Рос. Федерации по унив. политехн. образованию в качестве учеб. пособия для студентов.- М. : Науч. Мир, 2008.- 343с.
Дополнительная литература
3.Поздняков С.Н. Дискретная математика [Текст]: доп. М-вом образования и науки Рос. Федерации / С.Н.Поздняков, С.В. Рыбин. - М.: Издат. центр
«Академия», 2008 г. - 448 с.
4.Игошин, В.И. Задачи и упражнения по математической логике и теории алгоритмов [Текст] : учеб. пособие для студ. высш. учеб. заведений / В.И.Игошин. — 3-е изд., стер. — М. : Издательский центр «Академия», 2007. — 304 с.
|
34 |
|
Оглавление |
Введение....................................................................................................................... |
3 |
Лабораторная работа № 1.................................................................................. |
.......4 |
Лабораторная работа № 2........................................................................................... |
9 |
Лабораторная работа № 3................................................... |
....................................18 |
Лабораторная работа № 4......................................................................................... |
27 |
Библиографический список...................................................................................... |
33 |
35
Хухрянская Елена Станиславовна
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Методические указания к выполнению лабораторных работ для студентов направления 230400.62 - Информационные системы и технологии
Редактор _______________
Подписано в печать __.__.20__. Формат 60×90/16. Объем ___ п. л. Усл. печ. л. ___. Уч.-изд. л. ____. Тираж ____ экз. Заказ
ГОУ ВПО «Воронежская государственная лесотехническая академия» РИО ГОУ ВПО «ВГЛТА». 394087, г. Воронеж, ул. Тимирязева, 8 Отпечатано в УОП ГОУ ВПО «ВГЛТА». 394087, г. Воронеж, ул. Докучаева, 10