border=0

Foarbyld 7.2

Sykje wearde. S 3 ( I 2 2 , I 1 1 , 0 1 ). Yn dit gefal wurdt de finale funksje twa-plak ( n = 3 - 1 = 2), dus h ( x 1 , x 2 ) = I 2 2 ( I 1 1 , 0 1 ) = I 22 ( x 1 , 0) = 0.

Primitive rekursion

Lit guon numerike dielfunksjes wurde jûn: n- sit g (x 1 , ..., x n ) en (n + 2) -plicht h (x 1 , ..., x n , k, y). It wurdt bepaald dat ( n + 1) -plasjale funksje fan funksjes g en h ynsteld is troch middel fan primitive rekursion, as foar alle natuerlike wearden fan x f ; ..., x n , y hâldt wier:

Sûnt it domein fan definysje fan funksjes is de set fan alle natuerlike nûmers, is de partialfunksje f befetsje fan betingsten (7.1) foar elke dielfunksjes g en h, en dizze funksje sil unyk wêze. Understeande (7.1) bepale ek de sesje foar it bepalen fan de wearden fan f by ferskate rekursionstappen:

It symboalysk primityf rekurt is f = R (g, h); yn it fan dit rekord wurdt R as beskôge as in symboal fan in partiel-operaasje bedarre dy't definiearre wurdt op 'e set fan alle partialfunksjes. Relaasjes (7.2) betsjuttje, benammen dat as g en h oeral fêstlein binne, dan wurdt f ek oeral definiearre. It is ek sjoen fan (7.2) dat it wichtich is dat as wy de wearden fan 'e funksjes g en h fine kinne, dan kinne de wearden fan de funksje f (a 1 , ..., a n , m + 1) "meganyk" berekkene wurde troch te finen súksesfol de wearden op' e eardere stappen. Wy prate de definysje yn.

In partiale funksje f (x 1 , ..., x n ) wurdt primitive rekursive neamd as it kin krije troch in finite oantal operaasjes fan superposysje en primitive rekursion, basearre allinich op de ienfâldige funksjes S 1 , 0 n en I m n .

As de operaasjes fan superposysje en primitive rekursion tapast wurde foar universele funksjes, dan sil it resultaat ek in universele funksje wêze. Benammen alle primitive rekursive funksjes binne oeral definiearre.

Sjoch ek:

Foarbyld A.3

Foarbyld 8.1

Computer kodearring en ferwurking fan echte nûmers

Foarbyld 2.3

Value formalisaasje

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ bibinar.info