3148972479

Reprezentowalność funkcji rekurencyjnych w A-rachunku

Lemat. Funkcje bazowe (początkowe) Z, S,    są

A-definiowalne.

Dowód. Weźmy następujące kombinatory jako termy definiujące.

Z = An.O

suc = A nfx.f(nfx)

= \x\... x_n.Xi

Lemat. Funkcje A-definiowalne są zamknięte ze względu na operację składania funkcji.

Dowód. Niech funkcje g,hi,... ,h_r będą A-definiowalne odpowiednio za pomocą termów G,Hi,..., H_r. Wówczas funkcja

f(x) = g(hi(x),... ,h_r(x)) jest A-definiowalna za pomocą termu

F = Xx.G(H₁ x)...(H_rx)

Zdzisław Spławski: Teoretyczne Podstawy Języków Programowania, Wykład 4. Siła wyrazu rachunku A 17