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).
Previous Page Next Page