Лекции - Теория алгоритмов
Подождите немного. Документ загружается.
Вычисление значений функций
(продолжение)
►2) Для изображения упорядоченной
последовательности (x
1
, x
2
, ... , x
n
) будем
каждую группу единиц отделять друг от
друга нулем.
►Пример. Так выглядит на ленте тройка
чисел (3, 1, 10):
1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1
Вычисление значений функций
(продолжение)
► Пусть дана n-арная функция f(x
1
,x
2
, ... , x
n
). Будем
говорить, что машина Тьюринга
M
вычисляет
функцию
f,
если выполняются следующие условия.
1. Пусть строка (x
1
,x
2
, ... , x
n
) содержится в области
определения функции
f
. Тогда машина
M,
начиная
работать и обозревая левую единицу строки (x
1
,x
2
, ... ,
x
n
) (остальная часть ленты пуста), на некотором
шаге останавливается, обозревая левую единицу
строки f(x
1
,x
2
, ... , x
n
) (часть ленты справа от строки
пуста).
2. Пусть строка (x
1
,x
2
, ... , x
n
) не содержится в области
определения функции
f.
Тогда машина
M
работает
бесконечно.
Пример вычисления функции на
машине Тьюринга
► Построим машину Тьюринга, вычисляющую значения функции
► f(x,y)=x+y.
Пусть на ленте находятся два числа x и y. Очевидно, что складывая эти числа
мы должны устранить между ними 0 и уменьшить число единиц на два. В
результате на ленте должно остаться (x+y+1) единиц, идущих последовательно
друг за другом.
Сначала проходим через x:
(0, 1, 1, R,0).
Эта инструкция повторится ровно x раз. Затем каретка окажется над нулем,
разделяющим числа x и y. Этот ноль заменяем единицей с помощью
инструкции:
(0, 0, 1, R, 1).
Теперь проходим через число y:
(1, 1, 1, R, 1).
Доходим до конца числа y. Каретка снова оказалась над нулем. Возвращаемся на
одну ячейку назад и стираем одну, а затем еще одну единицу:
(1, 0, 0, L,2),
(2, 1, 0, L,3),
(3, 1, 0, L,4).
После стирания двух единиц можно вернуться назад и остановиться:
(4, 1, 1, L, 4),
(4, 0, 0, R,5).
Тезис Тьюринга
► Теперь мы располагаем всеми необходимыми определениями для точной
формулировки понятия алгоритма. Из определения машины Тьюринга легко
убедиться, что ее работа удовлетворяет всем требованиям, предъявляемым к
понятию алгоритма. Поэтому произвольная функция, вычислимая на машине
Тьюринга, является вычислимой функцией. Рассмотрим обращение этого
утверждения.
► Тезис Тьюринга. Если функция f является вычислимой, то существует машина
Тьюринга вычисляющая функцию f.
► Сможем ли мы доказать тезис Тьюринга? Нет, т.к. у нас нет точного определения
понятия вычислимой функции. Тезис Тьюринга является результатом, возникшим
из опыта. Тезис Тьюринга - еще один вариант определения алгоритма, поскольку
отождествляет интуитивное понятие вычислимой функции со строгим понятием
функции, вычислимой на машине Тьюринга. Доказана равносильность тезиса
Тьюринга и тезиса Черча. Это подкрепляет уверенность в том, что оба тезиса
адекватно отражают понятие алгоритма. Тезисы Тьюринга и Черча можно
рассматривать как теоретические границы возможностей реальных
вычислительных машин.
Другие варианты определения
машины Тьюринга
Рассмотрим другие способы определения машины Тьюринга.
Пусть имеется некоторый алфавит
A={a
0
, a
1
, a
2
, ... , a
n
},
который мы будем называть внешним алфавитом. Элементами
алфавита A будем заполнять ячейки ленты, при этом символ a
0
будет служить для обозначения пустой ячейки.
Пусть имеется другой алфавит
Q={q
0
, q
1
, q
2
, ... , q
m
},
который мы будем называть внутренним алфавитом.
Этот алфавит мы будем использовать для обозначения состояний
машины
M,
при этом символ
q
1
будет служит для обозначения
начального состояния, символ
q
0
– для обозначения
заключительного состояния.
Другие варианты определения
машины Тьюринга (продолжение)
Команды, из которых составляются программы,
имеют один из трех видов:
1) q
i
a
j
q
k
a
l
, 2) q
i
a
j
q
k
a
l
L, 3) q
i
a
j
q
k
a
l
R,
где 1
i
m, 0
j
n. Легко видеть, что число
различных команд равно m(n+1).
Команда с началом q
i
a
j
срабатывает,
если машина M находится в состоянии
q
i
и каретка обозревает символ a
j
.
Поэтому в программе должна быть ровно одна
команда с началом q
i
a
j
.
.
Действия при исполнении команд
► Действия при исполнении данных команд следующие:
► 1) q
i
a
j
q
k
a
l
, - машина M переходит в состояние q
k
и
одновременно содержимое a
j
обозреваемой ячейки
сменяется на a
l
.
► 2) q
i
a
j
q
k
a
l
L - машина M переходит в состояние q
k
,
содержимое a
j
обозреваемой ячейки сменяется на a
l
и каретка смещается на одну ячейку влево.
► 3) q
i
a
j
q
k
a
l
R - машина M переходит в состояние q
k
,
содержимое a
j
обозреваемой ячейки сменяется на a
l
и каретка смещается на одну ячейку вправо.
Конфигурация машины
► Машинным словом, или конфигурацией
машины M, называется слово вида Aq
k
a
l
B, где A
и B - слова в алфавите
A.
Так изображается
содержимое ленты и обозреваемая ячейка. При
этом считаем, что машина находится в
состоянии q
k
, а каретка обозревает на ленте
символ a
l
. Слова
A
и
B
отражают содержимое
ленты до и после символа a
l
.
► Группу из
x
символов a на ленте будем
обозначать через a
x
.
Вычисление функции
(второе определение)
► Считаем, что машина M вычисляет функцию
f(x
1
,x
2
, ... , x
n
), если выполнены следующие два
условия.
► 1. Если f(x
1
,x
2
, ... , x
n
) существует, то машина,
начиная работу с конфигурации
q
1
01
x
1
... 01
x
n
0,
останавливается и при этом имеет
конфигурацию
q
0
01f
(x
1
,
x
2
,...x
n
)
0 ... 0.
► 2. Если f(x
1
,x
2
, ... , x
n
) не существует, то машина
работает бесконечно.
Применение машины Тьюринга к
словам
► Задача 1. Имеется машина
Тьюринга с внешним
алфавитом A={a
0
, 1} с
алфавитом внутренних
состояний Q={q
0
, q
1
} и
программой,
представленной в таблице.
Определить в какие слова
перерабатывает программа
каждое из следующих
слов:
► 1) 1 a
0
11 a
0
a
0
11 (4 ячейка)
► 2) 1 a
0
111 a
0
a
0
11 (2 ячейка)
► 3) 1 a
0
a
0
111 (3 ячейка)
Q
A
q
0
q
1
a
0
q
0
1
1
q
1
1R