LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 510.84 Ufcr no.708-7H dop. 2 Digitized by the Internet Archive in 2013 http://archive.org/details/recursivenatureo708pete z^ UIUCDCS-R-75-708 UIUC-ENG-R-75-2539 THE RECURSIVE NATURE OF DESCRIPTIONS: A FIXED POINT by Larry J. Peterson April, 1975 BCL No. 252 MAY 71973 DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN rhriSMi lllBMki THE RECURSIVE NATURE OF DESCRIPTIONS: A FIXED POINT* BY Larry J. Peterson Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 61801 April 1975 *In part supported by a grant from Point Foundation, San Francisco, CA, through the Biological Computer Laboratory, The University of Illinois, Urbana, Illinois 61801. THE RECURSIVE NATURE OF DESCRIPTIONS: A FIXED POINT Larry James Peterson, Ph.D. Department of Computer Science University of Illinois at Urbana-Champaign, 1975 The intuitive notion of description is formalized in a manner which reflects the computable nature of descriptions. Both the denotative and connotative aspects of description are indicated in the formalization. The structures arising from the repeated application of an interpretation to the result of the previous interpretation of a description is examined. The notion of a ty- description is introduced and the structure of heuristic procedures for con- structing the function t is examined. Finally, fixed point behavior of iteratively applied interpretations to descriptions is discussed and the possibility of effectively constructing self-operators is speculated about. 5i0.?4- ACKNOWLEDGMENTS There is simply not enough room here to list all those individuals who have contributed to the realization of this report. These are the people whom I have engaged in endless hours of discussion on the subjects of description and cognition, and I must thank then en ma s s e . I must single out for special thanks those people who have directed me through this experience. In particular, I express my sincere gratitude to Prof. Heinz Von Foerster, my thesis advisor, whose patience, tolerance and encouragement he has given me throughout. I wish to thank Prof. Lars LBfgren of the University of Lund in Lund, Sweden, for introducing me to the formal method. Also, I wish to give special thanks to Drs. Gordon Pask, Humerto Maturana, and Paul Weston, who have given me their time and advice. I wish to thank the Fulbright Commission for providing me with the experience of studying in Sweden under Dr. LHfgren, and in addition I wish to thank the Point Foundation whose generosity allowed the continuance of the Biological Computer Laboratory with which I have been associated since 1966. I wish to thank my typist Judy Rudicil, who, in addition to being one of the few individuals who can read my handwriting, found time in her very busy schedule to type this manuscript. The best thanks are saved until the last, for my wife, Alexis, who has shared with me every emotional aspect of the graduate experience. She has made it all worthwhile,, TABLE OF CONTENTS IV Page 1. INTRODUCTION 1 2. DESCRIPTION STRUCTURES II 2.1. Descriptions with Respect to Partial Recursive Functions 11 2.2. Description with Respect to Universal Partial Functions 19 3. INTERPRETATION FUNCTIONS FOR PARTIAL RECURSIVE FUNCTIONS .... 26 3.1.. ^-Descriptions 26 3o2. Interpretation Domains 28 3.3. Specific Interpretation Functions 38 3.4. The Structure of Breadth Types 41 3.5. Significance of the Structure of (B . . . 51 4. FIXED POINTS AND STABLE BEHAVIOR 54 4.1. The Construction of Functions with Fixed Points 54 4.2. Fixed Points for Specific Functions 60 4.3. Diagonal Arguments and Fixed Points 61 4.4. Fixed Points for Operators 65 4.4.1. Enumeration Operators 65 4.4.2. Self-Operators 71 5. CONCLUSION 74 LIST OF REFERENCES 77 APPENDIX 79 A-l. Algorithms 79 A-l.l. The Informal Notion of Algorithm 79 A-l. 2. Formalization of the Notion of Algorithm-- Church's Thesis 82 A-2. Turing Machines 83 A-3. Godel Numbering of Turing Machines and Computation Sequences „ 87 A-4. Partial Recursive Functions 91 A-4.1. The Halting Problem 94 A-4. 2. The Recursion Theorems 95 A-5. Recursively Enumerable Sets 96 A-6. Recursively Enumerable Relations 102 A-7. The Normal Form Theorem 105 VITA 107 1. INTRODUCTION Any study which uses some notion of description must use that notion in a manner consistent with the common usage of the word "description." Otherwise what is taken for a description and what is meant by a description will be two different things. The American Heritage Dictionary— defines the noun "description" as 1. The act, process or technique of describing... 2. A statement or account describing something, and it defines the verb "describe": 1. To give a verbal account of... 2. To transmit a mental image or impression of with words... Hence the common usage of the word description is: A description is a statement or verbal account which transmits a mental image or impression of something. This usage suggests the following situation. A man and his wife are in their living room. He is standing in front of a window looking out and she is sitting in a chair in a corner to the side where she cannot see out the window. He sees a man and a dog walking by and says, "I see a tall man with dark-rimmed glasses walking his dog." On hearing this she imagines a man who resembles John Wayne, wearing a long coat, a fur cap and sun glasses, and walking along the sidewalk with a large brown Great Dane on a leash. The man has described what he saw by uttering the words, "I see a tall man with dark-rimmed glasses walking his dog." She, upon hearing this, conjured up a vision of a warmly-dressed John Wayne walking with his Great Dane on a leash. He described what he saw. To him, his words, "I see a tall man with dark- rimmed glasses walking his dog," is a description of what he saw. His seeing and making a statement constitute the commonly accepted paradigm for the process of description, and everyone agrees that the man's words are a description of what he saw. On the other hand, the following question arises: In what sense are his words a description for his wife? She might have been preoccupied with her own thoughts and might not have heard him speak at all. In this case, his words described nothing to her because she imagined nothing from them. When she imagined a John Wayne type walking his dog, she interpreted what she heard, in the other case she gave no interpretation to the sounds which fell on her ears. That is, in one case, the sounds she heard were a description (of what she imagined to be the case), and in the other case, the sounds described nothing to her. Nearly everyone would agree that in both situations, the man's words con- stitute a description. In the first case they constitute a description of what he saw and also for what she imagined. In the second case, his words constitute a description of what he saw, but not of what she imagined, for she gave no meaning to his words. Whether or not she interprets his words, we still accept them as a description, i.e., we assume they are interpretable. Consider another situation in which a man is bear hunting. He sees impres- sions in some loose soil. Upon seeing their shape, he exclaims, "Bear tracks." He then notices a track which lacks an imprint of the leftmost toe. He exclaims, "Slewfoot," the name he has given to a bear he has tracked for three years. The presence of these tracks leaves no doubt in his mind as to their origin. They describe to him the recent presence of a particular bear. The tracks are, to the hunter, a description of a bear, just as fingerprints are to a detective descriptions of people. A glacier describes to a geologist the history of a region over a period of centuries. A scar on a man's cheek describes to a fencer a duel in which the man fought. These latter examples indicate the connotative aspect of description. Someone interprets something (tracks, fingerprints, a glacier, a smell, a sound, a light pattern) and produces something meaningful to him (a vision of Slewfoot, a vision of Jack The Ripper, the mean annual temperature in a certain region from 1822 to the present). This indicates that a thing which connotes something to someone is a description to that person of what it connotes (of what he inter- prets it as). This I state as the connotative principle of description . Any thing which is interpretable is a description of that which is produced under the interpretation. The man looking out his window made a statement. The intention of that statement was that it should be taken as a description of what he saw. That description is then a denotative description for the man since he produced it for the purpose of denoting something, i.e., what he saw. That same statement may or may not be interpreted by his wife, but it still qualifies as a description since it is interpretable. It is the purpose of this report to formalize the notion of description in such a manner that both its connotative and denotative aspects are easily indi- cated and dealt with as abstract entities. First, however, some examples from the literature in which notions of description are used will be presented in order to broaden the scope of the notion of description. Notions of description arise in such diverse fields as computer science, biology, anthropology, physics and mathematics. For instance, in the study of 2/ cognitive systems, Maturana - uses three different notions of description. One notion arises when he discusses the role of an observer. For the observer an entity is an entity when he can describe it. To describe is to enumerate the actual or potential interaction and relations of the described entity. Thus, the describing of the entity produces a denotative description, for it is assumed that someone interprets the description as an enumeration of inter- actions and relations. His second notion of description arises when the observer considers the relationship between an organism and its niche: Since the niche of an organism is the set of all classes of inter- actions into which it can enter, and the observer beholds the organism in an environment that he defines, for him any of the organism's behaviors appears as an actualization of the niche, that is, as a first order description of the environment (henceforth denoted by a capital D: Description). This Description, however, is a descrip- tion in terms of behavior (interactions) of the observed organism, not of representations of environmental states, and the relation between behavior and niche lies exclusively in the cognitive domain of the observer. 3 4/ This same notion of description is used by Von Foerster — ' — and Weston and Von Foerster. - This usage of description is connotative since the observer is interpreting movements of an organism as actualizations of its niche. Maturana introduces a third notion of description when he discusses how one organism can modify the behavior of a second: ...the first organism generates (as is apparent for the observer) a Description of its niche that, in addition to its own significance as a behavior (within the cognitive domain of the first organism, and independently of it), orients the second organism within its cognitive domain to an interaction from which ensues a conduct parallel to that of the first one, but unrelated to it. The conduct thus elicited by the orienting behavior is denotative: it points to a feature of the environment that the second organism encounters in its niche and Describes by the appropriate conduct, and that he can treat as an independent entity. The orienting behavior is, for the observer, a second order description (henceforth denoted by italics: description ) that represents that which he considers it to denote. Contrariwise, the orienting behavior of the first organism is connota- tive for the second one, and implies for it an interaction within its cognitive domain which, if actualized, originates a behavior that Describes a particular aspect of its niche; that which an orienting behavior connotes is a function of the cognitive domain of the orientee, not the orienter. It should be noted that Maturana 's description closely parallels the common usage of description but is broader in concept in that he presents the notion in terms of orienting behavior and states further that this orienting behavior is the basis for linguistic behavior--that behavior which is already presupposed in the common usage. Much of the recent work in pattern recognition involves the mechanistic generation of descriptions - which can be used for such purposes as classifying objects, generating scenes and answering questions about scenes under analysis. Narasimhan - indicates that two kinds of descriptions are possible: (1) either a generative description such that given this description an instance of the desired picture could be generated; (2) or an interpretative description which is the outcome of the analysis of a given, specific, input picture. These classes of descriptions are seen to be connotative and denotative, respectively, although an interpretative description can be interpreted as 8 9 / indicating one of several classes of objects. Michalski — J — demonstrates a system which employs a language in which a description, that is minimal in a strictly defined sense, is produced from a collection of classes of objects. This minimal description can be used to determine to which class a given object belongs. His descriptions are well-formed formulas in a variable-valued logic system and are produced by associating various symbols of the language with primitive objects and relations occurring in a graphic picture. The formulas produced are in disjunctive form and are minimized using covering- theoretical methods of switching theory. These descriptions are interpretative descriptions, and therefore denotative. However, since they can be interpreted as indicating to which class an object belongs, they are also connotative. Lofgren, — in formalizing notions of reproduction, learning, order, under- standing and evolution, relies on a connotative definition of description. His definition is the following: Let x and z_ be words in the alphabet of a universal Turing machine, U, with code number u. Then x is said to be a description of -l_ with respect to u_ if JJ computes z^ from the standard initial tape expression x, that is f u (x) = z. In this context, a number x, can be the description of, at most, one other number. In fact some numbers are not descriptive in that they produce no other number when computed on by U. LBfgren's definition of description is based on the computation of a universal Turing machine. It is well known that a universal Turing machine can be programmed to carry out the computation of the function which any other Turing machine performs. Specifically, the input to a univer- sal Turing machine, x, has the further interpretation that it is an encoding of the name of another Turing machine, say with code number w, and an input to it, say v. If the Turing machine so named operates on its input, it produces the same result, z^, as the universal Turing machine whose input is that encoding, x. In some sense then, the input v, to the encoded Turing machine w, can be considered a description of z_, with respect to that Turing machine (which in general is not universal). The use of natural numbers to represent objects is natural if one considers that, in order to be useful, descriptions must be of finite character lest they be incomprehensible to a human mind. In addition, it seems natural to assume that an algorithmic function can be used to interpret the description. This is because a connotative description does produce something, and in order to be useful, intuitively the function interpreting the description should be specifiable. Turing machines are one class of objects with which functions may be specified. This suggests that the connotative definition of description might be generalized so that descriptions are defined with respect to an arbitrary Turing machine, thereby providing a computation environment of various degrees of computational complexity in which to interpret descriptions. In addition to Turing machines, there are mechanisms such as Church's X-calculus and Kleene's system of general recursive functions which compute the same class of functions that Turing machines compute. This class of functions has become known as the class of partial recursive functions. For each partial recursive function there is a procedure in each of these systems which computes that function. Therefore, if we choose a partial recursive function to inter- pret a description, we can be assured that there is a computational procedure which will compute that function (interpretation). With these considerations in mind, the connotative aspect of description will be formalized as follows. If z is a number of a procedure (e.g., the number associated with a particular Turing machine) and cp denotes the partial recursive function computed by that procedure, then for each pair (x,y) such that cp (x) = y, x will be considered a description of y with respect to z (a name of the interpreting function). In particular, if z is the number of the procedure associated with a universal Turing machine, then this definition reduces to Lofgren's definition of description with respect to a universal Turing machine . Some of the consequences of this definition are shown in chapter 2. In particular, the consequences of the repeated application of a given interpreting function to the result of its previous computation is discussed. This repeated application of an interpreting function gives rise to description sequences such that each member of the sequence is a description of its successor with respect to the interpreting function. Some theorems are proved about such description sequences whose interpreting function is computed by a universal Turing machine . The idea of a universal Turing machine UTM computing on an encoding of the number z of some other Turing machine M and of an input y to that machine, and producing exactly the same result as M operating on y, gives rise to a formula- tion of the denotative aspect of a description. For suppose u is the code number of a universal Turing machine (which computes the partial recursive function cp ) , and for some pair (x,y), cp (x) = y. Then by the connotative definition of description, x is a description of y with respect to u. In addi- tion, x is an encoding of some pair (w,v) and cp (v) = y. If we shift our point of view from x to the pair (w,v) then the encoding function, \|f, which produces x from the pair (w,v) is in fact producing a description from the pair (w,v). In this sense, x is a denotative description of the pair (w,v). That is, in Narasimhan's terms, x is an interpretative description, and t|i is an interpreta- tive function for x. The question then arises: if given any z and some pair, (x,y), where cp (x) = y, can x be considered a denotative description of some other pair (w,v) such that cp (v) = y? That is, does there exist some function i|/ such w that for some pair (w,v): 1. f(w,v) = x 2. cp z (x) = y and 3. cp (v) = y ? w If for such an x (which is a connotative description of y) there does exist a function t such that relations 1-3 hold, then x is an interpretative descrip- tion (denotative description) of the pair (w,v), with interpretative function i|i. Again, the usefulness of such a notion depends on the ability to compute x from a pair (w,v), that is, it depends on whether ty is itself a partial recur- sive function. In chapter 3, x is defined to be a ^-description, if | is a partial recursive function such that relations 1-3 above hold. As will be shown in chapter 3, if x is a description of y with respect to z, then there does in fact exist such a partial recursive function t such that x is a f- description. As it turns out, any x is both a connotative description (there is a y and a z such that cp (x) = y) and a denotative description (since it is a ^-description). Consider the pattern recognition problem. A programmer, wishing to write a program which classifies various objects into groups, has a priori a method whereby he can classify those objects. If v represents an object he_ wishes to classify, w represents his classification procedure and y represents his classification of x, then this situation might be represented as cp (v) = y. w Now, in his program he constructs two procedures. The first procedure forms a description of the object (represented by v) he wishes to classify. The descrip- tion formed also reflects his classification procedure (w) in that its structure is in a form which will be easily interpretable by the second of the two procedures he constructs. This second procedure will give an output from the description it receives which indicates the same class which the programmer would have chosen for the object. If the two procedures are represented by i and cp respectively, then the situation just described is represented by the following: 1. cp (v) = y (the programmer's classification) w 2. f(w,v) = x (the description produced by the first procedure) 3. cp (x) = y (the classification of the description by the second procedure) . For a successful pattern recognition scheme, (t,cp ), a given object (v) will always be given the same classification (y) according to 1 and 3 above. Chapter 3 explores the consequences of ^-description. In particular, it shows that for an interpreting function cp (for connotative descriptions), there is a partial recursive interpretative function, i|i, which is complete in the sense that for any pair (x,y) such that cp (x) = y and for any pair (w,v), H w >v) = x if and only if cp (v) = y. The significance of this is that someone, 10 wishing to give an account of the behavior of some observable (but unknown) function (which might be the function cp ), can construct a function ty which maps behaviors, apparent to the observer, of the observable function into the domain of that function in a manner such that the outcome of the function is the same as the outcome predicted by the observer. In practice this mapping function constructed by the observer may not map every possible situation which might be apparent to the observer, but if the observer discovered (through astute observation or experimentation) new (to him) behaviors of the function, he can modify his function i|i to account for this behavior. He knows he can construct (in theory) a complete function t, but he may never know when it is complete. This situation is discussed in depth in chapter 3. Iteratively applying an interpreting function to a connotative description can lead to problems of self-reference which may or may not give rise to stable behavior of the iterative procedure. Stable behavior is evidenced by the appearance of fixed points or cyclic description loops for the given inter- preting function. This type of behavior is examined in chapter 4 not only with respect to functions, but also with respect to higher order operators. Also it is speculated in chapter 4 about the possibility of effectively constructing self-operators, that is, operators which operate upon themselves to produce themselves . The Appendix contains an outline of all the recursive notions and theorems upon which the text depends. Theorems, definitions, corollaries, lemmas and examples are all numbered sequentially according to the chapter in which they appear. For instance, Theorem 2.2 is the second theorem in chapter 2. Defini- tion A-4 is the fourth definition in the Appendix. 11 2. DESCRIPTION STRUCTURES Descriptions, as they are subsequently discussed, are to be regarded as codings of finite procedures from which some other object may be produced in some computational environment. Ordinarily, descriptions of things, objects, concepts, etc., are constructed by some agent in some language and they usually appear as strings of symbols in that language. It is the relation between that string of symbols and what is produced from it in some surround- ing which will now be examined. 2.1. Descriptions with Respect to Partial Recursive Functions Definition 2.1 If z is the code number of a partial recursive function and x and y are two numbers such that vp (x) = y, then x _is a description of y_ with respect to z_. This is denoted by Des(x,y,z). Definition 2.L is a very general representation of the form of descrip- tion in which an object y is produced from x in the computation environment denoted by z. The following explores some of the ramifications of this definition. Theorem 2.1 In general, it is undecidable whether Des(x,y,z) holds. Proof: Des(x,y,z) holds if and only if cp (x) = y. But to determine whether cp (x) = y involves determining the value of cp (x) if it is defined. But this is just the halting problem (Theorem A-5) , which is itself undecidable. Hence, to decide whether Des(x,y,z) holds implies that it is possible to decide whether Cp (x) = y. This implies that the halting problem is decidable. Therefore, by contradiction, Des(x,y,z) is undecidable. Q.E.D. 12 What this theorem shows is that there is no general algorithm which, for a given z allows one to determine whether x is a description of y. On the other hand, given z and y, the set of descriptions of y with respect to z can be enumerated. That is, the set D = [x:Des (x,y ,z) } is recursively enumerable. zy Theorem 2.2 D is recursively enumerable, zy Proof: xeD if and only if Des(x,y,z) holds. But Des(x,y,z) holds if and only zy if cp (x) = y, which is true if and only if ]w[T(z,x,w) & y = U(w)]. Here T is the Kleene T-predicate and U produces the value of the final term in the coded sequence of terms with value w. According to the Projection Theorem, this final expression is recursively enumerable because the expression in brackets is recursive ( Corollary A-3 ). Hence D is recursively enumerable. Q.E.D. One way to generate a list of the elements of D would be to use the zy following dove-tail scheme. Namely, perform one step of computation on cp (0). If the computation halts naturally, compare the value produced with y. If the values are equal, place on the list (i.e., is a description of y with re- spect to z). Next do two steps of computation on cp (0) and cp (1). If any values are produced, compare them with y. If a match is found, add the corresponding argument to the list. Proceed this way, perform n+1 computations on cp (0),cp (l), ,#, ,vp (n) , compare any values produced with y and add the corresponding argument to the list. Continuance of this procedure will generate all the elements of D . It should be noted that it still is not possible to zy determine in general whether some number n is a description of y since we may be kept waiting forever for it to appear on the list. Thus, for any partial recursive function and any value y, all the des- criptions for y may be generated. If a particular y has no description with 13 respect to a given z, then the above method would have one computing forever without producing a description. This method then would not explicitly demon- strate that y has no descriptions with respect to z. Such knowledge would have to be discovered with a case-by-case study. A slight modification of the above dove-tail listing would produce all the pairs (x,y) such that for a given z, cp (x) = y. That is it enumerates the set C(x,y): cp z (x) = y} . The list is generated by computing n+1 steps of the procedures for cp z (0),q) z (l),---,cp z (n) and whenever a value y is produced, the pair, consisting of the argument which produced y, and y is added to the list. Suppose for some z , Des (x ,y ,z ). It is possible that y is a descrip- rr oooo o tion of, say, y, , with respect to z , i.e., Des(y ,y.,z ). In this case x 1 o o 1 o o is a description of a description of y 1 . In general, D is non-empty and o 1 for any yeD , in general D is non-empty. Description chains arise from Vl these considerations. z y ' z y o y l o J Definition 2.2 If the sequence of pairs (y , y ), (y ,y„ ),•••, (y . ,y ) is a subset of cp , then the sequence y ,y_ , • • • ,y is a description chain of 'z, ., y o y 1 n c length _n with respect: to z_. Example 2.1 Let z be the code number for a function which computes the successor function defined by: s(x) = x+1 . That is, 14 rr> (x) = x+1 . T z Then any sequence of consecutive integers is a description chain with respect to z. The set of natural numbers N is such an infinite chain. Description chains may loop on themselves. Definition 2.3 If the sequence (y Q ,y, ) , (y 1 3 y 2 ) , • • • , (y^ ,y n ) , (y n ,y Q ) is a sub- set of some cp , then the sequence y , • • • ,y is a description loop with respect to z_ and has length n-f-1 . A description loop of length one is called a fixed point . Example 2.2 Let z be the code number for a function which computes the identity function. I.e.: cp z (x) = x . Then every number n is a fixed point for z. Trivially, every number is a description of itself with respect to z. A se t cp may yield the description chain y ,y 1 , • • • ,y , and cp (y ) is undefined. Such a chain is called a terminating description chain and the element y is called the terminus. J n For any function, the description chains may be infinite without loops, finite terminating, or may have a loop. Obviously, a description chain may not have more than one loop, because otherwise, for some value x, cp (x) would have more than one value, which is not possible. A description chain with a loop, then, cannot be a terminating chain. For any given y and z, Theorem 2.2 shows that D can be enumerated. Hence, for x eD , D can be enumerated, for x. eD , D can be enumerated, o zy zx 1 zx zx n J o o 1 and so on. 15 Definition 2.4 Let x eD .x.eD , • • • ,x £D , then the sequence x ,x, , • • • ,x o zy' 1 zx n zx ' n o' 1 ' n is a regressive description chain of length n+1 for y_ with res - pect to z . A description chain of length n with respect to z and beginning with y is called a progressive description chain from y_ with respect to z_ c^f length n. Example 2.3 Let z be the Godel number for a function which computes the successor function. Then for any y, the regressive description chain is always finite with respect to z. This is because D =0. However, each y has an infinite r zo ' ; progressive description chain with respect to z. Example 2.4 Let z be the Godel number for a recursive function which computes the predecessor function defined by: f(0) = f(x+l) = x for all x > 0. Then any y has an infinite regressive description chain with respect to z. This is because D = [O.l], D . = (2 }, D _ = {4 J, ■••ad infinitum . zo zl z3 Example 2.5 Let z be the Godel number of a recursive function which computes the function defined by: f(0) = 1 f(x) = x+2 for x odd f(x) = x-2 for x even and non-zero. Then any y has an infinite progressive description chain as well as an infinite regressive description chain with respect to z. 16 » t » t i » f r • 1 « • ' i , i t • • » i i • (a) Infinite progressive description chain. (b) Looping description chain. • • » (c) Terminating description chain. Figure 2.1. Description structures possible for partial recursive functions. 17 If cp is a many-to-one function, there are values y such that D has r z J Z y cardinality greater than one. Therefore if one considers graphs of all the description chains possible for the various partial recursive functions, the "web-like" structures of Figure 2.1 occur, where the nodes represent natural numbers, and the arcs indicate the computation such that the node at the tail represents the description of the node at the head of the arc. A description chain may be considered bounded under certain conditions. Definition 2 . 5 Let C,, 7 be the numbers in a description chain progressing from y as far as possible and regressing from y along some path as far as possible. The C zy has a backward bound or source if there is an xeC zv such that D = 0. Q z has a forward bound if a pro- gressive description chain from y with respect to z either has a terminus, or contains a Loop. A description chain with neither a backward bound nor a forward bound is unbounded . From this definition it is seen that the function in Example 2.3 has a description chain with a source but no forward bound; the function in Example 2.4 has a description chain with no source, but it does have a forward bound, namely the fixed point 0; and the function in Example 2.5 has an unbounded description chain. For any z, the domain of cp , dom(cp ) can be partitioned on the basis of the types of description chains which occur with respect to z. Definition 2.6 T Let D be the set of numbers in all the terminating descrip- tion chains with respect to z such that if x is a terminus, x^D„ and D_ v c D„ . D„ is called the domain of terminating £ ZX *~~ Z, ^ -r -*- ^— ^— — — — — — "'■"■ ,1 " ■ ■ descriptions for z. Let Dt 1 be the set of numbers in all the t Z T description chains with respect to z and which have loops. D is called the domain of looping descriptions for z_. Let D be the set of numbers in all the forward unbounded description chains with respect to z. D„ is then called the domain of for - ward unbounded descriptions for z_. Denote the domain of cp_ , dom(rp ) by D z and the range of cp_ by R z . 18 Corollary 2.1 For every z the following holds 1) d t n D L = z z 2) d t n D U = z z 3) d l n D U = z z 4) D T U D L U D U = D . z z z z Since

