2015-06-05
4522
На примере машины Тьюринга хорошо прослеживаются свойства алгоритмов. Попросите учащихся показать, что машина Тьюринга обладает всеми свойствами алгоритма.
Дискретность. Машина Тьюринга может перейти к (к + 1)-му шагу только после выполнения к- го шага, т.к. именно к- й шаг определяет, каким будет (к + 1)-й шаг.
Понятность. На каждом шаге в ячейку пишется символ из алфавита, автомат делает одно движение (Л, П, Н), и машина Тьюринга переходит в одно из описанных состояний.
Детерминированность. В каждой клетке таблицы машины Тьюринга записан лишь один вариант действия. На каждом шаге результат определен однозначно, следовательно, последовательность шагов решения задачи определена однозначно, т.е. если машине Тьюринга на вход подают одно и то же входное слово, то выходное слово каждый раз будет одним и тем же.
Результативность. Содержательно результаты каждого шага и всей последовательности шагов определены однозначно, следовательно, правильно написанная машина Тьюринга за конечное число шагов перейдет в состояние q 0, т.е. за конечное число шагов будет получен ответ на вопрос задачи.
|
|
|
Массовость. Каждая машина Тьюринга определена над всеми допустимыми словами из алфавита, в этом и состоит свойство массовости. Каждая машина Тьюринга предназначена для решения одного класса задач, т.е. для каждой задачи пишется своя (новая) машина Тьюринга.
3Практическая часть
Задача 3.1 Выяснить, применима ли машина Тьюринга T к слову P. Если применима, то выписать результат T(P) применения машины Тьюринга T к слову P.
q1 1 q1 0 R
q1 0 q3 0 L
T: q2 0 q2 1 L
q3 1 q2 1 R
q3 0 q3 1 E
P=11111001
Предполагается, что начальный момент Машина Тьюринга обозревает самую левую единицу слова.
Решение. По определению команд машины Тьюринга получаем последовательность конфигураций
q1 11111001
q1 1111001
q1 111001
q1 11001
q1 1001
q1 001
q3 0001
q3 1001
1 q2 001
q2 1101
Так как команда, начинающаяся символами q2 1 в программе отсутствует, то последняя конфигурация является заключительной. Следовательно, машина Тьюринга применима к слову P и T(P)=1101
Задача 3.2 Требуется построить машину Тьюринга, которая прибавляет единицу к числу на ленте. Входное слово состоит из цифр целого десятичного числа, записанных в последовательные ячейки на ленте. В начальный момент машина находится против самой правой цифры числа.
Решение. Машина должна прибавить единицу к последней цифре числа. Если последняя цифра равна 9, то ее заменить на 0 и прибавить единицу к предыдущей цифре. Программа для данной машины Тьюринга может выглядеть так:
| … | |||||||||
| 1 H 
| 1 H
| 2 H
| 3 H
| 4 H
| 5 H
| … | 8 H
| 9 H
| 0 Л
|
В этой машине Тьюринга q 1 — состояние изменения цифры, q 0 — состояние останова. Если в состоянии ql автомат видит цифру 0..8, то он заменяет ее на 1..9 соответственно и переходит в состояние q 0, т.е. машина останавливается. Если же он видит цифру 9, то заменяет ее на 0, сдвигается влево, оставаясь в состоянии ql. Так продолжается до тех пор, пока автомат не встретит цифру меньше 9. Если же все цифры были равны 9, то он заменит их нулями, запишет 0 на месте старшей цифры, сдвинется влево и в пустой клетке запишет 1. Затем перейдет в состояние q 0, т.е. остановится.
|
|
|
