Лекции - Теория алгоритмов
Подождите немного. Документ загружается.
Лекция № 5. Машины Тьюринга
► Другой способ для обоснования
понятия алгоритма предложили
независимо друг от друга и почти
одновременно с Черчем и Клини
английский математик А. Тьюринг
и американский математик Э.
Пост.
► Основная идея Поста и Тьюринга
заключалась в том, что
алгоритмические процессы - это
процессы, которые может
совершать некоторая «машина».
► Машины, введенные Постом и
Тьюрингом, имеют не очень
существенное различие и обычно
называются машинами Тьюринга.
Описание машины Тьюринга
Машина Тьюринга - это воображаемое вычислительное
устройство, имеющее следующие составные части.
Оно имеет ленту, разбитую на ячейки, и каретку,
расположенную в каждый конкретный момент работы
машины над некоторой ячейкой ленты.
Описание машины Тьюринга
(продолжение)
► Каждая ячейка содержит ровно один из символов 0 или 1. Лента
представляется конечной, но дополняемой в любой момент
ячейками слева и справа для записи новых символов 0 или 1. Эта
ситуация может возникнуть при сдвиге каретки влево или вправо
за край ленты. Тогда наращивается новая клетка с содержимым 0.
Это соглашение отражает идею о сколь угодно большой, но
конечной памяти.
► Если каретка, расположена над некоторой ячейкой с символом 0
(с символом 1), то говорим, что каретка обозревает символ 0
(обозревает символ 1).
Программы машины Тьюринга
► Машина Тьюринга имеет программу. Это
конечная последовательность инструкций q
1
,
q
2
, ... ,q
n
, каждая из которых является строкой
из 5 компонент:
(i, a, x, y, z ),
где i – номер инструкции;
a =0, или a=1;
x=0, или x=1;
у= L или y=R;
z – номер инструкции.
Выполнение инструкции
Рассмотрим как выполняется инструкция
(i, a, x, y, z )
с номером i.
1) Машина смотрит обозреваемый кареткой
символ. Если он равен 0, то исполняется команда
(i, 0,x,y,z),
если обозреваемый символ равен 1, то исполняется
команда
(i,1,x,y,z).
Если команды с таким началом нет, то машина
останавливается. Это единственное условие остановки
машины Тьюринга.
Выполнение инструкции
(продолжение)
► 2) Запись в обозреваемую ячейку величины x. Поэтому
содержимое обозреваемой ячейки останется прежним
или сменится на противоположное, например, 0
заменится на 1.
► 3) Сдвиг каретки на одну ячейку влево при y=L или
вправо при y=R.
► 4) Переход к инструкции с номером z.
► Выполнение инструкции с номером i, т. е. выполнение
пунктов 1) – 4) считается одним тактом работы
машины.
Пример работы программы
► Пример. Пусть дана машина Тьюринга
с программой из одной инструкции
( 0, 0, 1, R, 0 ).
Описать работу машины со следующими входными
данными: на ленте во всех ячейках расположен
символ 0.
Пример работы программы
(продолжение)
► Решение.
► 1) Обозреваемый кареткой символ равен 0.
Поэтому продолжаем выполнять эту
инструкцию.
► 2) Записываем в обозреваемую ячейку
величину x, находящуюся в третьей ячейке
инструкции, т е. 1. Поэтому содержимое
обозреваемой ячейки заменится на 1.
► 3) Сдвигаем каретку на одну ячейку вправо.
► 4) Переходим к инструкции с номером 0, то
есть повторяем предыдущую инструкцию снова.
Пример работы программы
(продолжение)
► После первого такта
работы программы
машина перейдет в
состояние (см.
верхний рисунок).
► Каретка движется
вправо, машина
Тьюринга работает
бесконечно,
заполняя ячейки
ленты символом 1.
Вычисление значений функций
► Рассмотрим алгоритм вычисления значений функций на
машине Тьюринга. Сначала договоримся о
представлении натуральных чисел на ленте:
► 1) натуральное число 0 будем изображать одной
единицей, число 1 – двумя единицами, и т. д.,
натуральное число x – (x+1) - ой единицей: