Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій, Детальна інформація

X#Y#XS(X#Y|#XSS }.

Приклад 12. Система Поста для функцiї f(x, y)=x \xF02Dy2:

A ={##};

P ={X##R(X|##R|,

X#Y#RYY|(X#Y|#R }.

Приклад 13. Система Поста для функцiї f(x)=x2\xF02D2x:

A ={#, ||#};

P ={X|#R(X||#RXX| }.

В цьому прикладі треба врахувати, що f(1)(.

Приклад 14. Система Поста для функцiї f(x)=x3 :

A ={((};

P ={X(Q(R(X|(QХХ|(RQQQXXX|,

X(Q(R(X#R }.

Для обчислення значення f(x+1)=(x+1)3=f(x)+3x2+3х+1 потрібне x2, тому теоремами СП мусять також бути коди трійок (х, x2, x3). Але теоремами в алфавіті {|, #} можуть бути тільки коди елементів графіка f(x), тому для кодування трійок (х, x2, x3) використано (.

Приклад 15. Система Поста для функцiї f(x)=x! :

A={#|};

P ={X#F(X|(F(((,

S(F(A(B(M(S(F(A|(B(MB,

S(F(A(B(M(S(F(A(B|(MA,

S(F(S(F(M(S#M }.

До теорем СП належать коди 5-рок (х+1, x!, a, b, ab), для їх коду-вання використано (. Із кодів 5-рок (х+1, x!, х+1, x!, (х+1)(x!) можна вивести закодовані в алфавіті {|, #} коди пар (х+1, (х+1)!).

:

A={((};

P ={X(((X|((,

QS|(Q(R(QS|(QRR|(R|,

X(X(R(X#R,

X(XS|(R|(X#R }.

До теорем СП належать коди трійок (х, r2, r), для їх кодування використано (. Із кодів трійок (х, x, r) та (х, (r+1)2, r+1) при умові r2(х<(r+1)2 можна вивести закодовані в алфавіті {|, #} коди пар (х, r).

Приклад 17. Система Поста для предикату "x=y":

A ={## |};