FORMALIZED RECURSIVE FUNCTIONALS

3

be written say!!^(a.,,•••*a, £-\ • • *^P )"•) The expressions atthe right

will be explained in1.3•

ry(a,-60**a if /(a,^)-0,

(50) (f(a,£) e*f (a«,£) if ^(a,£) «*c«. ^'^

Then f(a,^)^Uw^^^w^)^], so^w^(w,^)==o]^(0,-&). Cf. IMp. 351 (b).

(51) ^(a,"-i^)"= a' = a+1. ' L

(52) ~ f(4) =

£o

2,£

(53) ^(a,£)==a. 3

(54) ~/(^) -/(£(-£),£)• U,g,h

(35)

/f°.f =?*. „ „ 5,gli

rf(o,i

U(a',i

^(a',£) -^(a,^(a,-£),-£).

(56) ^ ( ^ - ^ U ^ ) , 6,g,h

where^^ is a list of variables including at least h+1numbervariables

from which #1 results bymoving theh+l-st number variable tothe front.

(57) f(±yOC,^) ~ gc(a.). 7

(58) ~ f{Mi) ~ ^iJ&jJ, S,g,h

where 4n isa list ofvariables including atleast h+1 function variables,

from which ^t results bymoving the h+l-st function variable to the front.

1.2. Inthe computation ofanyparticular value ofa partial recursive

functional cfi^ , • • • ,§_. , g(1 , . •., 9(g)

9

only finitely many values of its

function arguments #-,•••, Oi£ can beused. Sowecan dothe computation

having foreach function argument & aninput ofinformation consisting of

only a suitable finite setofvalues of °L (the values that will beneeded,

and perhaps some more). Itisconvenient torepresent such aninput bya

number. For this purpose, wehave been using the sequence number x(x)

(= 1 1.^vfe — ) torepresent the first x consecutive values of & (cf. FIM

pp. 45 3&, 93)• Itisadequate touse only such inputs under the normal

interpretation ofourfunction variables asranging over total (i.e.

completely defined) one-place number-theoretic functions. Butcontraryto

this interpretation, wedosometimes substitute forfunction variables

expressions for partial (i.e. not necessarily completely defined) functions

4In IMpp. 290-292 weused instead S(x) (=Ui?c£j ^ ),which is simpler

when x isknown independently, but ambiguous when x isnotknown (e.g.

§(5)"^ 2(4) if oc(4)-0).