Лаба 1 Машины Тьюринга / ais_Laba_1
.docБГУИР
ФИТиУ
ОТЧЕТ
по дисциплине «Алгоритмы и алгоритмическая сложность»
лабораторная работа №1
«Машины Тьюринга»
Выполнили:
Арлынах
Проверила
Хаджинова Н. В.
Минск
2007
Практическое занятие «Машины Тьюринга»
Цель работы: целью данного занятия является закрепление знаний по построению и работе машин Тьюринга, которые являются математическими (формальными) моделями алгоритмов.
Ход работы
В ходе работы мы закрепили знания по построению и работе машин Тьюринга, которые являются математическими моделями алгоритмов.
Было выполнено:
Задание 1. Построить таблицу машины Тьюринга, которая заменяет все единицы на нули, а все нули на единицы. Пример. Исходное число 111001. Результат – 000110.
Решение
1 |
ε |
0 |
1 |
Q1 |
εUQfin |
1LQ1 |
0LQ1 |
Задание 2. Построить таблицу машины Тьюринга, которая удаляет из числа все нули, например, число 1001110 преобразует к виду 1111. Эта задача уже сложнее и требует ввести в рассмотрение более двух состояний.
Решение
2 |
ε |
0 |
1 |
Q1 |
εRQ2 |
0LQ1 |
1LQ1 |
Q2 |
εUQfin |
0LQ3 |
1RQ2 |
Q3 |
εRQ4 |
1LQ2 |
0RQ3 |
Q4 |
|
εRQ2 |
|
Задание 3. Построить машину, имеющую два конечных состояния, условно обозначаемых как YES и NO. Машина должна завершить работу в состоянии YES, если число единиц в записи числа нечетное, и в состоянии NO – в противном случае.
Решение
3 |
ε |
0 |
1 |
Q1 |
εUQN |
0LQ1 |
1LQ2 |
Q2 |
εUQY |
0LQ2 |
1LQ1 |
Задание 4. Построить машину, имеющую два конечных состояния, условно обозначаемых как YES и NO. Машина должна завершить работу в состоянии YES, если в записи числа имеется три подряд идущих единицы, и в состоянии NO – в противном случае.
Решение
4 |
ε |
0 |
1 |
Q1 |
URQN |
0LQ1 |
1LQ2 |
Q2 |
UUQN |
0LQ1 |
1RQ3 |
Q3 |
URQN |
0LQ1 |
UUQY |
Задание 5. Построить машину Тьюринга, которая получает обратный порядок записи числа, например, исходное число 111001, результат 100111.
Решение
5 |
ε |
0 |
1 |
Q1 |
εLQ22 |
εRQ2 |
εRQ11 |
Q2 |
0LQ3 |
|
|
Q3 |
εLQ4 |
|
|
Q4 |
εRQ5 |
0LQ4 |
1LQ4 |
Q5 |
|
εLQ6 |
εLQ14 |
Q6 |
0RQ7 |
|
|
Q7 |
εRQ8 |
|
|
Q8 |
εLQ1 |
0RQ8 |
1RQ8 |
Q9 |
εLQ10 |
|
|
Q10 |
εRQ11 |
0LQ10 |
1LQ10 |
Q11 |
1LQ9 |
εLQ18 |
εLQ12 |
Q12 |
1RQ13 |
|
|
Q13 |
εRQ8 |
|
|
Q14 |
0RQ15 |
|
|
Q15 |
εRQ16 |
|
|
Q16 |
εRQ17 |
0RQ16 |
1RQ16 |
Q17 |
εLQ1 |
1LQ17 |
|
Q18 |
1RQ19 |
|
|
Q19 |
εRQ20 |
|
|
Q20 |
εRQ21 |
0RQ20 |
1RQ20 |
Q21 |
0LQ21 |
εLQ22 |
0LQ8 |
Q22 |
εRQ24 |
0RQ21 |
1RQ23 |
Q23 |
1LQ23 |
|
εLQ22 |
Q24 |
εRQ25 |
|
|
Q25 |
εRQ26 |
0RQ25 |
1RQ25 |
Q26 |
εUQfin |
0LQ27 |
0LQ28 |
Q27 |
0RQ27 |
εRQ26 |
|
Q28 |
1RQ28 |
εRQ26 |
|
Задание 6. Построить машину Тьюринга, которая меняет местами соседние два элемента попарно. Пример. Исходное число 011001 заменяется на 100110.
Решение
6 |
ε |
0 |
1 |
Q1 |
εUQfin |
0LQ2 |
1LQ5 |
Q2 |
|
0LQ1 |
0RQ3 |
Q3 |
|
1LQ4 |
1LQ1 |
Q4 |
|
0LQ1 |
1LQ1 |
Q5 |
|
1RQ6 |
1LQ1 |
Q6 |
|
|
0LQ3 |