FORMALIZED RECURSIVE FUNCTIONALS

11

Accordingly, we now allow as quadruple numbers

£j b&\ ^•••^ JL*ki###ki- 2£r also ones in which f is not a proper index.

And we reconstrue our computation trees to permit the two-and one-premise

inferences to be applied with conclusion f,k,a-1 • • • §j5i,b-i,...,b *,w if

f simply has the form shown opposite the respective schema in 1.1,without the

further requirement that the g for (SOa), (SOb), (S6)or (S8),or both theg

and the h for (S4), (S5a)or (S5b), be proper indices. (Nothing is changed for

the zero-premise inferences, (SI)—(S3), (S7)#) If f is of none of the nine

forms shown opposite the schemata in 1.1, of course no inference is

performable with the conclusion £&§.-,,...§, ,f,b1,•..,b0,w.

In this way,we come to interpret each natural number f_ as an index of a

partial function f = Aa^...a^.#....., ct^ ^a..,...,3^,o^ ,...,o{^) =

hzLi*• •ihrQr• ••Qfp {Q&i ••• 2ir9 ^i • ••&£) f°r ea°h k and Z.12 That is,

f is an index of that function f of k+ivariables which is defined forthe

arguments a,,...,a, , ^-.,•••* 5^ with value w exactly if a computation tree

exists which has as lowest quadruple number ^3c,a,-i,.•.,a^, /,b-,...,b^,w

for some numbers b,,...,b^ such that ID,,...,b^|o6-j, Q..9QL % .-^ Of course, thew,

if it exists, is unique for given f^jjb•••§!.^n ^•••2^^» We shall include a

proof of this fact in our formalized theory 1*31.8 in1.6).

A computation tree as just described can fail to exist (so

Here our terminology resembles that of IM pp. 289,330, where we took

each number j e to be a G5del number of a respective (total or)partial

function ^(x,,...^ ),even though £ may not be the G6del number of a system

E of equations defining ^(x, ,...,x ) recursively. So now, each number f is

an index of a respective ^(a_,...,a,,o£-,...,o£/), even though £ may not

represent a description of $ by the schemata (S0)-(S8) (i.e. may not be a

proper index of f).

In contrast, Hi 1958a and in 1959, and in the preliminary paper 1968tothe

present Part I, we used "index" only for a number representing a description

of the f by the schemata under consideration. (In 1958a, a non-index always

gives th~econstant function 0; in 1959, always the completely undefined

function.)

13

When £ is not a proper index, £f}(a, ,...,a,,#-.,..#,Q£/) may nevertheless

be defined for some or even all a., , •.,,a,, QC-,, .7.9oC^ For,f may involve (S5)

in such a way that its second equation, with a % given by an improper index h,

is never needed in the computation forthe given a-^,...,a^,OC-j_,. .•,££/• For

example, taking f = 4,5,3,h,2,0» with h not a proper index as an index

of a function £T±)9 then £ is not a proper index and yet cf(&) (— a, forall

a) is completely defined. ~