D . Associated with each integer 0,l,'**,t will be a list of numbers L ,L, ••*,L and a computation sequence c .c 1 , ,,, ,.c i . which begins by commenc- o'l''t v olt ° J ing computation of cp (0),vp (l), ••♦,($> (t) . Stage 0: perform steps of computation on cp (0) Stage t: perform t steps of computation on the computation sequences c c • • • c o' l' ' t 19 If before t steps are completed on say c., a result turns up, compare the argument from which that result occurred with the list L. . 1. If the argument is on the list, a loop has been found and L. is added to D (t) . r z 2. If that argument does not appear in L. , add it to L. and restart C. with the new result as the new computation argument . 3. Proceed according to 1 and 2 until the t steps of computation are completed. Increment t and perform the operation of stage t. As t increases, more and more description chains with loops will be added to D (t), and in the limit, D will be generated. T U This type of construction cannot be used to generate D and D because, U T by definition, D r has no loops and D has forward bounds which are termini. If a terminus is used as an argument in a computation sequence, that computation will never halt. L T U For a given z, if D ^ 0, then at least one of D , D and D must not be z z z z empty. However, one or two of them may be. For instance, in Example 2.5, L T U D = D =0 and D = D = N. There is, however, a class of partial recursive, z z z z ' ' ^ ' but not recursive, functions for which all these sets are non-empty. These are the class of universal partial functions which, under the proper interpre- tation, perform the same computation as any partial recursive function. 2.2. Description with Respect to Universal Partial Functions The notion of a function which is capable of computing any function which is computable by any partial recursive function arises when one attempts to carry out the following procedure which defines a partial function, t(z,x) — ' : 20 1. Given the GBdel number z for some partial recursive function and an argument x, generate the sequence of instructions M ,M, ■ ■ • , o 1 ' until M is generated. z ° 2. Apply the instructions M to the argument x. 3. If and when a value is returned i|f(z,x) takes this value. 4. If no value is returned f(z,x) is not defined. This procedure is effective since for any z the instruction set will always be found and the value given to i|>(z,x) depends on whether M operating on x returns a value. Therefore the function ^(z,x) is defined by: Kz,x) = i cp (x) if cp (x) converges undefined if cp (x) diverges . By Church's Thesis, t is partial recursive and, therefore, there exists a Godel number u such that cp (z,x) = i|f(z,x). This fact Rogers - states as a theorem. Theorem 2.4 (Enumeration Theorem) There exists a u such that for all z and x, cp (z,x) = cp z (x) if cp z (x) is defined, and cp (z,x) is undefined if cp (y) is undefined. Definition 2.7 Such a function cp is called a un iversal partial func t ion . T u The notion of universal partial function can be extended to include cer- tain functions of one variable whose argument is an encoding of a pair of numbers (x,y). For instance, consider the recursive function defined by — ': c(x,y) = sL(x+y) +3x+y] . 21 It is easily seen that no matter what values for x and y are chosen, the expression in brackets always yields an even number. In fact, c(x,y) associates the pair (0,0) with 0, (0,1) with 1, (1,0) with 2, (0.2) with 3, and so on. This is summarized in Table 2.1. 1 2 3 4 5 6 •■ • 1 3 6 10 15 21 1 2 4 7 11 16 22 2 5 8 12 17 23 3 9 13 18 24 4 14 19 25 5 20 26 etc . 6 27 • Table 2.1. Values for c(x,y) = M(x+y) +3x+y] . To each pair (x,y) there is associated a unique number. Conversely, to each number in the table there corresponds a unique pair (x,y). Given some value v, there exist recursive functions i and r such that if v = c(x,y), 12/ x = £(v) and y = r(v). These functions are derived explicitly by Davis— and are called separation functions (left and right respectively). Next consider a partial function i|i of one variable which is computed as follows : 1. Given argument v, <£(v) and r(v) are computed. 2. A universal partial function from Theorem 2.4 is applied to the pair (i(v),r(v)). Then if (x,y) = (^(v),r(v)) the function ^ computes: Hv) = Hc(£(v),r(v))) = Hc(x,y)) = cp u (x,y) = cp x (y) . This function ^ can be considered universal in the sense that, from an i 22 encoding of any pair (x,y), it computes Cp (y) . A more general definition of universal partial function can then be given. U/ Definition 2.8 ^ is universal if i|i is partial recursive and if there exists a recursive f of two variables such that for all x and y, Kf(x,y)) = cp (y). From this definition several theorems follow. Theorem 2.5 (L^fgren-') The function computed by a universal partial function is partial recursive and not recursive. Proof: Let f be a universal partial function, then from Definition 2.8 and Church's Thesis it follows that ty is partial recursive and, hence, that there exists a Godel number u such that cp = ty. If cp were recursive then it T u Y u would be defined for all arguments. Then for any z, cp (x) = cp (f (z,x)) would be defined for each z and x. Hence, for every z cp is recursive. But this is clearly untrue because for example, the function computed by z. : Cp (x) = uy[x+y=0] Z l is partial recursive and not recursive. It is defined only at x = 0. Q.E.D. If u is the Godel number for a universal partial function and D is its r u domain, then the complement of its domain D = N-D is clearly non-empty. ' c u u However, as the next theorem shows, every yeN has a description with respect to u. Theorem 2.6 Let u be the Godel number of a universal partial function, for all y, card(D uy ) =(^ q . Then 23 Proof: Let z be a GBdel number of a function which computes the identity function, i.e., Cp (x) = x for all x. There are a countably infinite number ftl (Theorem A-3) of such indices z for which Cp (x) = x. Let y be any number. Then cp (y) = cp (f(z,y)) = y. But since there are a countably infinite number of z's, there are a countably infinite number of values f(z,y)eD y uy Therefore, for each y card(D ) = 9>j • Q.E.D. From Theorems 2.5 and 2.6 it can be seen that every number has a descrip- tion with respect to u but not every number is a description of another number. In fact, every number in D has a description ( Cu of then) but for every xeD , cp (x) is undefined. That is, every xeD is a terminus for some OS] u u u o many) description chain. Hence: Theorem 2.7 If u is the code word for a universal partial function, then D T * 0. u The following shows that also, neither D nor D are empty whenever u u u r J is the GcJdel number for a universal partial function. Theorem 2.8 If u is the Godel number for a universal partial function, then D» i 0. Proof: Let f be the recursive coding function for cp such that for all x and u Y u y, cp (f (x,y)) = cp (y). Then define a function i|f such that n u jc <|< (x,y) = f (x,y+l) for all x and y. Since f is recursive, ty is recursive. Hence, by the Recursion Theorem (Theorem A- 7 ), there is a Godel number e such that 24 Then for any y; 9 e (y) = Ke,y) = f u (e,y+l) P u (f u (e,y)) = cp e (y) = i|r(e,y) = f u (e,y+l) That is, for all y, f (e,y) is a description of f (e,y+l) with respect to u If v ,v ,v^,' • • , is the sequence of values for f (e,0),f (e,l),f (e,2),"*, then the sequence v , v.. , v„ , • • • , is a forward unbounded description chain with respect to u. Hence D ^ 0. Q.E.D. u The proof that D ^ when u is the Godel number for a universal partial function requires the following lemma which Lofgren - proves as a theorem. Lemma 2 . 1 Let u be a Godel number for a universal partial function. Then for each partial recursive function g(x) there exists a argument T such that cp (t) = g(T). Proof: For any z, we have cp (x) = cp (f (z,x)), where f is the recursive coding function for cp . Let g(x) be an arbitrary partial recursive function. Then the function h(x,y) = g(f (x,y)) is partial recursive. By the Recursion Theorem there exists an e such that cp (y) = h(e,y). Therefore, g(f u (e,x)) = h(e,x) = cp e (x) = cp u (f u (e,x)) . Hence, there exists an argument t = f (e,x)) such that g(T) = cp ( T ). Q.E.D. Corollary 2 P ,n If u is the Godel number for a universal partial function then for any recursive function g(x) there exists an argument t such that cp u (T) = g(T). * ii Lofgren's paper uses Turing machines as the basis for his considerations of computability . His proofs, therefore, involve demonstrating the existence of Turing machines to satisfy the conditions of the theorem. The theorems in this paper which are attributed to Lofgren are generally restatements of his theorems in terms of partial recursive functions which are identified by their Godel numbers. 25 Proof: Since g(x) is recursive it is defined for all values of x and hence it is defined for the particular argument T guaranteed by the lemma. There- fore, by the lemma, this argument T must be in the domain of rp . Q.E.D. Theorem 2.9 Let u be the GBdel number for a universal partial function. Then D L ± 0. u Proof: Since a fixed point is a loop of length one in a description chain, it need only be demonstrated that cp has a fixed point. Let g(x) be the identity function. Then g(x) is recursive. In the proof of the lemma h(x,y) = g(f (x,y)) = f (x,y). There exists an e such that cp e (x) = h(e,x) = g(f u (e,x)) = cp> u (f u (e,x)) - f u (e,x) . Thus the T = f (e,x) satisfies the relation u

