12 S. Co KLEENE
{XKsh *'**L\r9 2^- i •••** #) ^s undefined), because andonly because, for all
K,...,bz)with b,,...,b/|tf-,,..., X£, (a) atsome stage inthe attempted
computation insufficiently many number arguments orfunction argumentsare
available, or (b) atsome stage anindex ispresented which fits none of the
nine schemata, or (c) aninfinite regress arises inattempting to evaluate a
function value by (SO).
The final step toobtaining convenient surrogates forcomputations
considered asproofs will betocollapse each computation tree into a number,
called a computation tree number. Say the tree isasfollows, with two, one or
zero premises tothe final inference, respectively:
Yl Y2 Yl
q,
q, g,
where q isthefinal quadruple number, andY-. and Y~, orY-,,are the subtrees
down tothe premise(s) ofthe final inference,inclusive.We collapse these into
respectively, where y. and y~, ory.,, result(s)by similar collapsing in Y-,
and Y2 orinY^
Thus a computation comes toberepresented bya single number. For
example, ifthe final inference isanapplication of (SOb), this number is of
the following form, with k 0 andu 0:
« 0 , g , k , a
1
, . .
9
2q,ihi 9^^9
€*£% 9^9L\9 &1U'
09^9k,a^,^ o..^iijki5 ° jki^^-°
where the second line (except forthe final comma) andthe third line (except
for the final "") aresmaller computation tree numbers. Thefinal dots in
the second andthird lines allow room for zero ormore quadruple numbers
serving aspremises forinferences above the lowest inference (together with
symbols "" and"'bracketing them and commas separating them).
Causes (a) and (b) of indefinition result from our loose management of
the indices, andcould have been avoided. (The first cause will not arise so
long asweuseonly proper indices f _ with 1 c mn^) and £ mf(f);the
second, solong asweuse only proper indicesT) Cause (cj ofindefinition is
fundamental (IM§63).^
Previous Page Next Page