Математическая логика и теория алгоритмов. Анкудинов Г.И - 72 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

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

Рубрика: 

Наша цель – дать читателю схематичное представление о
подходе к доказательству сформулированной теоремы, поэтому
дальнейшее изложение не претендует на полноту.
Общий план изложения заключается в доказательстве двух
утверждений:
• о возможности вычисления любой ЧР-функции на машине
Тьюринга;
• о возможности воспроизведения любого вычисления на
машине Тьюринга с помощью некоторой ЧР-схемы.
Порядок доказательства утверждений несущественен.
Утверждение 4.1. Любая ЧР-функция может быть вычислена
на машине Тьюринга.
Для доказательства этого утверждения докажем, что операции
суперпозиции, рекурсии, минимизации, а также функции следования,
константы ноль и тождества, могут быть запрограммированы на
машине Тьюринга.
Программирование операции суперпозиции. Рассмотрим эту
операцию на примере
h(x
, …,x )=g(f (x , …,x ), …, f (x , …,x )).
m m n m1 1 1 1
,…, f вычисляются машинами M , M , …, M
Если функции g, f
n n1 g 1
, то
функция h может быть вычислена машиной M
°(M * … * M ).
g n1
Программирование операции рекурсии. Рассмотрим эту
операцию на упрощенном примере:
f(0)=a,
f(x+1)=h(x, f(x)).
Рекурсивная схема реализуется машиной Тьюринга, а именно
циклической программой на рис. 4.7.
На этом рисунке:
• машина A перерабатывает слово x в слово x*0*a;
• машина B получает слово x
*x *x и выдает σ=и, если x
1 2 3 1
=0, и
σ=л в противном случае;
• машина M
оставляет входное слово без изменения;
0
по слову x *x *x выдает x ¬ 1;
• машина M
1 1 2 3 1
по слову x *x *x выдает x + 1;
• машина M
2 1 2 3 2
156

Страницы