v) and Cp w (v) = y. 27 One way at looking at the notion of ^-description is as follows. An observer viewing some mechanism or organism Ci identifies certain phenomena as "input" to Q, and other phenomena as "output" from Cl. He hypothesizes that there is some theoretically specifiable behavior function, cp , which relates inputs to outputs. Wishing to understand, and possibly formulate, this behavior function he views several input-output sequences. He then hypothesizes that the input, which resulted in some specific output, was an encoding to Cl of some "action command" to be performed on some "situation". The result (output) that the observer sees is consistent with what he considers is the action on what he considers is the situation. If the action command is regarded as a computation mechanism, denoted by w, and the situation is denoted by v, the observer then has hypothesized that cp (v) was computed to w produce output y. Then the action-situation pair he hypothesized was encoded as input to C is represented by i|i(w,v) and is operated on by the behavior function cp to produce y. The function i|f can then be considered an interpre - tation function of the observer for the behavioral domain of & which is computed on by cp . The graph in Figure 3.1 shows the relation between some function of the observer 0, the mechanism Cl and the interpretation function Y . The operation f is included for completeness, and in the definition of '('-description, it is simply the identity function f (x) = x for all x. The operation is simply defined by £>: (w,v) -cp (v) . (3.2) w For consistency from the observer's point of view, the relation = f _1 ni|i = Qi|i (3.3) must hold. The operation Cl is, of course, that relation which the observer 28 sees to exist between the input and output of the mechanism. The interpre- tation function i|/ is then constructed by the observer as he confirms his observations . Figure 3.1. A graphic representation of the model for ^-descriptions when j is viewed as an interpretation function, 3.2. Interpretation Domains The following investigates the structure of the description domains for cp when restricted by interpretation functions. Since the interpretation function, ty, in a ^-description is partial recursive, attention will be directed to the partial recursive functions of two variables with GBdel number i. Definition 3.2 Let z be the Godel number of a partial recursive function of one variable, and i the Godel number of a partial recursive function of two variables. Define: D (i) = [x:cp (x) converges and jw:jv[x=cp. (w,v) & cp (x) = 9 (v)]}. Z Z . J- z w D (i) is the description domain of cp restricted by the interpreta- tion function cp. . More simply, D (i; is the i-th interpretative domain for cp . What should be noted about D (i) is that there may be pairs (w,v) such that cp (cp. (w,v)) is defined but such that Cp z (9 i («>v))^ cp w (v) . 29 Such values Cp. (w,v) are not included in D (i). The following theorems follow as consequences of Definition 3.2. Theorem 3.1 For every z and i, D (i) is recursively enumerable. Proof: xeD (i) » cp (x) converges and dw3v[x= p. (w, v) & cp (x)=cp (v)] Z Z 3_ Z W « ]y{T(z,x,y) & dw] v 3tT(i ,w , v, t) & x=U(t) & 3sT(w,v,s) & U(y)=U(s)} « 3y]w]v]t3s[T(z,x,y) & T(i,w,v,t) & x=U(t) & T(w,v,s) & U(y)=U(s)J . As is the case with the expression in brackets in the proof of Theorem 2.2, the final expression in brackets is recursive. Hence, by the Projection Theorem (Theorem A- 16) , the final expression is recursively enumerable. There- fore, D (i) is recursively enumerable. Q.E.D. Theorem 3.2 For each z there exists an i such that D (i) = 0. Proof: Let 4(x,y) be a function which is not defined for any pair (x,y). Such a function is partial recursive. (Consider a set of instructions for ^ which annihilates the input and then begins computing according to a set of instruc- tions putting it into an infinite loop.) Let i be a Godel number for i)i. Then no matter what partial recursive function of one variable is considered, if z is a Godel number for that function, cp (cp.(x,y)) is undefined for all pairs (x,y). Hence D (i) is empty. Q.E.D. z Theorem 3.3 There exist two GBdel numbers z and i such that D (i) = N. z Proof: Let I be the Godel number of a recursive function which computes the function f defined by f(x,y) = y for all (x,y). 30 Let z c be the Godel number of a recursive function which returns the value c for all inputs x. That is CD (x) = c for all x. Then ffl (cp (z ,x)) = z ^z ^T c c c cp (x) = c for all x. Hence, D (I) = N. Q.E.D. Z Z c o Theorem 3.4 For each Gb'del number z and each pair (x,y) such that Cp z (x) = y, there exists a Godel number i such that x£D (i). Proof: Let I be the Godel number of the function defined in the proof of Theorem 3.3. Then for any z, x and y p z (cp 1 (z,x)) = cp z (x) = y . Q.E.D. Thus for any computation performed by a partial recursive function, there is an interpretation function for each input which produces a result. Corollary 3.1 If D = then for every i D (i) = . Z Z Although the interpretation function cp in the proof of the theorem produces a non-empty interpretative domain for any partial recursive function whose domain is non-empty, the result is trivial in that, from an observer's point of view, the input to cp is simply a restatement of the input to cp . I.e., cp does what cp does. One questions whether there is a stronger form of this theorem. The next theorem shows that there is a stronger form in which the interpretative function depends on the behavior function cp itself. Theorem 3.5 Let z be the Gb'del number of a partial recursive function, ijf, of two variables, such that: 1. The range of 4 is D . z 31 2. For every pair (x,y) in the domain of 4 ,

