Теория алгоритмов. Зюзысов В.М. - 13 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Пусть D
f
⊆ N
k
– область определения k-местной функции f: D
f
→ N. Функция f
называется вычислимой по Тьюрингу, если существует машина Тьюринга M такая, что
как только M начинает с инструкции q
0
, обозревая самой левый символ строки
<n
1
> 0 <n
2
> 0 ... 0 <n
k
>,
(вся остальная часть ленты пуста), тогда:
• если f(n
1
, n
2
,..., n
k
) определено, то M, в конце концов, остановится, обозревая самый
левый символ строки <f(n
1
, n
2
,..., n
k
)>, при этом часть, находящаяся справа от этой
строчки, пустая;
• если f(n
1
, n
2
,..., n
k
) не определено, то M никогда не останавливается.
Заметим, что имеется бесконечное множество машин Тьюринга, для каждой
вычислимой функции своя. Более того, для любой вычислимой функции имеется
бесконечное множество машин Тьюринга, вычисляющих эту функцию.
Пример. Построим машину Тьюринга, вычисляющую сумму n
1
+n
2
.
Зададим функцию M следующим образом:
M(0, 1) = <1, П, 0>;
M(0, 0) = <1, П, 1>;
M(1, 1) = <1, П, 1>;
M(1, 0) = <0, Л, 2>;
M(2, 1) = <0, Л, 3>;
M(3, 1) = <0, Л, 4>;
M(4, 1) = <1, Л. 4>;
M(4, 0) = <0, П, 5>.
Посмотрим, как происходит сложение 1+1. В текущей строке символов обозреваемый
символ выделен.
номер
инструкции
текущая строка
символов
комментарий
0 0110110
0 0110110
прохождение через
первое слагаемое
0 0110110 заполнение
промежутка
1 0111110
1 0111110
прохождение через
второе слагаемое
1 0111110 конец второго
слагаемого
2 0111110 стирание 1
3 0111100 стирание второй 1
4 0111000
4 0111000
4 0111000
движение назад
4 0111000
5 0111000
остановка
Мы должны заметить, что многие детали нашего определения машины Тьюринга
до некоторой степени произвольны. Если бы было более одной ленты, то класс
вычислимых функций остался бы неизменным, хотя некоторые функции могли бы быть
вычислены более быстро. Аналогично, мы могли бы допускать больше символов, чем 0 и
1, или же у нас могла
бы быть лента, бесконечная только в одну сторону от начальной
точки, вместо имеющейся бесконечной в обоих направлениях. Ни одно из этих изменений
не затрагивает класса вычислимых функций. Что действительно существенно в этом

Страницы