Конспект установочных лекций по комплексному курсу Информатика, Теория информации




Рекурсивные функции - часть 7


b. Для у = а-b получается:

ho(a, Ь, а-Ь) = sub(b+(a-b), a)+sub(a, b+(a-b)) = 0.

Для у < а—b (т. е. для b+у< а)

справедливо: ho(a, b, у) = sub(b+y, a)+sub(a, b+y) = sub(a, b+y) > 0.

Таким образом, в этом случае имеет место ). m(ho)(a, b) = а—b.

2.         Случай а < b. Для всех чисел у получается:

ho(a, b, у) = sub(b+y, a)+sub(a, b+y) =

sub(b+y, а) > 0.

Таким образом, в этом случае m(Ьо) (а, b) не определено.

(2)                Деление. Частично определенное деление

a./.b=[a/b,a mod b=0; 0, a=b=0; не определено иначе]

специфицируется через m-рекурсию

m(h1),

где

h1(a, b, z) = а - (b * z).

Это снова можно показать путем различения случаев.

1.         Случай a mod b = 0 или а =Ь= 0;

Если имеет место b > 0, то число у однозначно определено и для z < у определено

a-b*z.. Если b = 0, то у = 0 удовлетворяет уравнению.

2.         Случай a mod b не равно 0 или b = 0 , а> 0; если b > 0, то справедливо а •/•b не определено.

Не существует такого числа z, что a-b*z= 0, так что выражение а - b * z или не определено, или оно > 0. Если а > 0 и b = 0, то

а - b*y > 0

для всех у; тогда m (h1) (а,b) не определено.

(3) ulam. Функция ulam специфицируется через

ulam(n) = succ(zero(l)(m( h )(n))), причем пусть функция g специфицирована так же, как и при введениифункции ulam в начале данного раздела, а функции h и h специфицированы следующим образом:

h(n, 0) = п,

h(n, m+l) = g(h(n, m)),

h(n, m) = sub(h(n, m)-1) == pred(h(n, m)).

Снова можно доказать, что для всех n Î N значение ulam (n) совпадает

со значением succ (zero(1))(m(h )(n))). Имеет место: ulam (n) = 1 или ulam (n) не определено.

(1)  h(n, m) = gm(n),     где go(n) =n,

(2)  h(n, m) = 0à h(n, m) < 1à g”’(n) < 1.

Поэтому m( h )(n) определена точно тогда, когда справедливо

Э m:gm(n) < 1,

и дает наименьшее число m, для которого это свойство имеет место.

Определяется множество MR m-рекурсивных функций как наименьшее подмножество пространства функций




Содержание  Назад  Вперед