(r(t)) will be performed. -£(t) and r(t) are decoding functions such that if t = c(x,y) = ^[(x+y) + 3x+y], then &(t) = x and r(t) = y. Since $ is partial recursive, D is recursively enumerable. Then f(t) is the recursive function which lists the t+1 element in the enumeration of D . z When elements in lists Ll and L2 are used to form an element in list L3 , checks will be written next to the two elements involved in producing the third. However, there is a difference in the meaning of a check next to an entry in list Ll and a check next to an entry in list L2 . Although an un- marked entry in either list Ll or L2 , at some stage, is eligible for use in the formation of an element in list L3 , once an entry in list Ll has been checked, it cannot be used in the formation of another triplet in list L3; whereas, an entry in list L2 which has been checked may be used many times in the formation of different triplets in list L3 . 32 Conceptually the lists are constructed as follows. Some finite number of computations is performed on the expressions cp (v ),•••, cD (v ) . Each comou- w o Y w n o n tation which halts in the meantime results in the placing of a triplet on list LI. For instance, if cp (v ) halted in n or less steps and produced 8 value y then the triplet (w ,v ,y ) is placed on Ll if it already has not appeared on the list at an earlier stage. List L2 is then searched, comparing y_ with the second argument in each pair so that if some "recent 11 pair has been entered into L2 and whose second argument matches y , a triplet is formed o and its coded value is placed in list L3. Say the pair (f(4),cp (f(4))) is the match, where y = cp (f(4)). Then the value c (c (w , v ) , f (4) ) is placed O Z o o in the list L3 and a check is placed after (w ,v ,y ) in list Ll and a check o o o adjustment is made with the pair (f(4),cp (f(4))). The adjustment will be explained shortly. If in fact no match was made nothing further is done with the triplet (w ,v ,y ) at this point. The next thing done is to compute the o o o next pair in the list L2 . The second argument of this pair is compared against, the third argument of all the unmarked triplets in list Ll . For every match found, a triplet is formed from the first two arguments of the matched triplet and the first argument of the pair. The coded value of this triplet is placed in the list L3 and a check is placed after the triplet in Ll and a check is placed after the pair in list L2 if it has not already received such a check. This process goes on until all the triplets in Ll have been searched for a match with the pair. If the new pair generated in list L2 is not matched with any triplet in Ll, it receives no check. Now when a new triplet in list Ll is generated, its third argument is checked against the second argument of eacl pair in list L2 whether or not that pair has a check. If the first match encountered is with an unmarked pair, a triplet is formed and its coded value entered into L3 , and both the forming triplet and pair receive checks. If the I 33 first match is with a pair that has a check, the pair receives a second check, and the search continues for a match with an unmarked pair. If other matches are found with already marked pairs, those pairs are ignored and the search continues. If a match is then found with an unmarked pair, the triplet is formed and its coded value entered into L3 , the forming triplet and pair receive checks, and then the extra check placed next to the first match with the checked pair is removed, so that at this point there are no doubly checked pairs in list L2 . Finally, after the match with the already checked pair, if no unmarked matches are found in list L2 , a triplet is formed from the triplet in Ll and from the doubly marked pair of list L2 . The coded value of the triplet formed is added to L3, the triplet in list Ll is checked and the second check is removed from the pair in list L2 , leaving that pair with a single check, and leaving no doubly checked pairs in L2 . The above process is continually repeated, thereby generating an infinite list L3 . This process is summarized in the following instruction sequences where each list is assumed initially empty. Stage 1: 1. Do one step of computation on y . (r(0)). 2. If cp^.-.(r(0)) converges with value y after one step of computation, place the triplet (4(0) ,r (0) ,y) in list Ll. 3. Produce the pair (f(0),cp (f(0))) and place it in list L2 . 4. Compare cp (f(0)) with y. 5. If they are equal 5.1. place the value c (c ( 4(0) ,r (0) ) , f (0) ) in list L3 5.2. place a check after (4(0) ,r (0) ,y) in list Ll 5.3. place a check after (f(0)/p (f(0))) in list L2 . 34 6. Go to next stage. Stage t+1: 1. Perform t+1 steps of computation on each of the members of the sequence q)^ (0) (r(0))/^ (1) (r(l)) ) .-.,c Pje(t) (r(t)) . 2. If members of the sequence converge on or before the t+1 step of computation, for each convergent computation, where CD (v) = y, place w a triplet (w,v,y) on list Ll if that triplet does not already appear in the list. 3. For each new triplet added to list Ll, compare y with the second argument of each of the pairs in succession in list L2 . 4. If a match is found, say y = cp (f(k)), then 4.1. If the pair (f(k),9 (f(k))) has not received a check 4.1.1. place c(c(w,v) , f (k)) in list L3 4.1.2. place a check next to the triple (w,v,y) in list Ll 4.1.3. place a check next to the pair (f(k),cp (f(k))) in list L2 4.2. If the pair (f(k),cp (f(k))) has a check 4.2.1. place a second check after the pair 4.2.2. compare y with the second argument of subsequent pairs in L2 looking for a match 4.2.3. If a match is found involving a pair with a check, ignore it and continue the search 4.2.4. If a match is found with an unmarked pair say, y = cp z (f<») 4.2.4.1. place the value c (c (w, v) , f (m) ) in list L3 4.2.4.2. place a check next to the triplet (w,v,y) in list Ll 35 4.2.4.3. place a check next to the pair (f(m),cp (f(m))) in List L2 4.2.4.4. remove the second check from the pair in L2 which has two checks 4.2.5. If no further match is found 4.2.5.1. place the value c (c (w, v) , f (k) ) in list L3 4.2.5.2. place a check next to (w,v,y) in list LI 4.2.5.3. remove the second check from the pair (f(k),cp (f(k))) in list L2 5. Increment t and go to next stage. If a function p is defined as follows: I cp (v) if «-p (v) converges / N J w ^w p(w,v) = < I undefined otherwise, then the above procedure 1. lists all the triplets (w,v,y) which define p, 2. lists all the pairs (x,y) which define cp , and 3. lists a set of codings of triplets constructed from considerations of the first two lists. List L3 is an effective construction from a pair of recursive procedures which listed cp and p. Hence, by Church's Ihesis, list L3 is a recursively enumerable set. Each coded triplet in L3 corresponds to exactly one triplet in list LI since each marked triplet in LI is used exactly once to produce a value in L3 , and in addition the first two arguments of each triplet in Ll are unique. Hence the first two arguments of each coded triplet in L3 are unique. The values in the list L3 can be listed by the function g defined by: g(0) = the first member in list L3 36 g(x+l) =< .(J-yLy has been added to the list before or during stage x+1 and y£{g(0) ,g(l), • • • ,g(x) }], if such a y exists. g(0) otherwise . Since the procedure for construction L3 is effective, by Church's Thesis g is partial recursive. Furthermore, since L3 is non-empty (because D was assumed non-empty), g is total and is therefore a recursive function. Now if t s c(c(w,v),y) for some triple (w,v,y), then it is easily seen 2 that y = r(t), v = r(i(T)) and w = & (T). The partial recursive function i(f, which is sought, is then given by: K*,y) = r[g(>sU 2 (g(s)) = x & r(4(g(s))) = y])]. Since the function I, r, and g are recursive, the expression in the innermost brackets is recursive. By definition of p., M-s[ ] is partial recursive. Therefore, r[g((is[ • • 'X* • -y • • • ]) J is partial recursive, so that l|i (x,y) is partial recur- sive. The expression M-s[; • -x* • «y • • J searches for the first (and only) value in the list (the entry corresponding to the integer s) which has value g(s), 2 and such that & (g(s)) = x and r(-#(g(s))) = y, if such an s exists. If such an s is found, this means that g(s) is an encoding of (x,y,v) where ^(Xjy) = v (i.e. cp (y) = cp (v)). Therefore, for this value of s, r(g(s)) extracts the value v. 4 is therefore, the partial recursive function sought. Q.E.D. Corollary 3.2 If z is a Go'del number of any partial recursive function such that D z ^ 0, and i is a Godel number of a partial recursive func- tion i|< as defined in the theorem, then D = D z (i). The result of this theorem can be viewed as the demonstration of an interpretation function for a behavior function cp for which all possible types of machine computations which produce the same result as cp can be 37 effectively listed. This gives an appearance of universality for the inter- pretation function since, in effect, i|f maps all possible computations of the elements in R onto D . z z An observer, viewing the behavior of the mechanism (organism) Cl, discussed earlier, who assumes that the behavior function of is partial recursive, can be assured that there is a non-trivial interpretation, ty, for the inputs to fi. The observer may attempt experimentally to discover just what the function i|) is by observing several input-output situations for ti and then constructing successively closer approximations to ty . This amounts to determining a sequence of Godel numbers i, ,i ,»«'.i such that D (i, ) ^ D (i„) CI ... C 12'n z 1 z 2 D(i)CD, The following discussion shows that there is a definite structure imposed on all partial recursive functions of two variables by considering each as an interpretation function of a given partial recursive function of one variable. Theorem 3.6 Let z be the Godel number for any partial recursive function. Then for each i D (i) c D . z — z Proof: Obvious from the definition of D (i) and Theorem 3.5. z Theorem 3 . 7 00 For every z, D = U D (i). z i=0 z Proof: Follows directly from Theorem 3.4 and the definition of D (i). Theorem 3.7 gives rise to questions such as: given z, i, and j, does there exist a k such that D z (k) - D z (i) U D z (j) (3.4) 38 or D z (k) = D z (i) fl D z (j) ? (3.5) Although it is true that both D (i) U D (j) and D (i) O'D (i) are recursively z z z z enumerable sets, it is not immediately clear whether there exists a k satisfy- ing either equation. It would be advantageous to prove such values k exist which satisfy relations (3.4) and (3.5) because any such process which pro- duces k from i and j would indicate a general process of synthesizing perhaps more complex interpretation functions from less complex interpretation func- tions. The difficulty in proving Equations (3.4) and (3.5) arises from the fad J that although for a given pair (x,y), cp. (x,y) and cp.(x,y) may both be defined, i and, in addition, be members of D (i) and D (j) respectively, but not be equal to each other. In trying to construct a partial recursive function which satisfies either (3.4) or (3.5) it is not clear what value to choose for cp(x,y) in order that values will not be dropped from D (k). 3.3. Specific Interpretation Functions If, now, emphasis is shifted from the interpretation domains to the portions of the domains of the interpretation functions which provide "situa- tions", which from the observer's point of view result in an expected output from 5 a more natural structuring of the relations between the interpretation functions becomes apparent. In the process of determining an interpretation function i|i for the behavior function, 41 , of f}, the observer may hypothesize that i|> is cp. for some i. Then in considering D (i) the focus falls on only those pairs (x,y) for which cp.(x,y)eD (i), even though there are other pairs J- Z (x,y) such that cp. (x,y) is defined but not an element of D (i). This, reflects 1 z the fact that the observer is not really interested in those pairs (x,y) such that cp (y)£R . Therefore, it seems natural to consider functions which are 39 restrictions of the cp. , but whose domains are exactly the subsets of the domains of the cp. , and which each Cp. maps into D (i). This gives rise to a more natural organization of interpretation functions for cp . Theorem 3.8 If z and i are G'odel numbers for partial recursive functions of one and two variables respectively, then the function i|i defined below is partial recursive: fq^Cx.y) if cp i (x,y)£D z (i) Kz,i,x,v) =< undefined otherwise . Proof: cp. (x,y)eD (i) iff cp. (x,y) is defined and cp z (cp i (x,y)) = cp x (y) iff ]wfT(i,x,y,w) & Mt(z,U(w) , v) & 3s(T(x,y,s) & U(v) = U(s))]} iff Jw3v3s[T(i,x,y,w) & T(z,U(w),v) & T(x,y,s) & U(v) = U(s)] . The expression between the brackets is recursive, hence, the whole expression is recursively enumerable by the Projection Theorem. Therefore, by Church's Thesis f is partial recursive. Q.E.D. Corollary 3.3 There exists a recursive f such that cp f , . \(x,y) = t(z,i,x,y). Proof: Immediate from the s-m-n theorem (Theorem A-4) . Definition 3.3 For two functions f and g, _f i_s a restriction of £ denoted f Cj g if for every x if f(x) is defined, then f(x) = g(x). fL i§. OH extension of f_. Theorem 3.9 Denote rp in Corollary 3.3 by f. . Then \|f. c - cp. and Y i (z ,i) J J x l — ' l D z (f(z,i)) = D z (i). 40 Proof: Follows directly from Theorem 3.8, Corollary 3.3 and Definition 3.3. Definition 3.4 De f- ' - - - is said to £ive rise to the ine ♦? as above, then cp is said to £ive r^p ±w ^s. ciflo 1 lHter E retation function ^ Denote the domain of ♦J by «J. spe Corollary 3 A (x 5 y)eiS Z if and only if tJ(x,y)«D z (i).. Definition 3.5 The specific interpretation function j£ is broader thaa the The specinc i"«i.p x JB r C $?. This is more specific interpretation function I if ^ _ V simply stated: jfcj is broader than Jr.. The notion of comparing the broadness of two interpretations is very natural when one wants to explain certain sets of facts. Intuitively, an inte, station which accounts for more facts is usually considered broader than another that accounts for less facts. Theorem 3.10 The relation "is broader than" Is reflexive and transitive. Proof: For any ♦*, *J is broader than ** since tfi £ *?• Hence the relation is reflexive. If f. is broader than f. and f. is broader than **, then V c ? and it - * 2 . Therefore, < £ *? and ** is broader than **. There- j - i k J fore the relation is transitive. Q.E.D. Theorem 3.11 For any t? and *». the relation -*J is broader than * and ♦? i" broader than ♦*" is an equivalence relation. Proof/ Fro. Theore. 3.10, the relation is clearly reflexive. The relation is clearly sy mm etric by its definition. Using A, B and C for convenience, if 41 A is broader than B and B is broader than A, and if B is broader than C and C is broader than B, we have then A is broader than B and B is broader than C. Therefore, A is broader than C. On the other hand, we have C is broader than B and B is broader than A. Hence C is broader than A. Therefore, the relation is transitive and thus an equivalence relation. Q.E.D. Definition 3.6 Denote "^ is broader than forms a lattice. The third statement z of Corollary 3.5 indicates that corresponding to every breadth type, say [i] , there corresponds a unique set, namely that set which is equal to ^ for all i|i Z e [i] . 43 Definition 3.10 Denote the set corresponding to the breadth type [i ] by i.i, With this convention it is obvious that & = &,-.-, for all i|f e[il . a L 1 ] a L J z Corollary 3.6 1) [i] z = [j] z if and only if ^ j = ^.-j. 2) [i] z < [j] z if and only if ^. j C ^. j . Definition 3 . 11 Let S be a subset of (B . Then [i] r is an upper bound for S if for every [a] e S, [a.] z < [i] z ' t L ]z ^ s t ' ne ieast u PP er bound or supremum for S if for all other upper bounds [fi] 7 for S, [j] z is a lower bound for S if for every [a] eS, [j] z ^ [ a ] Z ' [j ] is the greatest lower bound or inf imum for S if for all other lower bounds [y] for~S^ [y] < [ j ] . Theorem 3.13 Let S be a subset of 35 . Then \i]„ is an upper bound for S if and only if for every L^J z e ^ a [a] - [i] Proof: Let [i] be an upper bound for S. Then by the definition of upper bound, [a] < t L ] f° r ever Y [ct] £ S. Therefore, by Corollary 3.6 &V -. C z z z l Ct J *?.-, for every [a] eS . Hence U ^ , C jfi? , . Let U^ i c *r-i for every U] J z a [aj - [ij a laj — L ^ J [al eS. Then jtff , c ^ f or every [al eS. Hence, by Corollary 3.6, J z [aj — |.x J L J z ' ' t a l z 5 [i] for every [a] es. Therefore, by Definition 3.11, [i] is an upper bound for S. Q.E.D. Theorem 3.14 Let S be a subset of (B . Then, [j] is a lower bound for S if and only if for every [a] €S 44 [j] - a LaJ Proof: Let [j] be a lower bound for S. Then by definition of lower bound, [j] < [a] z for every [a] B «S. Hence, by Corollary 3.6, ^ . j £ &[ a y There " forl, ^E g ^ for every [*]*. Let ^ E g ^ for every [a^S. Then ^ Z r t c «? i for ever y ^] e S • Therefore, by Corollary 3.6, [j] z < [a] z LjJ - LaJ z for every [a] «S. Hence [j] z is a lower bound for S. Q.E.D. Theorem 3. 15 Le Let S be a subset of ■ i Proof: Since & Z [±] = U &\ a] , by the definition of equality between sets, U & z i c & Z . Therefore, by Theorem 3.13, [i] z is an upper bound for S. Let [ P ] be an upper bound for S such that [^ < [l] z - Then ^ E &\ ±] * nd U £ z c & z But, by definition of set equality, A^j ^- Therefore, tf ^ & Z [p] . But thiS meanS that 1i] = *W ^ ^^ [llz = Mz ' HenC6 ' fil is the least upper bound for S. Q.E.D. L J z Theorem 3.16 Let S be a subset of B . If there exists a J such that ^.-j = fl tf , for all [a] eS, Z then [j] is the infrmum for S. a LaJ z Proof. By definition of set equality ^j £ g 4j a] . Therefore [j], is a lo W er bound for S. Suppose there Is another lo W er bound for S, [V], such that [j], < M.. ^en ^j £ *> Z [Y] £ g fl Z [a] . From the definition of set equality, ^.,C^.. Therefore «J vl £ «?,,. Hence, by Corollary 3.6, [v] z = [j],- a [a] - L J J LV J UJ Therefore [j] is the greatest lower bound for S. Q.E.D. 45 Definition 3.12 Denote the supremum of two objects a and b, by a V b and their infimum by a A b . The supremum for a set of objects, S, is denoted by V a for all a eS and the infimum of S is ' ^ a a a denoted by A a for all a eS. a a a Lemma 3 . 1 z Let cp. give rise to t. , then if the domain of cp. equals the domain of | z , cp. = ^ l l i Proof: By Theorem 3.9, i|f. 5E cp. , which means that cp. has the same value as z z i|). for every pair (x,y) in the domain of \|f. . But since the domains of cp. z z and if. are identical, for each (x,y) in the domain of cp. , cp. (x,y) = ty. (x,y) . Therefore, cp. C \|r and hence cp. = l|f. . Q.E.D. i—i T i i Theorem 3.17 For each z, i and j there exists a k such that [k] = [i] V [j] . Proof: It must be shown that for each ^ efil and j 1 e [ i 1 there exists a a z |3 1 such that & = $ U & and hence & r , -> = &r-i u ^r • t To arrive at such k k a £3 [kj [ij [jj z z z z a f , a function ty is constructed from ty and f by computing t (x,y) and K- Ot p en. ^ (x,y) for each pair (x,y). Whenever a value shows up, that value is given P z z to <|i(x,y). If \|f (x,y) and ^ (x,y) converge simultaneously with two different values, ty(x,y) is assigned the smaller value. Two lists, LI and L2 will be formed; LI will contain an encoding of the pairs (x,y), for which t is defined, and L2 will contain an encoding of all triples (x,y, ^(x,y ) ) for which >Kx,y) is defined. These initially empty lists are constructed in stages . Stage 1: 1. Perform one step of computation on each of ^ (^(0),r(0)) and LX ^(4(0), r(0)). 46 2. If exactly one of the computations converges, say with value v , place in list Ll and the value c (c( 4(0) ,r (0>) ,v ) in list L3 . 3. If both computations converge with values v and w , place in list Ll and the value c(c(4(0) ,r (0)) ,min(v ,w )) in list L3„ 4. Go to next stage. Stage t+1: 1. Perform t+1 steps of computation on each of the pairs [f (4(0), r(.0», l£(4(0), r(0))},{^(^(l),r(l)) 5 C(,i(0). J r(.0)) },•••, CX p Ct p {t*(4(t),r(t)),^(4(t),r(t))3. 2. Whenever a convergence occurs in any computation on or before the (t+l)st computation step, say it occurs in pair n, 2.1. If n is already in list Ll, continue the computation steps. (A value for (x,y) = (4(n),r(n)) has already been placed in list L2.) 2.2. If n does not occur in list Ll, add it to Ll. 2.2.1. If exactly one of the pair {+ Z (Jfc(n) ,r (n) , 1 w n )) in list L2. 3. Go to next stage. Next define function g as follows: g(0) = the first member of list L2 . 47 (J.yLy has been added to the list L2 before or during stage g(x-fl) = J X+1 ' and y^^^^'S^ 1 )' ' " >§( x ) ^] if such a y exists. g(0) otherwise By Church's Thesis, g is partial recursive. If both &r . -r and &r . -i are empty, list L2 would be empty (as would list Ll). But by definition, L2 would be recur- sively enumerable and g would be undefined. However, if not both of ^r. -i and &r . -I are empty, then the lists are both non-empty and g is defined for every value of its argument. Therefore g is recursive. Hence, the function l|i defined by + (x,y) = r[gOs[£ 2 (g(s)) = x h r(£(g(s))) = y])] is partial recursive. Therefore, there exists a k such that cp - i)j. 7 Z Next it should be noted that the domain of ty equals & U & which a j3 equals & t . -, U & r .-.. That Ll is an encoding of the domain of ty is easily seen UJ LJJ when one considers that a number n was added to Ll (and a corresponding number z z to L2) whenever either i|» (£(n),r(n)) or i(i _ ( i(n) ,r (n) ) first converged (if in fact either did converge), and if n was not already in the list Ll. But the number placed in L2 was c(c(£(n),r(n)),v) = c(n,v) . Thus *(*(n),r(n)) = v. Now by construction of list L2 , there is a value associated with each (x,y) in z z the domain of ^ and a value associated with each (x,y) in the domain of <|» • z z That is for each (x,y)e$ U & there corresponds a single value in L2 so that Q. p U JQ c dom(i)i). But ty is defined only for those (x,y) for which either ty or ♦ o is defined so that domO) c - & Z U JB Z Therefore dom(t) = & Z U ^ = p - a p a p *? . i U tf [i] [J]* 2 Z Now let cp = \|i give rise to t . Then & = dom(^). This follows from the method used to construct cp = i|f from t and *|» , and from the method of K Q p 48 constructing i|f from cp . Hence, by the Lemma 3.1, 1 = cp and hence &^ = & Z \J & Z = & Z r, U tfr.y Then [k] is the degree of breadth for i|£. From this fact we have &r-i = & for all t v ®[k] and in particular 7 7 7 *Z ^Tkl = ^k = ^T' 1 ^ f'T Hence b Y Theorem 3.17, [k] is the supremum for [i] z and [j] z . Therefore, [k] = [i] V [j] . Q.E.D. Theorem 3.18 For each z, i and j there exists a k such that [k] = [i] A [j]i .. Argument without proof: Two lists can be constructed in an analogous manner to the construction of the two lists in the proof of Theorem 3.17. Entries were not made into these two lists unless at some stage of construction both z z t (-^(n).r(n)) and i|f (.£(n) ,r (n)) converge for some n with values v and w a (3 n n respectively. Then n is added to LI and c(n,min(v ,w )) is added to L2. The rest of the proof is exactly the same as that of Theorem 3.17 except for replacing U by H, V by A and ^ by p where appropriate. By theorems 3.12, 3.17 and 3.18 (B is a partially ordered set such that each pair a,|3QB has both a supremum and an infimum. Therefore (S> is a lat- 13' tice.— ' In fact, for every z CB is a distributive lattice with a unique maximum element and a unique minimum element, as the following shows. Definition 3.13 A partially ordered set S has a maximum element e if e . , , r r, \ 7, ^~~i ~ • max n max is an upper bound for S and e max es. S_ has a minimum element e . if e . is a lower bound for S and e . es . min min min The uniqueness of a maximum and a minimum element in a lattice is shown 13/ by the next two theorems.— 49 Theorem 3.19 If the lattice £ has a maximum element, then it is unique. Proof: Let a and b be maximum elements in £. Then a < a V b and b ^ a V b. But since a and b are maximum elements, a = a V b and b = a V b. Therefore, a = b. Q.E.D. Theorem 3.20 If the lattice <£ has a minimum element, then it is unique. Proof: Let c and d be minimum elements in <£. Then a A b < a and a A b < b. But since a and b are maximum elements, a A b - a and a A b = b so that a = b. Q.E.D. Theorem 3.21 For each z, (B has a minimum element, z Proof: From Theorem 3.2 there exists a number i such that D (i) = 0. Let Z r\Z cp. give rise to if. . Then &. = 0. This is because for no pair (x,y) is 9- (x,y)eD , (even though cp. (x,y) may be defined for these values), and z z hence i|f. is nowhere defined . Let the breadth type containing i|f. be denoted 2 by [0] . Then & Z = rff_, = 0. Then for any [k] eft , & fn , C jB? Therefore, L J z l [0J ^ L J z z' [0J — [kj by Corollary 3.5 [0] [k ] . Therefore, CB has a unique minimum element, namely [o] . Q.E.D. Theorem 3.22 For each z, B has a maximum element, z Proof: Case 1. D = 0. Then for every i, D (i) = since cp (cp. (x,y)) will always be undefined. Therefore, for each i, cp. gives rise to a if. such that 50 & z = 0. That is, . Then by Theorem 3.5 there exists an i such that z (x,y) e D. if and only if ^(y)** and, in addition, for every (x^eD., . cp^y)) = 9 X CY). Now let cp. give rise to f. Then t - D. since cp., aid hence f. are defined precisely for those pairs (x,y) such that ^(y)*,. Let [l]z be" the breadth type for z containing f.. But then for any [j]^, «f .1 E %]• This is becaUSe £ ° r eaCh (X ' y)e ^j]' 9 x Cy)eR z- BUt ^ 1 reverse implication does not necessarily hold. Therefore [^ < [l], and fll is the unique maximum element for (B z - Q.E.D. L J z Theorem 3.23 For each x, 1, j and k the following hold. 1. ([l] z V[j] z )A W z = (HI, A W z ) V (bl z A W z ) 2. ([I], A []];' W z =C[i] z V [k] z )A(bl z V W z ) • Pro o £: That % has breadth types for each of the entities on hoth sides of both equations follows from Theorems 3.17 and 3.18. Proof of 1: Let [m^ = «tl,V [il z ) A [k], and Kl z = (W Z A W.) V(U1 Z A W,). Then ^r^H^L^^W ■*ii] nl i.i )U( ' i ii] n ^^»ir Thaf t . iS ,■ - «J ,. Therefore, by Corollary 3.6 [m^ = [^1. That 1S [mj [n x ] and the first equation holds. Proof of 2: Let [m^ = C[i] z A [j] z > V [kl, and [n 2 ] z = ([i] z V [k] z ) A ([j] z V [k] z ) . 51 Again by Corollary 3.6 [m~ ] = [n ] and the second equation holds. Q.E.D. If for each z every element in S had a complement, that is, if for each [i] e(B there exists a [ j ] e(B such that [i]^ V [ j ] = [i ] and [i] A [ j ] = [Ol , then since Theorem 3.23 shows that U is a distributive lattice, each 3 J z z ' z would then be a Boolean algebra. However, given any two recursively enumerable sets A and B such that A ^ B, the set B-A is not in general recursively enumerable. Therefore, although the domain corresponding to a breadth type, y [i ] , in (B is recursively enumerable, and although the set &r -i-fii . -i sa has the properties < S [l]- fl [i] )U *[!] = *[!] and (& z [i]-1ij> n Vr*[or* i\Z it is not known whether $r n - $r.i is recursively enumerable. If it is not UJ UJ recursively enumerable, then there can be no breadth type corresponding to it in £ . On the other hand, if for some z and i it can be shown that z ' jS r T -I - &[-.] is not recursively enumerable then we know that, in general, for any z (B is not a complemented lattice and hence not a Boolean algebra. z z z Whether such a non-recursively enumerable set $r-r i " ^r • n ca " be demonstrated UJ UJ is an open question. 3.5 . Significance of the Structure of CB a z The fact that for any z, N, if x is the initial number, (Ps) (n) (x) = (Ps) (n_1) (x)+l . In the first case if n = 3, then the relation holds for x e [5, 6, 7 , 8, 9, 10 }. Or if n = 4, the relation holds for x e{l,2,3,4J. This is reflected in 3 4 the table for entries under (Ps) (x) and (Ps) (x) respectively. If the first number chosen is 0, then for the second case N = 2. For any number except 0,1, •••,10, the second relation holds with N = 1. Condition 1 above shows further that there exist functions, defined from 3 the composition Ps , which have fixed points. Namely, (Ps) has 6 fixed points 4 (and one description loop consisting of members 4,3,2,1) and (Ps) has four fixed points (and two three element loops). In general, from any partial recursive function with non-empty domain a paetial recursive function can be constructed which has a fixed point. Definition 4.1 The class of functions IP = {f:f is a one-to-one, onto, recursive function] is the class of recursive permutation functions . 56 Table 4.1 Values for P(s(x)), (Ps) 2 (x), (Ps) 3 (x), 4 and (Ps) (x) of Example 4.1. X s(x) P( s(x)) (P s) 2 (x) (Ps) 3 (x) (Ps) 4 (x) 1 11 12 13 14 1 2 2 3 4 1 2 3 3 4 1 2 3 4 4 1 2 ■ 3 4 5 1 2 3 4 5 6 6 7 5 1 6 6 7 7 5 6 7 7 8 5 6 7 5 8 9 9 10 8 9 9 10 10 8 9 10 10 11 8 9 10 8 1 11 12 12 13 14 15 12 13 13 14 15 16 ; -* 11 -* 12 -* 13 Figure 4.1. Description chain and loops for P(s(x)). 57 Theorem 4.1 — The class P is a transformation group on N. Proof: Let f and g be elements of P. Then since, f and g are one-to-one and onto, fg is one-to-one and onto. Since f and g are recursive, fg is recursive by Church's Thesis. Therefore fgeP. Let f be an element of P. Then since f is one-to-one, f is a single- valued, partial function. Since f is onto, f is a total function. Since f is recursive, a procedure for calculating f (x) for all x can be given. Namely f is the function i|f defined by l|f(x) = Uy[f(y) = x] . Since f is recursive and onto, calculation of f (0) , f (1) , * * * , and after each computation comparing the result with x until finally for some n, f(n) = x, will yield a value for each n. Hence f " is recursive and therefore a member of P. Since P is closed under composition and inverses, it is a group. Q.E.D. Since each feP is recursive, by the Normal Form Theorem (Theorem A-18) and Definition A-10, there exists a Godel number z such that f = cp . Hence o T z o the composition of any f with any partial recursive function produces a par- tial recursive function whose Godel number is directly determined from the two Godel numbers for f and the partial recursive function it composes with. A more general form of this notion is expressed by the next theorem. Theorem 4.2— / Let x and y be the Godel numbers for the partial recursive func- tions cp and cp y . Then there exists a recursive function h such that T h(x,y) T x ' y 58 Proof: Let u be the Godel number of the universal partial function of Theorem 2.4. Define a function 6; 9(x,y,z) = cp (cp 00) - CD (x,cp (y,z)) . The last expression is effectively computable. So by Church's Thesis, 9 is partial recursive and there exists a w such that 9 = cp w . By the s-m-n ° 2 ° Theorem there exists a recursive function S.. such that 9 2 < z) = e ( x >y> z )- S 1 (w o ,x,y) Since w is fixed for all x and y, let o 2 h(x,y) = S 1 (w o ,x,y) Hence, since h is recursive, h(x,y) ^x y Q.E.D. Theorem 4.3 Let z be the Godel number of a partial recursive function cp such that D z ^ 0. Then for each xSD , there is an feP such that f(cp (x)) = x. Proof: If xSD is a fixed point for CD , then the identity function is such z z an f. For every other x, cp (x) = y for some y. Hence define the function f as follows: f(w) = 1 *~ x if w = y y if w = x w otherwise Then it is readily seen that feP. Now since cp (x) = y and f(y) = x, f (Cp (x)) = x. Q.E.D. Corollary 4.1 Let z be the Godel number of any partial recursive function such that D z ^0. Then for each xeD z , there exists a w such that cp w (x)=x, Proof: Follows directly from Church's Thesis, Theorems 4.3 and 4.2. 59 Corollary 4.2 Let z be the Godel number for a partial recursive function Cp such that D z £ 0. Then for each y such that Cp z (x) = y, there exists a w such that cp (y) = y. Proof: Define the same f as in the theorem. Then since f(y) = x and cp (x) = y, cp (f(y)) = y. Such a w is assured by Church's Thesis and Theorem 4.2. Q.E.D. Functions other than recursive permutations can produce fixed points when composed with partial recursive functions. These pairs of functions, when viewed from different perspectives, display three types of stable behavior. In each case, two functions, f and g, and two points, x and y , are related by the equations : (4.1) f(x ) = y o ■'o g(y ) = x o . Furthermore, the function fg and gf have fixed points, namely : f(g(y Q )) = y (4.2) and g(f(x Q )) = x Q . (4.3) In analyzing stable behavior of some mechanism or organism, an observer will attempt to distinguish from what he considers its behavior function, b, which shows stable behavior at say x, sub-modes of behavior, say g and f such that gf = b. If he succeeds in finding such g and f then he will have called into existence another quantity which is the output for f and the input for g. The situation is shown in Figure 4.1. This process, of course, is the initial stage for constructing a theory about the behavior function b. Con- firmation of this theory would depend on the isolation and measurement of the 60 quantity y. If x is a fixed point with respect to b, then Equations (4.1) predict the expected value y for y. By severing the connection at y, Equa- tions (4.2) and (4.3) would no longer be observable, although the relations of Equations (4.1) could still be tested in some cases. x -*l i r i i i i i I I * i „ i i b -J I 1 x Figure 4.1. The decomposition of a behavior function with a fixed point. 4.2. Fixed Points for Specific Functions Although Theorem 2.3 shows that for a given partial recursive function cp , the domain of looping descriptions for z, D , is recursively enumerable, z z it is not decidable whether a given x is an element of D . However, if x£D then there exists an N and an m such that z CD (x) = cp (x) = x . Y Z Y Z o (4.4) In addition, there are m-1 more values for x, namely x, •••,x ,, such that ' J 1 m-1 cp (x. .. ) = x. for 1 < i < m ^z l-l l — and CD (x ) = x r z N m o 61 Thus for every xe{x .x, , • • •, x } o 1 m-l m p z (x) = x. What this means that in the case of partial recursive functions a fixed point for cp can be found in a finite number of computations from a value x, L T U if x£D . However, if xeD or D , no finite amount of computing would dis- z z z cover a fixed point. On the other hand, there are some functions for which it is possible to determine at least some of its fixed points. For instance, the such fixed points are enumerated for the universal partial function in o the proof of Theorem 2.9. 4.3. Diagonal Arguments and Fixed Points It is to be noticed that the proof of Theorem 2.9 depends on Kleene's Second Recursion Theorem (Theorem A-7). The significance of this statement is that in order to demonstrate fixed points for the universal partial function an appeal was made to an approach which yields functions which apparently use their own Godel numbers in their respective computations. For instance, if 2 2 g(x,y) = x +y then there is a Godel number e such that 2 2 P e (y) = e +y . The number e can be effectively calculated. It is e = sJ(z o ,z o ) 1 9 9 where z is the Godel number for a function which computes [S.(x,x)J + y . The quadruple for M can be effectively generated and from any y placed on 2 2 its tape M will compute the value e + y 1 e r J o In addition, Theorem A-6, the First Recursion Theorem, also locates a fixed point for any recursive function f. If n is that fixed point, it is not the case that f(n) = n, but it is the case that m = rn . This means that r f(n) 'n 62 for each x, cp (x) is undefined if and only if cp . . . (x) is undefined. For n f (n) each x such that both are defined, ^n (x) = C Pf(n) (x) ' The self-referencing nature of the functions produced by these two theorems make them likely candidates for developing theories of self-referenc- ing phenomena. Lofgren ' — uses these theorems to prove theorems about self-reproducing Turing machines, learning systems and evolutionary systems. The common basis for the establishment of these theorems is applicable to all such proofs of self-referencing nature. The proof for Theorem A-6 relies on a function which computes the value of cp (x) for all x, and the proof for Theorem A-7 relies on a function which computes values for S..(x,x). In a square matrix with values cp (y) for all x and y, the values cp (x) occur on the main diagonal. The same is true for the values of S- (x,x) in a matrix whose values are S,(x,y). In both cases the proofs are established through the method of diagonalization. This method of diagonalization is a generalization of the Cantor Diagonal Argument for proving that the cardinality of the reals is larger than that of the natural numbers. The interesting thing about the method of diagonaliza- tion is that in some cases it produces a contradiction, as with the Cantor rgument, and in other cases it produces fixed points as with the recursion theorems . • As is well known, diagonalization involves a class of sequences of 16/ elements from some set S, and a mapping Oi from S into S. — The sequences are * arranged as rows in a square matrix. The operation Oi induces a mapping ot on the class of arbitrary sequences of elements of S. If [s(i):ieNj is such a sequence, then a ({s (i) :ieNJ) = {^(S (i) :ieN}. Usually a maps rows of the 63 matrix onto other rows of the matrix. If at is applied to the sequence of elements on the diagonal of the matrix one of two things happens: 1. The resulting sequence i_s_ not a row of the matrix. 2. The resulting sequence _is_ a row of the matrix. In the first case, a sequence is produced which was not in the original class of sequences. This leads to a contradiction of any statement about the com- pleteness of the original class of sequences. On the other hand it may suggest suitable enlargements for that class of sequences. In the second case, a sequence is produced in which at least one element of the diagonal remained unchanged under the application of at y namely, that element located in the intersection between the diagonal with the row upon ■;'<■ which the diagonal is mapped by at . This element is a fixed point for at. 1 f> / Owings proved a theorem demonstrating the construction of such fixed points. — In order to provide a solution space for a very broad class of problems involving fixed points he defines a structure which includes a set of objects S, four binary operations on S, an equivalence relation on S and a special object 6eS. Two of the operations * and □ define multiplication tables on S. 6 is an object such that for all f^S, - r Qf is defined (other entries in the a table may be possibly undefined). The other two binary operations, • and ° , relate rows of the □ table to rows of the * table via the equivalence rela- tion. In his theorem, if two conditions are satisfied, then the existence of a fixed point, with respect to the equivalence relation is determined for each element of S. The use of an equivalence relation gives as broad a defini- tion to fixed point as possible. For instance, as was pointed out earlier, that for the fixed point n in the proof of the First Recursion Theorem, it is 64 not necessarily the case that n = f(n), but it is the case that CD = cp , . . — T n f(n) If S = N in this case, then the equivalence relation: m - n if and only if rf> = (h is applicable. Owings theorem now can be stated. r m ^n Theorem 4.4 (Owings Fixed Point Theorem) Let (s,°,*, * ,Q,=, S) be a structure as outlined above. Then for each f,g,heS, if: 1 . 6gf = f *f 2. (f°g)*h - f * (gQh) whenever grjh is defined, given any feS, there exists a tes, such that t=f*t, namely, t = 6Q(f 6 6). Proof: t = 6n( f ° 6 ) = (f°6)*(fo6) = f-[ti(f°6)] = f-t . Q.E.D. Condition 1 of the theorem shows that the 6 th row of the q table is equivalent to the diagonal of the * table. Condition 2 shows that the result of applying f to the g row of the □ table is, modulo equivalence the (f g) th row of the * table. The result of applying • to f and the 6 row of the q table is modulo - the (f°S) row of the * table. Since con- dition 1 holds, the (f°&) row must intersect its diagonal in a term equiva- ■f"H lent to its corresponding term in the 6 row of the □ table. Since • must not map f and 6Q(f°&) outside its equivalence class, f-t - t where t = 6 Q (fo6) . 16/ Example 4-2 — (Proof of Kleene's Second Recursion Theorem) Let S be N. Define s(m,n) and t(m,n) such that for all m,neS,

v) = CD m (s(n 5 p),v) =

x (v) = cp s(a)T) (v) - ^ a (T,v). 4.4. Fixed Points for Operators The discussion in this chapter has been mainly about fixed points for functions. The idea of a fixed point, however, generalizes to operations on functions and relations, and conceptually to higher order operations on operations. It is well known that fixed point functions exist for various classes of operators. For instance, in the theory of differential equations there exists at least one function satisfying the relation Dx = ax at namely the function e There is a very interesting class of operators called enumeration operators. These operators have the nice property that each one has a fixed point that is a recursively enumerable set, and they map recursively enumer- able sets into recursively enumerable sets. These enumeration operators will be discussed next, and this section will be concluded with some speculation on the existence of operators which enter their own computing domains. 4.4.1. Enumeration Operators The definition of enumeration operator depends on the definition of a finite set with a canonical index. 66 Definition 4.2 Let A be the nonempty finite set {x. ,x , • • • ,x } where 1 Z Xn Xo X k x < x < ••• < x . Then the integer 2 +2 + • • • +2 is called the canonical index of A. If A is empty, the canonical index assigned to A is 0. Denote E as the finite set whose canonical index is x. Definition 4.3 — A set A is enumeration reducible to B (denoted by A < B) if ■ ■ — ■-- - „._ . . e 3z Vx[xeA « M(x,u>ew & E <= B]] . z u — A is enumeration enumerable to B via z if Vx[xeA « 3u[ew & E £ b]] . The number z yields intuitively the following procedure. Simultaneously begin enumerating W and start requesting inputs from B. (B is an arbitrary subset of N that cannot always be listed, but if appeal is made to an oracle about whether a given number is in B, the oracle will always respond correctly.) Whenever it is found that (x,u)eW for which D is a subset of the inputs z u already obtained, then x is added to a list for A. No matter what the order is for receiving inputs, the same set A will always result. Hence, for any z and B, a unique set A will be generated. Hence z determines a total mapping from 2 into 2 . Definition 4.4 — $ (x) = y if y < x via z. $ is called an enumeration z — *e z operator . Theorem 4.5 If $ and y are enumeration opreators, then, the composition $Y is an enumeration operator. 67 Proof: Since Y is an enumeration operator, Y(A) is defined for every Ae2 . Since $ is also an enumeration operator, $(A) is also defined for every Ae2 ; in particular $(Y(A)) is defined. Since $ and Y depend on some z 1 and z„ respectively, by Church's Thesis, a z can be found such that $ = §Y . Q.E.D. Z 3 Theorem 4.6 — Let Y be an enumeration operator. Then 1. A C b =» Y(A) C Y(B) ("Y is monotone") 2. xeY(A) =» 3e[E is finite & E c A & xeY(E)] ("Y is continuous"). Proof: 1. A c b. Let Y = $ for some z. Then xeY(A) =» ]u[eW & E ~A], — z z u — In the bracketed expression since A c B, E ^ A implies E c B. — u — u — Hence 3uC(x,u>eW &E " A] =» ]u[£W & E c b] =» xeY (B) . z u — ' z u — Therefore Y(A) C Y(B). 2. xeY(A) ^3u[ew &E c A ] z u — =* ]u[ew & E " E ] => xeY(E ) . z u — u u The finite set E satisfies the condition that u xeY(A) =» ME is finite & E C a & xeY(E)] . Q.E.D. The following shows that for each z, $ has a minimal fixed point which is a recursively enumerable set. 11/ Theorem 4.7 — Let $ be an enumeration operator. Then there exists a set A such that: L. *(A) = A 68 2. VB[*(B) = B =» A C b] 3. A is recursively enumerable, Proof: 1. Define a sequence of sets A ,A n , • • • as follows: o' 1' A = o A ,. = §(A ) n+1 v n Then define A = U A. . 1-0 x Now xeA =* }n[n > & x«A ] (by definition of A) n J =» 3n[ n > & xe§(A .)] (by definition of A ) n-1 J n =* xe$(A) (by monotonicity--Theorem 4.6) . Now xe$(A) => ]E[E is finite & E <= A & x6$(E),] (Theorem A-6) =* 3E]n[E is finite & E ^a & xe$(E)] (definition of A) =* 3n[xeA ,:] (Theorem A-6) n+1 =* xeA (by definition of A). 2. Assume for some B, *(B) = B. Then A = c B. o — If A c B then by monotonicity A , . = $ (A ) <= $ (B) = B . n — n+1 n — Hence A -, c B and therefore by induction n+1 ~ Vn[A <= b]. n ~ Hence U A. = A c B. 1-0 r 3. Let § = § for some z. Then for any y z $(W ) = {x:3u[ew & E <= W ] } (by definition) . y z u — y Since E is a recursive set and W is a recursively enumerable set, the u y relation E ^ W is recursively enumerable. (Since E = [x , ••• J x,-'j for X l Y X k u = 2 + • • • + 2 , an enumeration of W would determine E c W if indeed it ' v u — v 69 is the case.) Likewise the relation (x.u)ew is recursively enumerable. z J Hence the relation in brackets is recursively enumerable. Therefore, by the Second Projection Theorem (Theorem A-16) $ (W ) is a recursively enumerable set. Hence there is a recursive function f (by tacit use of the s-m-n Theorem) such that for all y w', . - § (W ) . f(y) z v y Then a function g can be defined: e(0) ■■ a where q is a recursively enumerable index for the empty set g(n+l) - f(g(n)). Then for all i, A. = W .. • and therefore i gU) xeA « ]y[x£W . . ] and g(y) A = [x:3y[x€W . .]} . g(y) Since the expression in brackets is recursively enumerable, by Theorem A-16, A is a recursively enumerable set. This completes the proof of the theorem. The following two corollaries strengthen the form of the theorem. Corollary 4.3 There exists a recursive V such that for all z and y, W,,, . = $ (W ). f'(z,y) z y Proof: In the proof of the theorem, part 3, since $ (W ) is a recursively enumerable set which depends on the choice of z and y, by the s-m-n Theorem (Theorem A-4) , there exists such a function f such that W,.., . = $ (W ) . ' V (z,y) z v y Q.E.D. 70 Corollary 4.4 There exists a recursive function h such that for all z: 1 . $ (W, , . ) = W, . . z h(z) h(z) 2. VB[$ z (B) = B =» W C bJ . Proof: 1. Consider the equality A = {x:3y[xeW , . ] } in the proof of part g(y) 3 -of the theorem. Then a recursively enumerable index for A depends on an index for g, which depends on an index for f, which in turn depends on z. Hence, by Church's Thesis there exists a function h such that $ (W, , v ) = W. , v . z h(z) h(z) 2. Follows immediately from the third condition in the theorem. Theorem 4.7 shows that for each z there exists a minimal recursively enumerable fixed point set for $ and Corollary 4.4 provides an effective listing of this minimal fixed point for each z. Theorem 4.7 also indicates that there may be other fixed points for a given § . The next theorem shows that beginning with any recursively enumerable set with arbitrary index x, a fixed point B can be found for each $ . r zx z Theorem 4.8 Let z be an arbitrary index for an enumeration operator. Then beginning with any recursively enumerable set W y a set B can be found such that Zy 1. $ (B ) = B z zy zy 2. B is recursive . zy Proof: 1. Define a sequence of sets for a given z by: C = W z,o y C ,. = § (C ) . z , n+1 z s z , n 71 00 Then let B = U C . . ^ 1-0 z ' x The rest of the proof to 1 is analogous to the proof of part 1 in Theorem 4.7. 2. As in Theorem 4.7 define a function g from the function f such that W_, . = $ (W ): f(x) Z X g(y,0) = y g(y,n+l) = f(g(y,n)). Then x£B ** ]w[xew . .J zy g(y,w) Hence B is recursively enumerable, zy Corollary 4.5 There exists a recursive h such that for all z and y, $ (W, , J - W, , . = B z K h(z,y) h(z,y) zy Proof: Analogous to the proof of Corollary 4.4. Corollary 4.6 For any z if q is Godel number for an empty set, then for all y W, . , ( - W, . . . h(z,q) - h(z,y) Proof: Immediate from the third statement in Theorem 4.7. Theorem 4.8 allows the enumeration of a large number of fixed points for each $ . Whether it enumerates all recursively enumerable fixed points is an z J r open question. 4.4.2. Self-Operators Considerations of biological phenomena sometimes gives rise to the notion of self-operator. For instance, Varela, e_t a_l. in their studies of living systems give the following definition for the autopoietic organization — : 72 "The autopoietic organization is defined as a unity by a network of productions of components which (i) participate recursively in the same network of productions of components which produced these components, and (ii) realize the network of productions as a unity in the space in which the components exist." An interpretation of the behavior of the autopoietic organization is that it operates on itself to produce itself. In symbols: 0(0) = O. Lofgren, in considering complete self-reproduction, — shows in par- ticular that the existence of atomically self-reproducing entities does not cause an inconsistency in axiomatic set theory. He characterizes such entities by: "An automically self-reproducing entity TT must constitute a unit length complete explicability chain, such that: TT(TT) = ." Lofgren 1 s paper argues that, although such objects are apparently members of both their own domains and their own ranges, their existence need not cause, any logical inconsistencies. The problem in dealing with such self-operators is that none have been formally demonstrated, although Lofgren concludes that such objects can be axiomatized in set theory. An approach to the construction of such operators would be to find an effective procedure which maps operators of a given type onto operators of the next higher type. For instance, if P denotes the procedure, and zero-level operators, , are identified with the natural numbers, first level operations, , associated with relations, etc., then P maps the class of zero-level operators into the class of first level operators, the first to the second, and so on. Symbolically this process is represented by: 73 PClo (0) 3) = {o (l) } r ((o (1) ])=(o (2) }.p ! ((o(°'))' P([o (n - l) }) = {o (n) ) = P n ({0 <0) }) . The question then arises: as n becomes arbitrarily Large, does the sequence of operator classes converge to a fixed point for P? That is, is there a class of operators {o} such that {0} = lim P n ({0 (Q) }) = P(lim P n_1 (fo (0) })) = P({0}) ? n->°° n->°° If there is such a P with such a fixed point, then for every 0.e{oj, 0. maps {o} into itself. That is 0.({o}) £ {o}. Further questions about P exist, namely, of what type level is P? And does there exist such a P such that pe{o}? 74 5. CONCLUSION A formal framework has been established in which it is possible to deal with the notion of description. An attempt has been made throughout to relate various processes, such as stable behavior, to effective procedures within the framework of the theory of partial recursive functions. An exception to this is the role of the observer discussed in chapter 3. However, his role can be given a more formal stature by limiting the searches he performs to finite search times. Beginning with the definition of description with respect to a partial recursive function, an analysis is made of the sequences of descriptions which arise through successive applications of the function to each of the natural numbers . Description chains were identified and a partition of the domain was effected according as a chain was terminating, looping or non-ending. In particular, universal partial function domains had elements in all three classes . The notion of ^-description was then introduced, and this gave rise to interpretation domains defined for various interpretation functions i|». An equivalence relation was imposed on the class of interpretation functions for a given partial recursive function, and the structure of the induced equiva- lence classes, called breadth types, was shown to be a distributive lattice with a maximum and a minimum element. It is not known whether these lattices produced are complemented, but it is suspected that in general they are not.. If they are, then they are Boolean algebras. If it can be shown that they are not in general complemented, then it would be interesting to attempt to develop intuitionistic logics from them. 75 The existence of description Loops gives rise to the consideration of fixed points. Methods for finding fixed points for partial functions and enumeration operators were discussed. In particular the method of diagonali- zation was discussed and Owings ' fixed point theorem was presented. Finally, it was speculated whether or not self-operators could be constructed using recursive methods. For the study of stable behavior mechanisms, a well-developed theory of recursively enumerable fixed points would be extremely useful. For instance, 19/ consider the following relation which may hold between two functions f and g — : f(x L ) = x l f(x 2 ) = x 2 f(x-) = x 3 g(x 1 ,x 2 ) = x 3 . Then f(g(x L ,x 2 )) = f(x 3 ) = x 3 = gCx^x^ = g(f (x^ , f (x 2 > ) . That is, f(g(x ,x )) = g(f (x ) , f (x. ) ) . This suggests the possibility of considering fixed points for some function as being linear superpositions and decomposi- tions of other fixed points in that function. Stated problematically: given the set of fixed points for f, F f , do there exist two functions g and h such that for all x,y£F f f(g(x,y)) = g(f(x),f(y)) ? 20/ Inselberg's thesis — might shed some light on the solution of this problem. Any such theory of fixed points would allow the study of stable behavior as compositions and decompositions of other stable behaviors for a large class of mechanisms. As a final comment it should be pointed out that attempts to deal with self-referencing problems usually produce one of two results, as was pointed 76 out in the discussion of diagonalization, namely 1. a contradiction results or 2. a fixed point results. Investigators are comfortable with fixed points because these signify some typt of stable situation. However, contradictions usually make investigations uncomfortable. Such contradictions often point out an inconsistency in a mode of thinking. At other times, these contradictions display paradoxes or antinomies. Paradoxes can shake the foundation of a formal system, as witness the Russell paradox. However, there are instances when a paradox leads to an expansion of a system of thought, as for instance, the simple 2 equation x +1 = giving rise to the field of complex variables. 21/ A modern day example of this phenomenon occurred when Spencer Brown — arrived at a contradiction in his calculus of indications in which he introduced the notion of reentering a form. No problems arise until he attempts an infinite number of reentries into the form. Then his calculus seems to 22/ collapse. He salvages it by introducing the notion of time. Varela- — beginning with the Spencer Brown contradiction, introduces a third value into the system and expands the original calculus into a consistent three valued calculus. The point to be made is that, although stable behavior may give rise to confirmation, which gives rise to comfortable feelings, paradox should be looked on as a hope for a development of new ideas. Paradox should be accepted as a challenge and not simply be something to avoid. 77 LIST OF REFERENCES 1. The American Heritage Dictionary of the English Language , WT. Morris (ed.), American Heritage and Houghton Mifflin, Boston (1969). 2. Maturana, H. R. , "Neurophysiology of Cognition", in Cognition : A Multiple View , P. Garvin (ed . ) , 3-23, Spartan Books, New York (1970). 3. Von Foerster, H. , "Thoughts and Notes on Cognition", in Cognition : A Multiple View , P. Garvin (ed.), 25-48, Spartan Books, New York (1970). 4. Von Foerster, H. , "Notes pour une epistemologie des objects vivants", in L'unite de L'homme, E. Morin and M. Tiattelli-Palmarini (eds.), Editions du Seuil . Paris, 401-417 (1974). 5. Weston, P. B. , and H. Von Foerster, "Artificial Intelligence and Machines that Understand", Annual Rev. of Phys. Chem. 24 (1974). 6. Kanal, L. , "Patterns in Pattern Recognition: 1968-1974", in IEEE Trans . onlnf. Theory IT-20 (6), 697-722 (1974). 7. Narasimhan, R. , "Picture Languages", in Picture Language Machines , S. Kaneff (ed.) 1-30, Academic Press, New York (1970). 8. Michalski, R. S., "A Variable-Valued Logic System as Applied to Picture Description and Recognition", in Graphic Languages , F. Nake and A. Rosenfeld (eds.) 20-47, North-Holland, Amsterdam (1972). 9. Michalski, R. S., "AQVAL/l--Computer Implementation of a Variable- Valued Logic System VL-^ and Examples of its Application to Pattern Recognition", in Proc. 1st Int . Joint Conf . Pattern Recognition , IEEE Publ. No. 73, CHO 821-90, 3-17 (1973). 10. Lofgren, L. , "Relative Explanations of Systems", in Trends in General Systems Theory , G. J. Klir (ed . ) , 340-407, Wiley-Interscience , New York (1972). 11 . Rogers , H. , Jr . , Theory of Recursive Functions and Effective Computa - bility , McGraw-Hill, New York (1967). 12. Davis, M. , Computabili tv and Unsolvabili ty . McGraw-Hill, New York (1958). 13. Bell, J. L. and A. B. Slomson, Models and Ultraproducts : An Introduction , North-Holland, Amsterdam (1971). 14. Ashby, W. R. , Design for a Brain, Science Paperbacks , London (1952). 15. Lofgren, L. , "On Formalizability of Learning and Evolution", Proc . of the I Vth Int . Congr . on Logic , Methodology , and Philosophy of Science , P. Suppes et al. (ed . ) , North-Holland, Amsterdam (1973). 78 16. Owings, J. C, Jr., "Diagonalization and the Recursion Theorem", Notre Dame Journ . of Form . Logic 14 (1), 95-99 (1973). 17. Varela, F. G., H. R. Maturana, and R. Uribe, "Autopoiesis : The Organization of Living Systems, It's Characterization and a Model 11 , Biosystem 5 (4), 187-196 (1974). 18. Lofgren, L. ,. "An Axiomatic Explanation of Complete Self-Reproduction", Bull , of Math . Biophys . 30., 415-425 (1968). 19. Von Foerster, H. , Private Communication. 20. Inselberg, A. , On Classification and Superposition Principles for Nonlinear Operators, AF Grant 7-64, T. R. No. 4, Electrical Engineering Research Laboratory, Engineering Experiment Station, University of Illinois, Urbana, Illinois (1965). 21. Spencer-Brown, G. , Laws of Form , Allen and Unwin, London (1969). 22. Varela, F. G. , "A Calculus for Self-Reference", Int . Journ . of Gen . Systs . (in print). 23. Church, A, "An Unsolvable Problem of Elementary Number Theory", Am . Journ . of Math 58, 345-363 (1936); Also in The Undecidable , M. Davis (ed), Raven, Hewlett, New York (1965). 24. Turing, A. M. , "On Computable Numbers, with an Application to the Entscheidungsproblem", Proc . of the London Math . Soc . , Sec„ 2, 42, 230-265 (1936-37) and 43, 544-546 (1937); Also in The Undecidable , M. Davis (ed.), Raven, Hewlett, New York (1965). 26. Kleene, S. C. , "General Recursive Functions of Natural Numbers", Mathematische Annalen 112 (5), 727-742 (1936); Also in The Undecidable , M. Davis (ed.), Raven, Hewlett, New York (1965). 27. Kleene, S. C. , Introduction to Metamathematics , Van Nostrand, Princeton (1952) _ 28. Hermes, H. , Enumerability , Decidability , Computability , G. T. Herman and 0. Plassmann (trans.), Springer-Verlag, N. Y. (1969). 29« Godel, K. , "On Formally Undecidable Propositions of Principia Mathematica and Related Systems", E. Mendelson (trans.), in The Undecidable , M. Davis (ed.), Raven, Hewlett, New York (1965). 79 APPENDIX OUTLINE OF RECURSIVE FUNCTION THEORY Recursive function theory has evolved from the many different efforts to formalize the informal notion of algorithm. These efforts all represent dif- r *. ■ jtu^t -4-u- j • 23,24,25,26 / , . ]_ . .. n ferent views of what algorithmic procedure is, ' ' ' but it is well established that each approach yields a different characterization of the same class of functions. This class of functions is called the class of recursive 11 12 27 28 / functions and has been discussed at length in the literature. — • ' * It is the purpose of this appendix to outline the concepts involved and to present those theorems of recursion theory upon which the formal material of this text depends. A similar outline can also be found in Lofgren — which 12/ uses the Turing machine formalism of Davis. — A-l. Algorithms The idea of using an algorithmic procedure for solving classes of problems is not new. The rules for the addition and multiplication of a pair of deci- mal numbers are algorithms for determining the sum and product, respectively, of those numbers. The Euclidean Algorithm is used to determine the greatest common divisor of two numbers. Although these algorithms have been known for centuries, it has been only in the last forty years that the notion of algorithm has been given formal status. A-l.l. The Informal Notion of Algorithm Rogers — lists the following features as being intuitive in the under- standing of the notion of algorithm: 1) An algorithm is given as a set of instructions of finite size. 2) There is a computing agent, usually human, which can react to the instructions and carry out the computations. 80 3) There are facilities for making, storing and retrieving steps in a computation. 4) Let P be a set of instructions as in 1) and L be a computing agent as in 2). Then L reacts to P in such a way that, for any given input, the computation is carried out in a discrete, stepwise fashion, without use of continuous methods or analogue devices . 5) L reacts to P in such a way that a computation is carried forward deterministically, without resort to random methods or devices, e.g., dice. These five features are almost universally accepted as being inherent in the idea of algorithm. Features 1) - 3) certainly are acceptable, whereas, 4) could be disputed on the basis that there are effective procedures for computing values of continuous functions for given arguments. However, there are more than countably many real numbers of which only countably many can be listed. Some of these numbers, e.g., tt, can only be "given" by specifying a non-ending procedure for writing down its decimal or equivalent expansion. In a computation, if one step depends on the exact value of tt, the final result, would not be forthcoming since it would take forever to compute the exact value', of tt. The notion of a "given number", therefore becomes confused. In carry- ing out the steps of an algorithm then, what is required is a precise method for distinguishing when one step of computation leaves off and another begins. An argument against accepting 5) as a feature of algorithms might be: one can list a set of instructions, such as, "Toss a coin. If it is heads, per- form instruction A. Otherwise perform instruction B." Surely such a process could be considered effective and the set of instructions an algorithm. The notion of algorithm, however, should not allow for uncertainty. In particular, it should always produce the same result every time it is applied to the same value of argument. Three additional, though less obvious, features of algorithms are' 81 11/ 6) Inputs to the algorithm may be of arbitrarily large, but finite size . 7) The instruction set may be of arbitrarily large, but finite size. 8) There should be no bound on the amount of "memory" storage space required for a computation. These three features of algorithms assure that the notion of algorithm is broad enough to allow for the effective computation of that which one might consider computable "in principle". If finite bounds were placed on the input size, the instruction set size or the storage size, the computation of something could be prevented which otherwise could be computed with, say, one more instruction or one more storage space. A further consideration for the notion of algorithm concerns the ability or capacity of the agent L which carries out the instructions. It might be of interest to know what size the agent should be, or what it should "know". Because the purpose of the instruction set is to direct L through a computation, one would expect that the agent would blindly carry out the instructions with- out lending into the computation any interpretation, which was not intended by the instruction set. Any decision process for the computation can be specified by the instruction set and L need only follow the instructions. If one con- siders how he carries out, say, the determination of the roots of a quadratic equation, he would discover that he needs only to perform a few operations such as move a pencil in a prescribed manner and make certain marks on a piece of paper. One could then expect that the computing agent need have only limited u-i. • ■ 11/ abilities . That is — : 9) There is a fixed, finite bound on the capacity or ability of the computing agent. 82 A final consideration is that of the length of the computation. One might wish to know a priori how long a computation will be. Or it could be asked whether there should be an upper bound on the length of the computation. Although it would be ideal to have an estimate on the length of a computation based on the instruction set and the input, it is not reasonable to expect that the computation of such an estimate would be any shorter than the compu- tation whose length it is of interest to estimate. On the other hand, we should expect that the length of a computation be finite in order to be useful. In other words — : 10) The length of a computation is not bounded, but is finite. Conceptually, a computation should end, but it should also have as much time as is necessary to do so. A-1.2. Formalization of the Notion of Algorithm—Church ? s Thesis The list of features above indicates our intuitive feelings of what proper-, ties are inherent in the notion of algorithm. Any list of statements offered as an algorithm can be checked against the feature list to determine whether it has the required properties. However, the feature list does not identify the class of algorithms. That is, although the list allows one to test for algorithmic candidacy, it does not indicate how to generate the class of algo- rithms. In an attempt to formally characterize the class of algorithms, or more precisely, the class of functions computed by algorithms, several compu- tational systems have been investigated. For each system it is argued that any group of statements which could qualify as an algorithm has a formal counterpar in that system. In addition, it is argued that any computational structure in the system is indeed algorithmic. Hence, the computations performed by the system are offered as formal counterparts to the computations which are 83 intuitively specified by informal algorithms. In particular, equivalences between functions computable by Turing machines, Church's ^-definable functions, Kleene's general recursive functions and other formalisms have been established. Strong arguments indicate that each of these characterizations provides an effective procedure for calculating any function intuitively thought of as being computable by algorithm. In Roger's words, — "On the basis of this evidence, many mathematicians have accepted the claim that the standard characterizations give a satisfactory formalization, or 'rational reconstruction', of the (necessarily vague) informal notions. This claim is often referred to as Church's Thesis ." In establishing the proofs to many theorems about recursive concepts (partial recursive functions, recursively enumerable sets, etc.) instead of producing a required function or set, oftentimes an effective procedure for producing such a function or set will be given, and its existence asserted by appeal to Church's thesis. This gives many proofs a more informal appearance, but such informality can upon request be replaced by strictly formal arguments. A-2. Turing Machines A definition of Turing machine is given in this section in order to pro- vide a basis for the enumeration of partial recursive functions which are discussed in section A-4. Conceptually a Turing machine consists of a tape which is arbitrarily long in both directions and a machine with a movable scanner which operates on the tape. The tape is segmented along its length into squares. Each square may contain, at any given time, exactly one symbol from some finite alphabet of symbols which includes the symbols B (blank) and j (stroke). The reading head may be positioned above only one square of the tape. Depending on which of a finite number of states the machine is in and the contents of the square under 84 the scanner, the machine will perform one of the three operations: 1. move the scanner right one square 2. move the scanner left one square 3. replace the symbol in the square with another symbol (or the same symbol), after which the machine assumes a new state (or remains in the same state). If iq ,q,, , ")'l } is the set of possible states the machine may assume, {s ,S ,-«-,S } (where S is B and S, is I) is the alphabet for the tape and o 1 m o 1 ' r v L (move left), R (move right) and S (replace tape square symbol with symbol S, ) are operations the machine can perform, the functioning of the machine can be represented by a set of quadruples of the following types : i. q.s.s.q. i J k 1 2. q.S.Lq, i J 1 3. q.S.Rq, . n i j ^1 The interpretation for these quadruples is: if the machine is in state q. with its scanner looking at symbol S., it performs the required operation (S, ,L,R) J K and assumes state q.. . The pair q.S. is called the initial pair of the n l v n i j quadruple . Definition A-l A Turing machine is a finite, non-empty set of quadruples such that no two quadruples has the same initial pair. The operation of the Turing machine is as follows. It is set to some initial state, a finite expression is placed into successive squares on the tape (assumed initially blank--that is, each square contains a B) and the scanner is positioned over some square. If this initial state is, say, q and the symbol in the square under the scanner is, say, S„, then the set of quadruples is searched for a quadruple whose initial pair is q S„. If such a quadruple 85 is found then the operation specified is performed and the machine assumes its new state, say, q_ . The machine is now in state q and the scanner is above a square with some symbol. The whole above process is repeated until the machine is in some state scanning a square with some symbol such that there is no quadruple with initial pair corresponding to the situation. If this happens, the Turing machine halts. A Turing machine may sometimes never halt after starting from some configuration on its tape. To compute a numeric function some conventions are assumed for the Turing , . 12/ machine . — 1. The numeric function computed maps N into N where N is the set of natural numbers {0, 1 ,2 ,3 , • • • } and N is the Cartesian product NxNx- • -xN. 2. One state of the machine is designated as the initial state for the machine. 3. A natural number n is represented initially on the tape by n+1 consecutive strokes. 4. The initial tape configuration for the argument (m . ,m-, • • • ,m ) is (m.+l) (m.+l) (m +1) ...B | l B | 2 B -.. B | n B ••• (m.+l) where | is m.+l strokes in consecutive squares on the tape. Each representative of a number on the tape is separated by a blank square . 5. The scanner is placed initially over the square containing the leftmost stroke on the tape. 6. After the machine starts, if it halts, the result is simply the number of strokes on the tape. (The strokes need not occupy consecutive squares on the tape.) 86 The reason for initially representing a number n by n+1 strokes is so that the scanner will be always placed over a square with a j in it. In this manner the number is represented by | . For example, consider the Turing machine defined by the following set of quadruples — : ^ l Bq o' q o BRq l' q ll Rq l» q l BRq 2 ,q 2' Bq 2^ ' This machine computes the function f(x,y) = x+y. Figure A-l shows the computa- tion sequence for the argument (x,y) = (1,2). The computation sequence halts with configuration (6) because there is no quadruple in the definition of the Turing machine whose initial pair is q„B. There are three strokes left on the tape, and so the result of the computation is 3. r B 1 1 B 1 1 1 B \ q o I B B 1 B 1 1 1 B \ q l L B B 1 B 1 1 B q i c B B 1 B 1 B q 2 L B B B B q 2 L B B 1 B B 1 1 B \ (1) (2) (3) (4) (5) (6) Figure A-l. The computation sequence for the Turing machine of Lofgren's example which computes f(l,2) = 1+2 = 3. 87 There exist Turing machines which, when started with a particular argu- ment on its tape, never halts. For instance, the Turing machine which has only B's and |'s on its tape and is defined by the quadruple set [q |Rq ,q BRq } , o o o o when started simply moves its scanner to the right ad_ infinitum no matter what initial configuration is placed on its tape. The function this Turing machine computes is undefined for all arguments. In general functions computed by Turing machines are undefined for some values of input. If a function com- putable by a Turing machine is defined for all natural numbers, that is, no matter what number is placed on its tape the Turing machine eventually halts, then that function is total. A-3. Godel Numbering of Turing Machines and Computation Sequences 29/ In his landmark paper, Godel — demonstrated a one-to-one correspondence between natural numbers and 1) denumberable symbols, 2) expressions of such symbols, and 3) sequences of such expressions. 12/ Davis — applies this method to Turing machines. Consider the ordering in Figure A-2 of all the symbols used in defining a Turing machine. For each i, S. is identified with the number 4i+7 and q. with 4i+9. With this identification of the symbols with odd numbers, it is then possible to identify quadruples with various even numbers. Simply form the product of the first four prime numbers, each prime raised to the power which represents the symbol in that position in the quadruple. For instance, the Godel number corresponding to the quadruple q S Lq. is 2 -3 -5 -7 88 R L S o q o S l q l S 2 q 2 S 3 q 3 X, X X . X. X X X. X X X 3 5 7 9 11 13 15 17 19 21 Figure A-2. The identification of odd numbers with the symbols used to define Turing machines. Other even numbers can be assigned to Turing machines, by forming a Gode] number from all the quadruples defining the Turing machine. For instance, let n..,n_,'"',n be the Godel numbers of the m quadruples defining a Turing machine. Then the number: m n. i Z = n Pr(i) x , i=l where Pr(i) is the i-th prime number, is a Godel number for that Turing machine 1 Notice that it is possible to distinguish a Godel number for a Turing machine from that of a quadruple. A GBdel number for a quadruple has an odd power for; 2 in its prime factorization. Whereas, since a Godel number for a quadruple is even, the power of 2 is even in the prime factorization of a Godel number for a Turing machine. It should be further noted that, since a Turing machine is a finite set of quadruples, there are n! ways to form a Godel number for the Turing machine if it has n quadruples. That is, there are n! Godel numbers corresponding to a given Turing machine . Finite computation sequences can also be given Godel numbers in a similar 12/ manner. — 89 Definition A-2 Let M be a Turing machine with alphabet G = [s ,S, , • • • ,S }. Then a o I. m tape expression for M is a finite (possibly empty; sequence of alphabet symbols from 6. A tape expression represents the symbols in successive squares on the tape for M. Definition A-3 Let P and Q be tape expressions for M such that Q £ 0, then Pq . Q is a state-tape expression for M, where q. e {q ,q , • • • ,q }, the set of states M may assume. Here the concatenation PQ is a tape expression for M and the significance of the q. is that it represents that the machine is in state q. and the scanner is viewing the square on the tape which contains the leftmost symbol in Q. For instance in Figure A-l the tape expression for configuration (4) is: BB |q B | | | B . That is, P = BB | and Q = b|||b. Definition A-4 An initial state-tape expression for M is q T QS where q is the initial state for M and QS is the finite tape expression which contains all the non-blank symbols on the tape such that S is the rightmost non- blank symbol on the tape. Again in Figure A-l the initial tape expression is q ||b|||. Definition A-5 Let M be a Turing machine, and let a and P be state-tape expressions. Then we write ot -► |3 (M) to mean that one of the following alternatives holds : (1) There exist tape expressions P and Q such that a is Pq.S .Q f3 is Pq x S k Q and M contains q.S.S, q, M i j k n l This is simply a restatement of Davis' Definition 1.7 in Chapter 1 of Ref. 12, 90 (2) There exist tape expressions P and Q such that a is Pq.S .S, Q 1 j k % P is PS .q.S. Q J Ik and M contains q.S Rq, . i J 1 (3) There exists a tape expression P such that Oi is Pq.S . i j P is PS.q B and M contains q.S.Rq... i J 1 (4) There exist tape expressions P and Q such that cv is PS, q.S .Q k L J p is Pqj_s k s q and M contains q.S.Lq,. i J 1 (5) There exists a tape expression Q such that oi is q.S .Q i J P is q BS.Q and M contains q.S.Lq, . i J 1 Definition A-6 A state-tape description a is called terminal with respect to M if for no P is it true that ot -» P (M) . Definition A-7 A computation of a_ Turing machine M is a finite sequence of state-tape expressions & } a , • • • ,Q? such that a is an initial state-tape expres- sion, Oi, -> a. . (H) for I < i < t and Ck 1 ^ is terminal with respect to M. l l+l — t At this point it is clear that Godel numbers for Turing machine computa- tions can be uniquely constructed. First, each state-tape expression on the computation C = (» 1 ot , • • • t ot ) is assigned a Godel number in a manner analogou; 91 to that of assigning Godel numbers to Turing machine quadruples. Let ex. = a-a • • -a, where one of the a.'s is a state symbol and the rest are 1 1 2. k j alphabet symbols for M. Then let gn(uu) be the Godel number assigned to object 0). Then: k gn( h(y)J. Then h enumerates the class of Turing machines as the following shows. 92 Definition A-9 M z is the Turing machine whose Godel number is h(z) as defined above. z is the index or GBde l number of M . Definition A-10 Let M z be the Turing machine associated with the natural number z. Then cp ' k ) is the partial recursive function of k variables computed by M . Z The superscript (k) is usually dropped when the meaning is clear or if k = 1, The subscript z is also called the index or Godel number of cp ^ . z Definition A-ll Let cp be a partial recursive function of k variables. .Then { (x , • • • yXy.) :cp (x. , • • • ,x ) is defined } is the domain of C£ ^ ' , by dom(cp (*■)). If dom(cp OO) = N then cp 'k; is a recursive function. Theorem A-l — ' There are exactly $\J partial recursive functions, and there are exactly Q{ recursive functions. Proof: All constant functions are recursive, by Church's Thesis, and hence there are at least y\ recursive functions. The Godel numbering of partial recursive functions shows that there are at most (A partial recursive func- ' o tions. Since the class of recursive functions is a subclass of partial recur- sive functions, the theorem holds. Q.E.D. Theorem A-2 — There exist functions which are not recursive. ^o * Proof: By Cantor's Theorem there are 2 functions from 1ST to N. Therefore the theorem follows from Theorem A-l. Q.E.D. Theorem A-3 — Each partial recursive function has XJ distinct indices. 93 Proof: Let 9 be given. Then M is the set of quadruples which computes o o cp . M has a set of states, say [q ,q, ,***,q }. If m is an integer greater o o than any of the subscripts for the states, and if M is modified by adding to o it the quadruples q q ,q ,, q .,,''*,q „ q ,. . the partial function deter- n m m+1 m+1 m+k m+k r mined by the modified machine does not change under the alteration, since none of the states q ,q -.^"'jq ,, can be assumed by the machine. As k varies, this m m+1 m+k J ' gives >{/ distinct sets of quadruples for cp . Hence there are ){) distinct o z o o indices for cp . Q.E.D. z o Theorem A-4 (The s-m-n Theorem) For every m,n > 1, there exists a recursive function s of m+1 variables such that for all z,y L , • • • ,y m , 9 ^ (x^x^ • • • ,X n ) = 9 z (j V '~,y m ,*i*'~.* n ) s n <*>y v '~,y m ) Proof: Consider some Turing machine, which when started with a representation of (x , ' ' ' ,x ) on its tape performs the following: 1. prefixes a representation for (y , • • • ,y ) to the representation for (x , •••,x ) already on the tape 2. proceeds to compute on the representation for (y_ , • • • ,y ,x.,-«',x ) according to the quadruples of a Turing machine M . Such a machine would have quadruples which when started places the tape expres- (y L +D (y 2 +L ) (y m+1 ) sion I B| B* • • B j B to the left of the initial tape expression (Xj+1) (x 2 +l) (x n +l) B| B • • ♦ B I , and it would have the quadruples of machine z with the subscripts on the state symbols initially transformed so that when the first set of quadruples has performed its task, the machine will be in state q which r is the transformation of the initial state of machine M . The scanner will be z positioned over the leftmost | on the tape and computation will continue according to the transformed quadruples of M . r z Now given any z,y ■ • • ,y such a machine can be constructed and its Godel number effectively computed. Hence by Church's Thesis there is a 94 m recursive function s of m+1 variables such that for any z,y, , ■••. v . s ( z »yi>*'*>y ) is the index of a Turing machine which performs as above. n 1 m r Hence for this function the specified relation of the theorem holds. Q.E.D. A constructive proof of this theorem in which the function s is demon- n strated explicitly is given by Davis. ■=£' A-4.1. The Halting Problem The problem of determining whether for any z and x, the computation cp (x) is defined is known as the halting problem . If M starting with x on its tape halts, then the value of the expression on its tape is given to cp (x) . If M does not halt, cp (x) must remain undefined. The halting problem can be restated as: is there an effective procedure which when presented with the numbers z and x will return a value 1 if cp (x) is defined and a value if cp (x) is undefined? Theorem A-5 settles that question. Theorem A-5 — There is no recursive function g such that for all z and x 1 if cp (x) is convergent g(z,x) = { j if cp (x) is divergent . Proof: Define a function t by , [ 1, if cp (y,y) = x ) f° r all z. Let L i- , x w n s 1 (w 1 ,z) 1 h(z) = s.(w.|,z) (since w will remain fixed throughout). Then cp (x) = K z »* for all z. Then cp . . ( x ) is convergent if and only if cp ( x ,x) = 0. Now assume 95 that there is such a recursive function g as in the statement of the theorem. Then for some z , g = cp . Then o z o cp . v (x) converges if and only if cp (x,x) = 0. o o Let x = h(z ) . Then o cp, , . (h(z )) converges if and only if cp (h (z ) ,h (z ) ) = . h (z ) o z o ' o o o But cp (h(z ),(h(z )) = if and only if g(h(z ),h(z )) = 0, that is, if and o only if cp, . . (h(z )) is divergent. Restated cp, . N (h(z )) converges if and J T h(z ) o h(z ) o o o only if cp %(h(z )) diverges. This contradiction shows that g cannot be o recursive. This completes the proof of this theorem. Corollary A-l There is no recursive function f such that 1 if cp (x) convergent if cp (x) divergent. Proof: If there were such an f, then g(x,x) in the statement of the theorem would be recursive. But by the construction of the recursive h from the defini- tion of i(f, any choice of index z such that g = cp would lead to a contra- ' J o z o diction, namely at the value h(z ). That is f(h(z )) = 1 if and only if f(h(z )) = 0. Hence there is no such recursive f. Q.E.D. A-4.2. The Recursion Theorems Theorem A-6 (Kleene's First Recursion Theorem) For any recursive function f of one variable, there is a number n such that cp = cp_, ,. n f(n) Proof — : Define a function if as follows (u,x) = CD / x (x) if CD (u) is convergent q ( u ) ' u u divergent if cp (u) is divergent . 96 By Church's Thesis, ty is partial recursive and hence by the s-m-n Theorem, there is a recursive function g such that k. The function f is recursive and A = range(f). Case 2. A is infinite. Let g be its characteristic function. Define a function f by : f(0) = M-y[g(y)=l] f (x+1) = M-yLg(y)=l and f(x) < y] . Since g(y) is recursive and A infinite, f is effectively defined for every x. Therefore, by Church's Thesis, f is recursive and A = range (f). Therefore A is recursively enumerable whenever A is recursive. Q.E.D. Theorem A-10 — Set A is recursive if and only if both A and A are recursively enumerable. Proof: Assume A is recursive. Then by Theorem A-8 A is recursive. Therefore, by Theorem A-9, both A and A are recursively enumerable. Now assume that A and A are recursively enumerable. If either A or A is 0, then A is recursive. If neither A nor A is 0, then A = range (f) and A = range (g) for some recursive functions f and g. Define a function h as follows: h(x) = M-y[f(y) = x or g(y) = x] . The function h(x) can be evaluated by evaluating in succession the pairs (f(0),g(0)), (f(l),g(l)), •••, until for some i, either f(i) = x or g(i) = x. Since f and g are recursive and since ALA = N, this procedure is guaranteed to give a result to h(x). Hence by Church's Thesis h is recursive. Now 99 define a function d as follows: f 1 if f(h(x)) = x d(x) = \ [0 if g(h(x)) = x . Since f, g and h are all recursive, d is recursive. Furthermore, since A range(f), d (x) is a characteristic function for A. Therefore, A is recursive. Q.E.D. Theorem A ■ll— 7 The set A is recursively enumerable if and only if it is the domain of a partial recursive function (that is, 3x[A = dom(cp x )]). Proof: Assume A is recursively enumerable. Case 1. A = 0. Let i|< be the partial recursive function which is everywhere divergent. Then A = dom(i|i). Case 2. A ^ 0. Then A = range(f). Define h by h(x) = ^y[f(y)=x] . A procedure for computing h would be, compute f(0), com- pare with x, if equal, give h(x) the value 0. If f(0) ^ x then increment y, compute f(y) and compare with x, if a match set h(x) = y. Continue this way until a match if found. If, however, no match is found, this procedure will not be defined for that particular choice of x, although since A ^ 0, h will be defined for other choices of x. Hence h(x) will be defined whenever x is in A. h is therefore partial recursive by Church's Thesis. But then there exists a z such that h = cp . Therefore A = dom(rp ). Now assume A = dom('Ji) for ^ a partial recursive function. If A = it is partial recursive be definition. If A ^ then the following effective 100 procedure will list A. The procedure is carried out in stages. Stage 1. Perform one step of computation on KO); if K0) converges, place in the list for A. Stage t+1. Perform t+1 steps of computation on each of ^(0) , i(l) , • • • , ^(t)i For each of these which converges on or before the t+l st step, place its input in the list for A. Increment t and repeat. While this procedure is going on, the function f can be defined as follows: f(0) = the first member of the list f i M-y[y has been added to the list during stage x+1 and ye{f(0),f(l),---,f(x)}], if such f(x+l) = \ ay exists f(0) otherwise . V By Church's Thesis f is a partial recursive function, and since A ^ 0, it is defined for all x. Therefore, f is recursive and range(f) = domain(i|0 = A. Hence A is recursively enumerable. Q.E.D. Corollary A-2— / Set A is recursively enumerable if and only if A is the range of a partial recursive function (that is, jx[A = range cp J). Proof: Assume A is recursively enumerable. Case 1. Same as before. Case 2. Define the function & d(x) = f(h(x)) where h is the partial recursive function in Case 2 of the theorem. Since f is recursive, d is partial recursive and A = range(d) . Now assume A is the range of a partial recursive function l|f. Proceed as in the proof of the theorem, to list members for A, except place the outputs at 101 each stage in the list for A, instead of the inputs. Then the function f that is defined is recursive and lists the elements of A. That is A = range(f) and hence A is recursively enumerable. Q.E.D. Theorem A-12 The set K = {x:Cp (x) converges} is recursively enumerable but not recursive. Proof: Define the function i|i as follows if cp (x) converges divergent if cp (x) diverges . By Church's Theorem, i|> is partial recursive. Also K = dom(t). Therefore K is recursively enumerable. By Corollary A-5 it is obvious that K cannot have a recursive characteristic function. Hence K cannot be recursive. Q.E.D, Definition A-15 Theorem A-13 W = dom(cp ) . x r x There exist recursive functions f and g such that for every x and g, W £/ . = W U W and W , , = W fl W . f(x,y) x y g(x,y) x y Proof: Define ty as follows if cp (z) converges or cp (z) converges divergent otherwise, By Church's Thesis, i|i is partial recursive. By the s-m-n Theorem there exists a recursive function f such that CD-/ \(z) = t, (x.y.z). Now 1 f(x,y) 1 ,J z«W.. . implies that ♦, (x.y.z) = 1 and that either cp (z) or cp (z) converged f(x,y) r 1 '-'' T x y That is zew or z£W . Hence W-, , c W U W . Now, if zew U W , then x y f(x,y) - x y x y' 102 either zeW or zew and either cp (z) converges or CD (z) converges. There- x y x T y fore cD, (x,y,z) = 1 and CD... . (z) converges. Therefore zeW r/ .. Therefore Y l -" Y f(x,y) ° f(x,y) W £/ s = W U W . f(x,y) x y Now define iL as follows t (x,y,z) r i f both Cp (z) and CD (z) converge T x y divergent otherwise . Now by Church's Thesis, iL is partial recursive, and by the s-m-n Theorem there is a recursive g such that cp . . (z) = i|f(x,y,z) for all x and y. It 6 H g(x,y) v TV ,y > y is readily demonstrated then that W , . = w fl W . Q.E.D. g(x,y) x y A-6. Recursively Enumerable Relations Definition A-16=^' 1 (- 2, ~| The function c(x,y) = gL(x+y) +3x+yJ is a coding function . Obviously c is recursive and the Table 2.1 shows that it is a one-to- one mapping of NxN onto N. Definition A-17 The function & and r of one variable are the functions which yield the inverse mapping to c. That is, for all z, c(i(z),r(z)) = z. Denote the value of c(x,y) by \x,y) . The following definition shows a one-to-one mapping of N^ onto N for all k > 0. Definition A-18 ^(x) = x T k+1 ( Xl ,x 2 ,...,x k+1 ) = r Denote T (x, , • • • ,x^) by (x, , •••,x, ). Obviously T = c. 103 Definition A-19 An n-ary relation R is recursively enumerable (recursive) if T n (R) is recursively enumerable (recursive) (here T n (R) is the set [(x, ,?**.x ):(x, .•••.x )sr}. 1' n 1 n Theorem A-14 The n-ary relation R is recursive if and only if both R and R are recursively enumerable. Proof: Let R be recursive, then t(R) is recursive. But the t(R) and N-T(R) are recursively enumerable. Hence R and R are recursively enumerable. Let R and R be recursively enumerable. Then t(R) and t(R) are recur- sively enumerable. Let f and g be recursive functions which enumerate T (R) and t(R) respectively. From these functions a recursive characteristic function for t (R) can be constructed as in the proof of Theorem A-10. Hence t(R) is recursive and therefore R is recursive. Q.E.D. It can be shown that the coding functions in fact render meaningless any notion of dimensionality in the theory of recursive functions. All func- tions and relations can be treated as if they were unary, binary or n-ary relations . — Definition A-20 The set {(x, ••• x. , .x, ,,,'•• .x ) : i)x .R(x_ , • • •, x } is called 1 j-lj+1 n j 1 n the pro jection of R along the J coordinate . Theorem A-15 — (The First Projection Theorem) If R is recursively enumerable, then there is a recursive relation S such that R is a projection of S. Specifically, if R is R-ary and recursively enumerable, then there exists a (k+l)-ary recursive S such that R = f (V-> x k ):3x k + i s( V"' x k + i )] • 104 T k. T Proof: Let R = T (R) . Then R is recursively enumerable. Therefore, there f is a partial recursive function y such that R = dom(f). Let m be a fixed index for l|i and M a set of quadruples which computes t. Then m rT R(x 1 ,---,x k ) » eR « \|(('''-> 0i t anc ' n ■"" s tne va l ue °f the tape expression in the state- tape expression ot . otherwise . Given any number y it can be effectively determined whether y is a Godel number for a computation sequence. If it is, it can be uniquely decoded into the state-tape expressions and the value on the final state-tape expression can be determined. Hence U is a recursive function. Likewise in the arguments for the T-predicate it can be decided whether z is the Godel word of a Turing machine, and if so that number can be decoded into the quadruple set for M . Then with x on its tape, a computation can be 106 started, and the initial tape expression can be compared with cr in the 11 decomposition of y (if y is the Godel number of a computation sequence). If they are not the same, T(z,x,y) is false. If they are the same, the next computation step is performed and state-tape expressions compared. Since y is finite only a finite number of computation steps need be taken and only a finite number of comparisons made. If each comparison is successful and if & is terminal, then T(z,x,y) is true. Hence it can be effectively decided whether T(z,x,y) holds or not, and by Church's Thesis T(z,x,y) is recursive. Now the value |^y[T(z,x,y) ] is partial recursive for each z and x. The reason for this is, that in order to evaluate the expression, the sequence T(z,x,0), T(z,x,l), T(z,x,2), •••, must be evaluated until eventually (if ever) for some t, T(z,x,t) is true. However, this may not be the case and My[T(z ,x,y) ] may not be defined for some choices of z and x. Theorem A-18 (Normal Form Theorem) Any function f is partial recursive if and only if there such that f(x) = U(uy[T(z ,x,y)]) . exists a number z such that o Proof: Assume such a z exists. Since |iy[T(z ,x,y)] is partial recursive and U is recursive, by Church's Thesis the right hand side of the equation is partial recursive. Hence, any f so defined is partial recursive. Assume now that f is partial recursive. Then there exists a Turing machine with Godel number z such that M computes cp = f. That is whenever f(x) is defined o z r r z o o M performs a computation resulting in the value f(x). If f(x) is undefined, o M will compute forever without returning a value. Hence if f(x) is defined z o uy[T(z ,x,y)] is defined. If f(x) is not defined uy[T(z ,x,y)] is not defined in either case f(x) = U(uy[T(z ,x,y)]) . Q.E.D. IBLIOGRAPHIC DATA HEET 1. Report No. UIUCDCS-R-75-708 UIUC-ENG-R-75-2539 3. Recipient's Accession No. Title and Subtitle THE RECURSIVE NATURE OF DESCRIPTIONS: A FIXED POINT 5. Report Date April 1975 Author(s) Larry J. Peterson 8- Performing Organization Rept. No. Performing Organization Name and Address Department of Computer Science University of Illinois at Urbana -Champaign Urbana, Illinois 61801 10. Project/Task/Work Unit No. 11. Contract/Grant No. |. Sponsoring Organization Name and Address Biological Computer Laboratory Department of Electrical Engineering University of Illinois at Urbana -Champaign TTrKana Tllinms 61801 13. Type of Report & Period Covered Doctoral - 1975 14. i. Supplementary Notes in part supported by a grant from Point Foundation, San Francisco, CA, hrough the Biological Computer Laboratory, University of Illinois at Urbana- hampaign, Urbana. I Hingis — 6_18_0_L i. Abstracts ^^ j_ n tuitive notion of description is formalized in a manner which ^fleets the computable nature of descriptions. Both the denotative and connotative spects of description are indicated in the formalization. The structures arising rom the repeated application of an interpretation to the result of the previous iterpretation of a description is examined. The notion of a \|r -description is atroduced and the structure of heuristic procedures for constructing the function is examined. Finally, fixed point behavior of iteratively applied interpretations 3 descriptions is discussed and the possibility of effectively constructing self- perators is speculated about. . Key Words and Document Analysis. 17a. Descriptors description interpretation partial recursive function fixed point stable behavior b. Mentifiers/Open-F.nded Terms c COSAT1 Field/Group • Availability Statement release unlimited RM NTIS-15 ( 10-70) 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages J£6_ 22. Price USCOMM-OC 40329-P7I #* \tf> UNIVERSITY OF ILLINOIS-URBANA 510.84 IL6R no. C002 no 708-71 1(1975 Report/ 3 0112 088401895