Iterated Limiting Recursion and the Program Minimization Problem

ITERATED LIMITING RECURSION AND THE PROGRAM MINIMIZATION PROBLEM.

L.K. Schubert

Department of Computing Science., University ofAlberta, Edmonton, Alberta, Canada.

ABSTRACT: The general problem of finding minimal programs realizing given "program descriptions" is considered, where program descriptions may specify arbitrary program properties. The problem of finding minimal programs consistent with finite or infinite input-output lists is a special case (for 1. INTRODUCTION A question considered by Gold [1) was for what classes of computable functions there exist machines which succeed in "identifying in the limit" any member of the class. Identifying a computable function in the limit infinite input-output lists, this is a variant consists of generating a sequence of "guesses" of E.M. Gold's function identification problem; another closely related problem is tne grammatical inference problem). Although most program minimization problems are not recursively solvable, they are found to be no more difficult than the problem of deciding whether any given program realizes any given description , or the problem of enumerating programs in order of nondecreasing length (whichever is harder). This result is formulated in terms of k-limiting recursive predicates and functionals, defined by (integers) convergent to an index for the function, successive guesses being based on successively larger portions of an information sequence which lists all elements of the function. An example of a practical problem to which these concepts are relevant is the learning problem in pattern recognition. Typically an adaptive pattern recognition system is caused to "learn" a mapping from patterns to responses by presenting to it a sequence of labelled patterns, i.e., patterns with their appropriate responses. All of the repeated application of Gold's limit operator. machine's responses will conform with the A simple consequence is that the program desired mapping once it has identified that minimization problem is limiting recursively mapping, in the sense that it has found an solvable for finite input-output lists and 2- algorithm (equivalently, an index) for it. limiting recursively solvable for infinite Two of Gold's main results were that any r.e. input-output lists, with weak assumptions class of total recursive functions is about the measure of program size. Gold identifiable in the limit, and that the class regarded limiting function identification of total recursive functions is not identi(more generally, "black box" identification) fiable in the limit (hence also the class of as a model of inductive thought. Intuitively, partial recursive functions is not identiiterated limiting identification might be fiable in the limit). regarded as higher-order inductive inference Here a modified version of Gold's problem performed collectively by an ever growing is considered. The first modification is the community of lower-order inductive inference replacement of information sequences by

machines.

KEY WORDS AND PHRASES: function identification, minimal programs , limiting recursion, inductive inference, program length measures, program properties, degree of unsolvability.

(finite or infinite) "program descriptions" which may specify arbitrary program properties. Descriptions which list input-output pairs are then regarded as a special case. The second modification is that iterated limit procedures (k-limiting recursive functionals) are admitted for program-finding, since finding suitable programs in the non-iterated limit is impossible for many classes of program descriptions. For this purpose k-limiting recursiveness is defined by straight-forward generalization of Gold's concept of limiting recursiveness. The third modification is the added requirement that programs found in the (iterated) limit be minimal according to some prescribed measure of program size.

in finding minimal-length programs. In work on grammatical inference closely related to Gold's identification problem, Feldman [2] considers inference schemes which try to find "good" grammars consistent with available information about a language. One measure of goodness is the intrinsic complexity, or size, of a grammar. In terms of the function identification problem, this corresponds to finding programs which are small according to some measure of program size. Indeed, the use of small programs for inductive inference is a recurring theme in the literature (see for example Refs. 3-5); allusion is usually made to the scientific maxim knows as "Occam's Razor", according to which "it is vain to do with more what can be done with fewer" in accounting for known phenomena. The special importance of minimal programs is also suggested by the work of Kolmogorov [6], Martin-Lof [7] and others, showing that the number of symbols in the shortest program for generating a finite sequence · can be taken as a measure of the information content of the sequence, and this measure provides a logical basis for information theory and probability theory.

Accordingly problems of this modified type are called program minimization problems. In the following the unsolvabi1ity of most nontrivial program minimization problems is first noted. After establishment of some basic properties of k-limiting recursive predicates and functionals, it is shown that any program minimization problem is k-limiting recursively solvable if the problem of determ­ ining whether any given program satisfies any given description is k-limiting recursively solvable and programs are k-limiting r.e. in There are various reasons for an interest order of nondecreasing size. Simple consequences are that the problem of finding minimal programs for finite functions is limiting recursively solvable, and that the problem of finding minimal programs for arbitrary computable functions (given an explicit listing) is 2-limiting recursively solvable, with weak assumptions about the measure of program size. Lower bounds on the difficulty of these problems are already known from the work of Pager [8] and Gold [1].

Finally, the point is emphasized in the concluding remarks that limiting recursively solvable induction problems, though strictly "unsolvable" in general, are nonetheless with­ in the reach of mechanical procedures in the important sense described by Gold, and that even problems unsolvable in the limit may be regarded as solvable in a weakened sense by an expanding community of mechanisms performing limit computations.

2. PROGRAM MINIMIZATION PROBLEMS

To fix ideas, any programmable machine M may be thought of as a 2-tape Turing machine, with one tape regarded as input-output (I / 0) tape and the other as program tape. One or both tapes also serve as working tape. A computation begins with the finite-state In the following, obviously machine and length-measure dependent concepts will some­ times be used without explicit reference to a particular machine or length measure. This control of the machine in a unique start state should be kept in mind for a correct inter­ and with a program on the program tape and an pretation of the results. input on the I / 0 tape. If and when the machine halts, the I / 0 tape expression gives the out- whose length does not exceed the length of any put. It is assumed that there is an effective other program for ~- The problem of finding a 1-1 coding from tape expressions (same syntax for both tapes) onto the integers N. The program (or I / 0 tape expression) corresponding of the elements of ~. is an example of a to code number (index) x will be written as x. program minimization problem. More generally, If M eventually halts with output z when supplied with program x and input y, one may write ~~(y) = z. If M does not halt, ~~(y) is undefined. Thus M computes a partial f t' ~M . unc lon ~x Wlth program x. However, it will be convenient to think of x not merely as a program for ~~. but as a program for any subset of ~M. I th d ~x n o er wor s, x is a program for a function ~ provided only that ~~(y) ~ (y) for ally in the domain of ~ ; ~M(y) X need not be undefined for y outside that domain. If such an x exists for a given ~. ~ will be said to be programmable (on M) . A machine on which all partial recursive functions are programmable is universal.

A program length measure assigns a nonnegative integral length to each program such that only a finite number of programs are of any particular length. A length measure need not be recursive, though this is a frequent assumption; furthermore, programs are often assumed to be effectively enumerable in order of nondecreasing length. For example, the number of elementary symbols in a program provides such a length measure.

A minimal program for a function ~ is one minimal program (or all minimal programs) for a function ~. given a (possibly infinite) list a program minimization problem is the problem of finding a minimal program (or all minimal programs) meeting the conditions listed in any "program description" belonging to some class of such descriptions. Program descriptions are loosely defined as follows. Suppose that a (possibly infinitary) logical system is given along with an interpretation based on a fixed M such that every wff in the system expresses some program property (i.e., every wff is a unary predicate over programs). Then the wffs comprising the system will be called program descriptions. Typically a program description might specify relationships between inputs and outputs (e.g., particular input-out­ put pairs), structural properties (e.g., the number of occurrences of a particular symbol in the program), operational properties (e.g., computational complexity), or combinations of such properties. If 8 is a program description, a program x will be said to realize 8 if x has the property expressed by 6;

more briefly, 6(x) will be written

for "x realizes 6". If ani exists such that 6(x), then 8 will be said to be realizable. For some descriptions (such as listings of input-output pairs) the truth value of the assertion 6(x) depends only on the function computed by M with program i, i.e.,

[ ¢M = ¢MH[ 6 (x) {:} 6 <Yl]. such descriptions X y will be termed I/O descriptions. As examples of I/0 descriptions which do not merely list functions, consider the following expressions (in a quasi - logical notation with the obvious interpretation):

Gold's identification problem can evidently be reformulated in terms of infinite descriptions (i.e., wffs belonging to an infinitary logical system) such as

involved, these can be coded as total number- program which enumerates descriptions and mapping from elementary symbols into integers. a minimal program longer than itself; it then For example, consider illustration (iv) above; simulates that program, and contradiction

It is assumed that descriptions can be coded numerically. If only finite descriptions are involved, an effective coding of descriptions into integers is appropriate. If infinite descriptions are theoretic functions on N by means of a 1-1 if the numbers from 1 to 5 are used to encode M the symbols ¢x' (, ) ,=, and &, respectively, and numerals within the description are represented by adding 6, the code secruence 1,2,6,3,4,6,5,1,2,7,3,4,7, 5 .. . . is obtained;

I

expressed as a total function this is {<0,1>, <1,2>,<2,6>,<3,3>, <4,4 >, <5,6 >, ... } . Thus a mapping whose domain contains coded representations of infinite descriptions is a functional.

The coded version of a description 6, whether it is finite or infinite, will be written as o. Since no confusion can result, coded representations of descriptions will also simply be called descriptions. A set of descriptions will be called infinitely diverse if no set of programs realizincr the descriptions is finite.

Theorem 1 is concerned with I/O descriptions

only, while Theorems 3 and 4 will apply to arbitrary program descriptions.

Theorem 1. Let M be a universal programmable machine and let a recursive length measure be given. Then the program minimization problem is not recursively solvable for any effectively enumerable, \ infinitely diverse set of I/0 descriptions.

Proof: Pager [8 ] previously noted this fact for the case when I/O descriptions specify finite functions, and remarked that the proof involves the Recursion Theorem. I formulated Theorem 1 independently and proved it, in outline, as follows. The negation of the theorem allows the construction of a corresponding minimal programs until it finds results. The possibility of a program measuring its own length and then performing other arbitrary calculations follows from the existence of a recursive function q such that AZ [¢~ (g(x);z) ] for all x. This can be proved from the S-m-n Theorem and the Recursion Theorem.

To demonstrate the unsolvability of a program minimization problem (for a universal machine), it is therefore sufficient to show that the descriptions concerned include an effectively enumerable, infinitely diverse set of I/0 descriptions. This implies, for example , that the program minimization problem for the singleton functions, for the finite decision functions, and even for the decision functions of cardinality 2 is 2 unsolvable , whenever the length measure is recursive.

For example, suppose the minimal programs are required to operate within a certain bound on the computational complexity, apart from an arbitrary additive constant. Then it is clear that the proof of Theorem 1 is applicable without change.

These unsolvability results do not mean that all interesting program minimization problems are entirely beyond the reach of mechanical procedures, as Theorem 3 will show.

The following definitions generalize the concept of limiting recursion introduced by Gold [ lJ.

Pager [9] has shown that the last-mentioned where the ~. are sets of unary total functions

problem is unsolvable even when the length measure is not recursive. Further, he established the surprising fact that the minimization problem is unsolvable for a certain finitely diverse set of decision functions, regardless of the length measure employed [ 8 J .

In view of Pager's results it may be asked whether the requirement that the length measure be recursive is superfluous in Theorem 1. The answer is no (although the requirement can be weakened somewhat) . To prove this, it is only necessary to specify some sequence of finite decision functions such that any program is a program for at most one of these functions, plus an arbitrary procedure for obtaining a particular program for each function in the sequence; then the length measure can readily be defined to guarantee the minimality of these particular programs.

It is interesting to note that Theorem 1 still holds for certain non-I/O descriptions.

Definitions: Let ~ be a subset of ~ 1 x ... x~rxNs J. 3 and r,s ~ O. A functional F is k-limiting recursive on 6 if there exists a functional G recursive on 6xNk such that

(Voe:6 ) (3m 1 ) (vn 1 >m 1 ) ... (3mk) (tlnk>mk)[F( o ) G ( o, n 1 , ··· , nk) J .

Equivalently one may write

" (lfoe:6 )[lim ... lim G(o,n 1 , ... ,nk)=F( o) J. nl nk Similarly a predicate P is k-limiting decidable on 6 if there is a predicate Q decidable on 6xNk such that (V oe:6 ) (3 m 1 l (lfn 1 >m 1 l ·.. (3mk) (tl nk>mk) [ P(o) = Q(o,n 1 , ... ,nk) J . A set of descriptions 6 will be called uniformly k-limiting decidable (with a particular M understood) if there is a predicate P k-limiting decidable on 6xN such that for oe:6, P(o,x) holds iff 6(x). A . set of integers is k-limiting r.e. if it is empty or the range of a function 5 k-limiting recursive on N. a-limiting recursive is the same as recursive, and 1limiting recursive is abbreviated as limiting recursive.

Gold (also Putnam [ 10 ] } has shown that recursive functionals H 1 ,H 2 , .·· ,Hs. Since F and H are k-limiting recursive, there exist functionals G and K recursive on 41 x Nk+ 2 and '!' x Nk+l respectively such that

Since H ( 'l',y) is defined for all ljJ e; ·'l' and all y, a consequence of (1) is

limiting decidable is e9uivalent to membership in the intersection· of classes E 2 and n 2 of the Kleene arithmetical hierarchy. It can be shown that if P is k-limiting r.e., then it is in E 2 k and if P is k-limiting decidable, it is in E nil for all k. The converse 2k 2k' statements are conjectured to be false for k>l; the proof (or disproof) of this conjecture = K(1jJ,y,n 1 ,. ·· ,nk) J. is an open problem.

Lemma 1. If P and Q are predicates of at least one number variable (and possibly additional number and function variables),

Proof. ~ · Suppose the antecedent holds. Let m = max{m 1 ,m 2 } where m 1 ,m 2 are numbers such that (Vn>m 1 )P(n, ... ) and (Yn>m 2 )Q(n, ·.· ). Then clearly (Vn>m) [ P(n, ... ) & Q(n, ... ) ] . c : Immediate.

Corollary 1.1. If P and Q are predicates of at least k number variables (and possibly additional number and function variables),

so that F' is k-limiting recursive on ¢ x '!' x N 2 · Note that it ha·s also been shown that a recursive functional whose iterated limit is the desired composed functional can be obtained simply by composing the recursive functionals whose iterated limits are the given functionals.

&(:J m 1 ) (V'n 1 >m 1 ) ... (3mk) (Vnk>mk)Q(n 1 , ... , nk' ... ) eo·ro·l ·l ·a·ry 2 .1. A predicate whose characteristic function(al) is expressible as =: (3m 1 l (Vn 1 >m 1 l ... (3mk) (Vnk>mk) [ P(n 1 , ... ,nk, .·· ) a c~mposition of k-limiting recursive function(alYs is k-limiting decidabl.e.

& Q(n 1 , ... ,nk, ... ) ~ .

Lemma 2. Composition of k-limiting recursive functionals yields a k-limiting recursive functional.

Proof. Consider the special case F' = A¢1jJxy[F(¢ ,x,H(1jJ , y )) J, where F and Hare functionals :K-limiting recursive on .4> x N 2 and ~· x N respectively, and <ll, ~ are sets of total functions. The proof is easily extended to the case where F is r-ary and s of its arguments are values of k-limiting For example, let the unary predicates p and Q have k-limiting recursive characteristic functions CP and c 0 , and let f(x, y ) = xy for all x andy; then R defined as R={xiP(x)&Q(x) } is k-limiting decidable, since CR(x) = f(CP(x), c 0 (x)) for all x and f is recursive and hence k-limiting recursive for all k.

Lemma 3. Application of the minization operator to a k-limiting decidable predicate yields a k-limiting recursive functional, provided the requisite minimal value always exists .

For example, if P is k-limiting decidable on <1> x N 2 , where <I> is a class of total functions, then >..¢xCl-!yP(¢,x,y) J is k-limiting recursive on <t x N, provided (V¢e: <!>) Wx) (.:Jy) P(¢,x , y) . The notation " ~y ·.. " stands for "the least y such that .·. ".

Proof. Consider the ternary predicate P above (extension to the general case is straightforward). Let Yq,x be the Skolem functional in the existence criterion above, i.e., (V¢e:<t)(Vx)P(¢ ,x,y¢x). Since P is k-limiting decidable, (V¢e: <!>) (Vx) (tfy ) 8m 1 l (lfn 1 >m 1 ) ... (3mk) (lf nk>mk)[P(¢,x,y) ~ Q( ¢ ,x,y,n 1 , ... ,nk) J where Q is decidable on ct x Nk+ 2 . Restrict y to Y~Yq,x' so that the (Vy ) quantifier becomes (V y ~y¢k). This bounded quantifier may be passed through the others: (lf nk>mk) ( tf y ~y ¢x) [ P (¢,x,y) - Q(¢,x , y,n 1 , ... ,nk) J .

Hence

(V¢e: ¢) (Vx) (3m 1 ) (lf n 1 >m 1 J ··· (3mk) (ll nk>mk) [ (~Y ~Yq,x)P(¢,x,y)=(~Y ~Yq,~)Q(¢,x,y ,nl' · .. ,nk) ]. Now since P(¢,x,y¢x) holds, (~Y ~Y¢x)P(¢,x,y) ~yP( ¢ , x,y) . But [~yP(¢,x , y) = ( ~Y ~Yq,x)Q(¢,x,y,n 1 , ... ,nk) J is equivalent to [~yP(¢ ,x, y) = ~yQ(¢,x , y ,n 1 , ... ,nk) J from the definition of Yq,x ' and this is in turn equivalent · to [ ~yP(¢,x,y)=~y [ Q(¢,x,y,nl'"''nk) [h (i,n,n 1 , ... ,nk) = ( ~xe:Sin)[Jxl ~l yl JJ . v y=n 1 JJ provided n 1 >y¢x' Since the right side of the bracketed equality expresses a k+l d . functional recursive on <I> x N an s1nce m 1 can be chosen >y¢x' ~yP(¢,x,y) is k-limiting recursive on . <!> x N.

Theorem 2. For any k-limiting recursive length measure, programs are (k+l)-limiting

• r.e. in order of nondecreasing length.

Proof. There exists a recursive function f such that (l/ X) (3m 1 J (vn 1 >m 1 ) ... b mk) (Vnk>mk) [ f (x, n 1 , ··· , nk) = I x I J. ( 4) Let g (i) = ( ~xe:Si) (Vye:Si) [I x i ~ I vi J for all i, where s 0 =N, si+l=Si-{g(i)}. Thus g enumerates programs (actually , their indices) in order of nondecreasing length. Analogously let h(i,n,n 1 , .·. ,nk) = (~xe:Sin) (Vye:Sin) [f(x,n 1 , ... ,nk) ~ f(y,n 1 , ... ,nk) J for all i,n,n 1 , ··. ,nk, where s 0 n = { O, .·· ,n},Si+l,n = (Sin-{h(i,n,n 1 , ... ,nk) })u{n} for all i,n. As Sin is finite for all i,n and f is recursive, h is also recursive.

For x~n the first auantifier in (4) is bounded and can be passed through the others: ttm 1 ) (Vn 1 >m 1 ) ... (3mk) (ll nk>mk) ( V x~ n) [ f(x,n 1 , ·.. ,nk) = lxi J. From the definition of h (Vi) (li n) (3m 1 ) (Vn 1 >m 1 ) ... (3mk) (ll nk >mk) [h(i,n,n 1 , ... ,nk) = (~xe:Sin) (lfye:Sin) [ f (x, n 1 , ... , nk l ~ f (y, n 1 , ... , nk) J J . By Corollary 1.1, (5) & (6) give (Vi) (Vn) (3m 1 J {fl n 1 >m 1 J ··· (3mk) (\lnk >mk) [h(i,n,n 1 , ... ,nk) = (~xe:Sin) (!iye:Sin) [f(x ,n 1 , ... ,nk) ~f(y,n 1 , ... ,nk) J & {\lx~n)[f(x,n 1 , ... ,nk) = lx l J & I y I J J. Since, x,y~ n in the definition of h, (5) (6) {\;li) (\t'n) (3m 1 ) (Vn 1 >m 1 ) ... 8mk) (Vnk>mk) (7)

For any given i, let m = max{g(j) lj ~ i } . Then for all n>m, all j ~ i and all choices of n1 , ... ,nk which guarantee the eauality in (7), it is easily shown by induction on j that s. Jn Hence sj-{xlx>n} and h(j,n,n 1 , ... ,nk) = g(j). (Vi) (3m) (lf n>m) 0:Tm 1 J (Vn 1 >m 1 J ···

so that g is (k+l)-limiting recursive.

Roughly speaking, Theorem 3 states that finding minimal programs is no more difficult than enumerating programs in order of nondecreasing length or deciding whether a given program realizes a given description (whichever is harder), where the "difficulty" of a k-limiting recursive functional is k.

Theorem 3. Given: a programmable machine M, a length measure such that programs are klimiting r.e. in order of nondecreasing length, and a set ~ of realizable, uniformly k-limiting decidable program descriptions.

Then the program minimization problem for ~ is k-limiting recursively solvable.

Proof: Since programs are k-limiting r.e. in order of nondecreasing length, there is a k-limiting recursive function f which maps N onto N such that j >i ~ l f(j) l~l f(i) I . Also, since program descriptions are uniformly klimiting decidable, there is a predicate P such that for all c5e: 6 and xe:N, P( cS ,x) # 6(x).

Let i c5 = ViP(c5,f(i)); thus ITf6/ is the first minimal program realizing 6 in the sequence ITQf,fTf), .... By the lemmata, ic5 is k-limiting recursive on ~ .

Theorem 4. Given: a k-limiting recursive length measure such that programs are klimiting r.e. in order of non-decreasing length and a set ~ of realizable, uniformly k-limiting decidable program descriptions.

Then the problem of finding all minimal programs realizing any c5 e:~ is k-limiting recursively solvable.

Proof: Define i c5 as in the proof of I Theorem 3 and let i c5 = vH lf(i) I >l f(i c5 ) I J. The predicate expressed by the bracketed inequality , i.e. {<c5 ,i>ll f(i)l >l f(i c5 ) 1, c5e:~,i e: N}, is k-limiting decidable by Lemma 2, as f, i c5 ' I I , and the characteristic function of { <x,y>lx>y} are all k-limiting recursive. Hence by Lemma 3 i c5 is k-limiting recursive on ~.

Now if the set of indices of the minimal programs realizing o is expressed by its canonical index

where CP is the characteristic function of P, with P defined as in Theorem 3, then application of Lemma 2 shows 1 0 to be k­ limiting recursive on ~.

Note that because of the assumption in Theorem 4 that the length .measure is klimiting recursive, Theorem 3 cannot be regarded as a consequence of Theorem 4. Note also that any (k-1)-limiting recursive length measure satisfies the conditions of Theorem 4 (by Theorem 2).

Theorems 3 and 4 are the main results of this paper. The remaining theorems illustrate their application.

Theorem 5. For any recursive length measure, the problem of finding all minimal programs for finite programmable functions is limiting recursive (each finite function is assumed to be specified by a program description which lists the argument-value pairs of the function in any order) .

Proof: By Theorem 2, programs are limiting r.e. in order of nondecreasing length. Let the finite function encoded by any particular o e:~ be { <yf,zf >1 i s n 0 }. Let Q={<o ,x,n> l for all i s n 0 , M with program x and input yf halts within n step s with output z~ } . Clearly Q is decidable and (;/ o£1'1) (Vx) (:tm) (Vn >m) [Q(o,x,n) ::P(o,x) J, where P( o ,x) (9 iS(x). Hence the problem of finding all minimal programs for any finite function is limiting recursive.

Theorem 6. Given a recursive length measure and a machine M which computes total functions only, the problem of finding minimal programs for functions programmable on M is limiting recursive (each programmable function is assumed to be specified by a program description which lists the argument­ value pairs of the function in any order) ·

Proof: For all i'th argument-value pair specified by any description a,· and let Q={ <o ,x,n> l for all - -a i s n, M with program x and input yi computes - a} output zi · Q is decidable since M always halts; if there is an m such that M fails to -a -a output zm with program x and input Ym ' then Q( o ,x,n) will be false for all n >m; if there is no such m (so that x realizes iS), then Q( o ,x,n) is true for all n. Evidently the descriptions are uniformly limiting decidable and the theorem follows.

Gold had already shown that the problem of finding any programs (not necessarily minimal) for members of a r.e. class of total functions is limiting recursive, and Feldman [ 2 ] remarked that this can be extended in an 6 obvious way to finding minimal programs when programs are r.e. in order of nondecreasing length. Theorem 6 strengthens this result slightly, as there are recursive length measures for which programs are not r.e. in order of nondecreasing length (e.g., define I so that the sequence I 0 I , I ll , 12 1 , ·.. enumerates a r.e., nonrecursive set without repetition).

Theorem 7. For any M and any limiting recursive length measure, the problem of finding minimal programs for functions programmable on M is 2-limiting recursive (as in Theorem 6, the problem is interpreted in terms of program descriptions, where any description lists the argument-value pairs of a programmable function in any order) .

Proof: Let Q={ <o,x,n 1 ,n 2 >1 for all i s n 1 , -a M with program x and input yi halts within -a a o n 2 steps with output zi}' with yi, zi defined as in Theorem 6. For fixed o ,x,n 1 , Q(o,x,n 1 ,n 2 ) holds in the limit of large n 2 iff x is a program x is a program for for { <y~,zf>1i s n1L { <y ~ ,z~>li£N}, then ~ ~ If (Vn 1 )limn Q(o,x,n 1 ,n 2 ); if not, there is a 0 0 2 o 0 pa~r <ym ,zm>' conta~ned in all sets { <yf,zf >1i s n 1 } for which n 1 >m, such that M - -o with program x fails to compute output zm -o for input ym; hence (Vn 1 >m) limn 2 Q(o,x,n 1 ,n 2 l. It follows that the descriptions are uniformly 2-limiting decidable. Since programs are 2limiting r.e. in order of nondecreasinq length by Theorem 2, the program minimization problem is 2-limiting recursive.

Note that it is known from the work of Gold that the problem is not in general limiting

recursive.

The theorem is readily generalized to

descriptions which prescribe divergent computations for some inputs. The minimization problem remains 2-limiting recursive.

1. Remarks on Induction and Iterated Limiting Recursion

Deduction is concerned with the derivation of particular consequences from aeneral premises, while induction proceeds in the opposite direction. The problem of finding an algorithm (minimal or otherwise) for a function, after inspection of some but not all values of the function, is clearly of the inductive type: the complete algorithm proposed on the basis of incomplete information expresses a generalization about the function sampled. Non-trivial inductive problems are inherently "unsolvable" in the sense that no terminating procedure exists for generating "correct" generalizations; any unverified consequence of a proposed generalization may turn out to be in error. This motivated Gold's definition of limiting recursive predicates and functionals, which are more powerful than their non-limiting counterparts. He noted that a "thinker" employing a procedure for function (or "black­ box") identification in the limit and using the current guess of a function's identity as a basis for goal-directed activity would be acting on correct information eventually. In this sense, therefore, some unsolvable problems are within the reach of mechanical procedures. The most general function identification problem, however, is 2-limiting recursive. Can any mechanical system be conceived which in some sense "solves" a 2limiting recursive problem? Not if attention is restricted to a single "thinker" generating a single sequence of guesses; however, suppose that instead of a single thinker, each of an ever growing number of such thinkers T 0 ,T 1 , ... with universal computational power observes the non-terminating sequence <y 0 ,z 0 >, <y 1 ,z 1 >, .·· which enumerates some partial recursive function ¢. At any time the i'th thinker Ti regards as his best guess the shortest program (if any ) he has been able to find which, in the time available, has given correct outputs for inputs y 0 ,y 1 , ..· , y i and either no output or a correct output for any other argument tested. It is clear that each thinker will eventually be guessing a program for a subset of ¢1 furthermore, all but a finite ·number of the thinkers will be guessing programs for ¢ eventually. In this iterated limiting sense the expanding community successfully identifies ¢. Of course there is no strategy effective in the limit for deciding in general which thinkers are guessing programs for ¢ at any time. To interpret third-order limit processes, one might envisage a growing number of expanding communities of the above type, each committed to a distinct value of a certain parameter. At most finitely many of the unbounded communities would in, general be "unsuccessful". Similarly still higher­ order processes could be interpreted.

Acknowledgement

I am indebted to C.G. Morgan for several stimulating and helpful discussions and to J.R. Sampson for his many useful comments on the manuscript. I.N. Chen's help on some aspects of the paper is also gratefully acknowledged. The research was conducted under a National Research Council postdoctorate fellowship.

Footnotes

1 A code into total functions would also be used for a mixture of finite and infinite descriptions; one digit, say 0, would be reserved as terminator and all function values corresponding to point~ beyQnd the end ot a finite description would be set to 0.

2 For the finite decision functions, note that the functions computed with any finite set of programs can be diagonalized to yield a finite decision function which requires a program not in the given set. To prove infinite diversity for the 2-element decision functions, it is sufficient to show that no set of n programs can include a program for each 2element decision function whose arguments are in a fixed set of 2n+l integers; but for this many arguments at least 2 of the programs must give identic~l results (if any), so that two unsymmetric decision functions are missed. 3 Functions are regarded as a special case of

functionals;

4 The equivalence follows from the fact that r(c) is independent of nl, ·.· ,nk' so that the iterated limit of G must exist.

5_ _This differs from Gold's definition, which expresses limiting recursive enumerability in terms of limiting semi-decidability. However, the definitions can be shown to be equivalent (for k=ll .

6 Actually, Feldman was concerned with "occams enumerations" of formal grammars, but the problem of finding minimal grammars for languages is essentially the same as that of finding minimal programs for decision functions.