Введение в схемы, автоматы и алгоритмы


Программная вычислимость рекурсивных функций - часть 3


Действительно, предположив это условие, получим, что после очередного выполнения фрагмента

 \Pi_1;\ z_1:=0;\ldots ; z_m:=0;\ u:=x_1;

значение u = x1 = g(a1,…,an,i), а рабочие переменные восстанавливают нулевые значения. Если g(a1,…,an,i)=0, то u=z и в условном операторе x1 получает значение y'=i. После этого условие цикла нарушено и ? завершает работу с выходным значением x1=i =F(a1,…, an). Если же g(a1,…,an,i)> 0, то u>z и в условном операторе y' увеличивает значение до (i+1). Тогда условие цикла выполнено и перед (i+2)-ым выполнением ?1 ее входные переменные x1,…,xn,y имеют значения a1,…,an, i+1, соответственно, y'= i+1, а все рабочие переменные равны 0.

Из доказанного утверждения непосредственно следует, что

\Phi_{\Pi,x_1}(a_1,\ldots,a_n)= \mu y[g(a_1,\ldots,a_n,y)=0].

Имеет место и утверждение, обратное теореме 8.1, которое мы приводим здесь без доказательства.

Теорема 8.2. Каждая программно вычислимая функция является частично рекурсивной.




Начало  Назад  Вперед



Книжный магазин