Теорема Клини о нормальной форме - Рекурсивные функции

Существуютпримитивнорекурсивныефункция u и примитивно разрешимый предикат T такие, что e, x ( E(x)=p ( k [T(e, x,k)])). В частности, e, x ( E(x) k T(e, x,k))

(здесь и далее запись вида f(x)= означает, что функция f неопределена в точке x).

Доказательство.

Неформальная формулировка результата прямо следует из предыдущих рассуждений. Для более формального доказательства рассмотрим слегка измененную версиюпрограммы вычисления универсальной функции, добавив в нее счетчик состояний:

{сделать шагов n шагов в вычислении универсальной функции}

{и проверить, не вычислилось ли значение y}

Start(e, x,y, n);

Привести_программу_в_ начальное_состояние;

Счетчик:=O;

While Счетчик<=n and Не_попали_в_конечное_состояние do

Begin Перейти_к_следующему_состоянию; Счетчик:=S(Счетчик) end

По_конечному_состоянию_определить_значение_функции

IfРезультат=y

Stop(1) {true}

Else

Stop(0) {false}

End

Эта программа вычисляет предикат "при входных данных e, x программа вычисления универсальной функции на шаге n вычисляет y", обозначим его через T1(e, x,n, y). Очевидно, за счет добавления счетчика - параметра цикла - единственный цикл нашей программы гарантированно сходиться, т. е. Т1 - примитивно разрешимый предикат. Для окончания доказательства осталось положить T(e, x,k)= T1(e, x,Элемент_пары(k,1),Элемент_пары(k,2)) и p(k)=Элемент_пары(k,2)

Результат предыдущей теоремы может показаться неожиданным - фактически, он означает, что любую программу можно преобразовать в эквивалентную ей программу, содержащую Единственный цикл. Это действительно так, и можно дать более строгое доказательство этого факта. Но, на практике, все нащи нетривиальные программы содержат множество циклов. Тем более, поклонники нисходящего проектирования программ вряд ли сочтут такую форму программы нормальной, т. е. канонической. С другой стороны, для сторонников событийного программирования такая форма программ естественна - они знают, что в интерактивной программеналичествует если и не единственный, то главный цикл - цикл обработки событий, предназначенный для определения типа компонент входного потока и вызова соответствующих этим типам процедур (методов). Мы продолжим разговор о моделях вычислений с единственным циклом и трактовке работы алгоритмов как реакции на внешние события в лекции по теории автоматов.

Похожие статьи




Теорема Клини о нормальной форме - Рекурсивные функции

Предыдущая | Следующая