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