Лекции по СЯП (987656), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

F(b+8,F(b+7,F(b+6,F(b+5,F(b+4, b+4))))),

и далее мы получаем

F(b+8,F(b+7,F(b+6,F(b+5, if b+4=b+4 then b+4+1

else F(b+4,F(b+4–1,b+4+1)))))).

F(b+8,F(b+7,F(b+6,F(b+5,b+5))))

:

F(b+8,F(b+7,F(b+6,b+6)))

:

F(b+8,F(b+7,F(b+6,b+6)))

:

F(b+8,F(b+7,b+7))

:

F(b+8,b+8)

:

b+9

Таким образом, F(a,b) = F(b+8,b) = b+9 = a+1. Отсюда видно, что F(a,b) = a+1, если a b и a–b четно.

Итак, мы получили, что вычисление по программе Q дает функцию f₃(x,y).

Примеры. 1) Рассмотрим функционал τ : F(N⁺,N⁺) F(N⁺,N⁺), определяемый как

τ[F](x) = if x = 0 then 1 else x•F(x–1).

Далее через _┴ будем обозначать не только неопределенное значение, но и всюду неопределенную функцию: _┴(х) =_┴.

Имеем:

τ[_┴](x) = if x=0 then 1 else x• _┴(х–1) = if x=0 then 1 else _┴

τ²[_┴](х) = τ[τ[_┴]](х) = if x=0 then 1 else x• τ[_┴](х–1)

= if x=0 then 1 else x• (if x–1=0 then 1 else _┴)

= if x=0 then 1 else x• (if x=1 then 1 else _┴)

= if x=0 then 1 else (if x=1 then x else _┴)

= if x<2 then 1 else _┴ = if x<2 then x! else _┴.

Докажем индукцией, что 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

τ^k[_┴](х) = if x<k then x! else _┴ .

Если это верно, то

τ^k+1[_┴](х) = ττ^k[_┴](х) = τ[τ^k[_┴]](х)

= if x=0 then 1 else х• τ^k[_┴](х–1)

= if x=0 then 1 else х• (if x –1<k then (x–1)! else _┴)

= if x=0 then 1 else (if x<k+1 then x! else _┴)

= if x<k+1 then x! else _┴ .

Ясно, что τ^k[_┴] τ^k+1[_┴]. Следовательно,

sup{τ^k[_┴] | k = 0,1,2,…}(x) = x!

2) Возьмем оператор

τ[F](x,y) = if x=y then y+1 else F(x,F(x–1,y+1))

и найдем его наименьшую неподвижную точку.

τ[_┴](x,y) = if x=y then y+1 else _┴(x,_┴(x–1,y+1)) =

= if x=y then y+1 else _┴ =

= if x=y then x+1 else _┴.

τ²[_┴](х) = τ[τ[_┴]](x) = if x=y then y+1 else τ[_┴](x,τ[_┴](x–1,y+1)) =

= if x=y then y+1 else τ[_┴](х, if x–1=y+1 then x–1+1 else _┴) =

= if x=y then y+1 else τ[_┴](х, if x=y+2 then x else _┴) =

= if x=y then y+1 else if x=(if x=y+2 then x else _┴) then

x+1 else _┴ =

= if x=y then y+1 else if x=(if x=y+2 then y+2 else _┴) then

(if x=y+2 then y+3 else _┴) else _┴.

Рассмотрим условие x=(if x=y+2 then x else_┴). Возможны два случая: (1) х=у+2 и (2) х у+2. В случае (1) получаем х = х, т.е. это условие истинно, а в случае (2) получаем х= _┴, т.е. это условие имеет значение _┴..Следовательно,

τ²[_┴](х) = if x=y then y+1 else if x=y+2 then х+1 else _┴ =

= if (x=у) (x=y+2) then х+1 else _┴ .

Докажем индукцией по k, что

τ^k[_┴](х,y) = if (x=у) (x=y+2) … (х=у+2(k –1)) then х+1 else _┴ .

Условие (x=у) (x=y+2) … (х=у+2(k –1)) в доказываемом равенстве запишем короче: V{x–y=2j | j < k}. Предполагая равенство

τ^k+1[_┴](х,y) = if V{x–y=2j | j < k} then х+1 else _┴

верным, для k+1 будем иметь:

τ^k+1[_┴](х,y) = τ[τ^k[_┴]](х,y) =

= if x=у then y+1 else τ[_┴](x,τ^k[_┴](x–1,y+1)) =

= if x=у then y+1 else

τ[_┴](x, if V{(x–1) – (y+1) =2j | j<k} then х–1+1 else _┴) =

= if x=у then y+1 else

τ[_┴](x, if V{x–y =2(j+1) | j<k} then х else _┴) =

= if x=у then y+1 else

τ[_┴](x, if V{ x–y =2j) | 0<j<k+1} then х else _┴) =

= if x=у then y+1 else if

x=(if V{x–y=2j | 0<j<k+1} then х else _┴)

then x+1 else _┴).

Рассмотрим условие x=(if V{x–y=2j | 0<j<k+1} then х else _┴).

Характеристики

Список файлов лекций