ion Nos Le a Hai 3.1.1 Bele2 Bede Balely Bele 3e1.6 Bele 30108 Beled 3.1.10 3.1.11 3.912 301613 Bedell Ae 362.1 3.21.2 3e2.1.2 Be2e]63, Qu. AN INDUCTIVE INFERENCE MACHINE ers i Table of Contents Introduction: Description of inductive procedure im humans and a correspondence Setween elements of this procedure and slements in the machine. A general description of the kinds of problems the machine solves, end how it solves them....++++ Deteiled description of machine behavior and operation. .+ Definitions of terms.. Digit...+ Blement.. Q Blement.. Interrogation square..+++.+ N-gram (ngm) -- P N-Gram (pngm) «++ N-Gram countess. P NeGram counter ssesseeeeereees GaseSssceeeeecerececeerereee ees Consistency. N-tuple (ntp) -- Structure (str) se.+se++ Multiplication. . Uehlity (U) se Mode of operation. wonnneroa Be B85 w 8 : e b “ Bb B b —£ Steady state operation, after initial transients have died Gown..-+++++++ The five memory banks of the machine aL a. 3. ke 5 How the machine makes predictions. & 2 E Pagm memory Nem momory Wtp memory Str memory Array memory . seeeeeee ay iow the machine creates new abstractions from old ones that heve been found to be [Link] wees as Lparwntt ‘helTable of content: ’ Section Nok Page No. ' 3.201.321 Structures transformed into structuresessres 15 [Link]:2 Netuples and n-grams trensformed into netuple se. a oveevedactaceete it [Link] Structures and n-tuples transformed into ngrems and p ngramses+ sapeeees 18 [Link]: P ngvame and ngrems transformed into p nerent 19 [Link] P ngrams transformed into p ngrems and .ngrams 19 3e2e12366 Some inversion techniques. eoaeiew 20 ' 3e2e1el How the machine assigns @ priori and 8 posterior! utilities to various abstracy : Exons end prediction methods. In par 1 ticular, to ngms, stra, ntps and PEmsss++++ a1 | 2.165 Equations for operation of a simplified a TUChiNG ,seseaceceereenoerstedpepeweeeeger ere 23 Be2el.6 Rules for operation of a simplified machines Am operating Progralivsses+ aaeeeeeeeoee 26 36242 Initial ngs, ntps, strs and pngns, Initial values of prediction paramoterss+.+erreesers 29 de Examples of machine operation...++ 29 del A training sequence of 20 problems.. 30 Lee Discussion of machine response to problems ie i 5 Pubure Worksscssseececteoeeeeeabareeeeseen es ye : Sel Some new definitions and a modification of ap ola one, resulting in a very poworful machine 1anguages.++er* 42 5.2 New abstraction combination methods ~~ the i concept of “function” — Boolean combina~ I $lons Of SCtBresceseeccdeserne Ay 503 Modification of the machine for probablistic a (non-detorministic) prablems..«sroesseecrsee Ay i Say Future problems tobe solved by the machine uh Seb Use of machine training sequences as training sequences for childrons.++e- us 6 Evaluation of machine as a study tool.- . 4s 5 Appendix I: Exemples of MultiplicationPREFACE Le AN INDUCTIVE INFERENCE MACHINE by R. J. Solomonof£ Technical Research Group New York City A machine is described which is designed to operate as human beings seem to. Inductive inferences are made by classifying eeents and the outcomes of these events within suitable cate~ gories. The inductive inference in the individual case is B0%e on the basis of the average behavior of events within the category used. Accuracy of inference is largely depéndent upon how good the categories are. Most of science can be viewed as attempts fo find useful ways to categorize phenomena. The inductive inference machine takes categories that have been useful in the past and, by means of a small set of trans- formations, derives new categories that have reasonable like- 1 Uihood of being useful in the future. ‘These are then tested eapirically for usefulness in prediction and the new useful Gans are combined with old useful categories to create newer ones NTmese, in turn, are tested and the process is repeated again and again. A simplified machine was devised to illustrate the operation ge such devices. Since it utilizes only part of a more com- \ plete set of transformations, it performs only relatively Eimple learning tasks. Its behavior in learning to perform Some arithmetic operations on the basis of a set of correctly Sorked examples is analyzed. Operation is described with al~ host sufficient detail for programing on a digital computer. At even the most elementary level of complexity, recognition ef erructural similarities and performance of substitutions Peceme natural developments of the heuristic devices that are 7 Reed. At a slightly more complex level, relations, sets, and hierarchies of sets develop.‘The simplified machine that is described here operates on problens in which there is one and only oné correct answer. by making the machine operate on statistical training se~ quences and asking for probability distributions as. answers qorproblens, sensitivity to errors in input data is decreased. Tt fs also possible to progranme such a machine to work on the problem of improving itself. Using the more complete set of transformations, it is expected that these machines will ultimately be able to prove theorems, play good chess and answer questions in'English. A preliminary Pnalysis of the relationship of these devices to the work of Ghongky on English grammar, indicates that these machines would probably be able, to recognize the difference between a "gram: Eatically correct" and a "grammatically incorrect" sentence in Ghomsky's best approximation to English, providing the machine was given a training sequence of grammatically correct senten- ces. Sections 2, 3 and 4 describe the simplified machine in some stall, as well as its response to a set of examples and prob- ‘ems. Section 1 is rather general, and applies to more com- plex machines, as well as the simplified type. Sections 5.1, and 5.3 are descriptions of some of the heuristic devices 2h4 transformations that are used in the more complex machines.oe om August 1h, 1956 AN INDUCTIVE INFERENCE MACHINE By R. de Solomonoff 1. Introducti The following is.a description of a machine which is designed to learn to work problems in mathematics by being given 2 series of examples of correctly worded oxamples, After the machine has been show several examples, 1t 1s able to evolve a method by which they might have all been solved. When the machine is given new problems, it uses this method to work them. The operation of the machine is meant to follow what the author velieves to be a process by which much abstract learning takes place In man, A person solving simple problems will try @ series of simple methods. He will tend to remember the methods that have been suc~ cossful and discard those that have been useless. When he is given a new set of more difficult problems, he wili first try the methods of solution thet have been successful in the past. If these fail, he will combine these once successful methods to ob— tain new trial methods. The ones thet are most often successful will be used on the next set of problems. The process continues in this manner. ‘he techniques by which methods of problem solving, that have been successful in the past, are combined to form new trial methods is, I believe, the critical problem in all problem solving and in- duction, Several methods have been found to be of great applica~ bility.oe An important guide to selentific methodology 1s our spoken ana written languagg. For the purposes of problem solving end prediction, we shall define "word" to designate any sot of pos~ sible or actual objects, or space-time configurations, in the wonld, fn example of a "word" might be "pencil," which designates the set of all possible pencils. Another "word" in this sense would ye “a rainy day in Egypt” -- which designates the set of all such possible days, Another would be "35° contigrade," which desig— nates all parts of the world at that temperature. There ave two kinds of words we shall sxamino. The first kind is exemplified by "cloudy weather," “rainy weather," "automobile," "gasoline." The property of these words that is useful is that certain of them have a high space-time correlation with certain others. For example, if we observe "cloudy weather," we expect "rainy weather" in the immediate space-time neighborhood -- and vice-versa. If we observe an Yeutomobile," we expect "gasoline" to be found, with high Like Lihood, in a cortain spacial orientation with respect to 44 —— i.e., in its gas tank. Phe finding of "words" that have a high and useful correla~ tion with other “words" has been, by far, the most important task of science. The second kind of "word" consists of two or more "words" of tho first kind, in a particular space-time orientation with re~ spect to one encther, with a probabilistic implication relation petween the various parts. An example would be “automobile” — consisting of on "engine," "gasoline tank," "wheels," etc. If weobserve part of the "automobile," we expect to find en “engine" in a certain spacial orientation to the part of the "automobile" we have seen. The "automobile" Includes various "words" es parte of it, and the presence of any group of such parts probabilisticelly implies the others. The implication may be unidirectional, however. For example, the presence of most of en “automoblle" may male She prosence of an "engine" very probable. However, observation of ‘engine implies the existence of the rest of an “automobile” with somewhat less probability. Associated with a "word" of the second kind 1s 2 set of prob~ abilities —- one for each part of the word -- that gives the prob~ ability of that pert occurring if the rest of the "yord" is observ Ib will be noted that most words that we use are of both types simitaneously. However, in designating them "types one and two,” we have @rawn attention to different aspects of their use in inducé tion. It is clear that vords of the second kind cen be easily used for prediction. rial words of the second kind can easily be con~ structed by specially orienting words of the first kind with re spect to each other in various ways, ‘These are then tested for usefulness in prediction, The useful "words" are retained and given symbols, like "automobile." The useless ones are never used and are immediately forgotten. The useful words ef the second kin ave used as trial words of the first kind, They ere combined spacio-temporally with other words and trial words of the first kina, to produce trial words of the second kind. These latter are tested for their effectiveness in prediction, The words of the first kind that are effective in producing useful words of theie second kind are retained in the lenguage and given symbols —~ like “engine.” Trial words that have not been useful are always dis- carded. While many abstract operations can be expressed in terms of "words" of the first and second kinds, they are by no means adequate to cover all interesting phenomena. "Words" have been defined to mean sets of possible or actual objects in the real world. To cover more complex phenomena, we will need sets of words. ‘These will correspond to sets of sets of objects. We will also need higher order sets of sets of sets, etc. Im order to avoid certain paradoxes associated with higher order sets, B. Russell has evolved the "theory of types." It is likely, however, thet we will have no need to avoid these para~ doxes by spevial logical rules. We can, in a statistical machine, steer clear of such paradoxes in a very natural way by noting that the operations that form them tend to be of little value in pre~ @iction. Even if these operations psually do turn out to be use~ ful, we shouldn't be surprised if they are occasionally of little value. In the description of the operation of the machine, the ob- jects that correspond to words of the first kind are celled "n grams." Objects-corresponding to words of the second kind are called "prediction n grame." An ordered set of n words of the first kind, that is to be made into a word of the second kind, corresponds to what is callec an "n-tuple.* ~ A set of instructions corresponds to what is called a "struc— ture" if 16 tells how to mtually orient in space~time a set of words of the first kind to form a word of the second kind.The application of the above-mentioned instructions corres— ponds to the operation of a "structure" upon en "n-tuple" to form a "prediction n gram," It should be stated at the present time that the machine de~, seribed here is intended to be only a preliminary approach to the problem, designed to clarify the general method of operation, The prosent machine can only learn the most elementary arithmetic op~ erations, Significant operational modification must be made before it can learn anything interesting, though the direction of develop~ ment seems quite clear at the present time. It should also be noted that this is not a "progress report" in the usual sense, but merely serves to indicate in what direction work is proceeding and the general approach used. It is not moant bo indicate the state of development of the work. 2. General description. 2.1 The problem. The machine is at first presented with many examples of cor~ rectly worked arithmetic problems. An example consists of a lo x 7 rectangular array of digits. Hach digit may be 0, 1, = +, s (space) or any of many other mathematical symbole. The machine is then presented with an example in which one or more of the digits have been omitted. It 1s the problem of the machine to compute what these digits should be.—* ee Some examples of correctly worked problems presented to the machine are: =1o001 Folil =1000 =ooll 1001 o1il 1000 oor. ~O102 ~1002 ~ooll ~o001 Lolo o110 L100 aiig Each of these examples is presented somewhere in its 7 x 10 array. A problem might teke the form =0010 or Bee eae oo0° Oo10 The machine mst then give the digits that are appropriate to each of the blank squares. 2,2 How the machine solves the problem. The most elementary method used utilizes what are called n— grams, An n-gram is a spacial configuration. of n digits. Soms 1 =1 ~ail 10 ° 1 ol 1o. examples are: These n-grams are, respectively, a digram, a trigrem, a pentagram, anda tetragram, By designating one of the symbols of an n-gram as the "predicted digit," we can use n-grams for prediction, For =L example, the n-gram would be useful in prediction if, every time the pair of digits =1 sppeared in this relative posi tion, another 1 appesred below the 1. For the set of examples shown above, the n-grams i 0 , 12 ng MOL ave 022 usefel, since the [J] om 10 of]-1- closed digit is always implied whenever the rest of the digits eppear in an example. qhe positive or negative verification of the usefulness of an n-gram in prediction is a relatively routine task, as ts the problen of prediction itself, once a set of useful n-grams has been found. An important, difficult problem of the machine is to find n- grams that are likely to be useful in prediction. One method the machine uses to find n-grams that are likely to be useful is to take n-grems that have been useful in the past and place them in various relative spacial orientations. The resultant configura- tions of digits are n-grams that are of reasonable probability of usefulness. N-grans may have either or both of two types of usefulness. Firet, thoy may be directly useful in prediction of digits. Sec- ondly, thoy may be useful as components, to be combined with other negrams, to produce n-grams of the first type. che methods of spacially orienting various n-grems of the seconé type involves a special construct, called & "structure." Various methods will be devised for obtaining useful "structures." It is possible to form more complex entities than n-grams, whieh are also useful in prediction, One such entity that is of much Importance is a set of n-grams. ALL n-grams correspond to certain sub-sets of the set of all possible configurations of digits on the 7 x 10 array. The use of sets of sets end sots of sets of sets, ste., will become ex- tremely important in meny problems.3. Detailed Description. 3e1 Definitions of terns: 3ele1 Digit: A digit is eny one of the mathematical symbols that may occupy a position in a 7.x 10 array, Some digits that will be used are 0, 1, =, ~, +, X, 8 (denoting space), @, and @ = 3.1.2 Element: An elenent is a 7 x 10 rectangular array of 70 digits, If there are 9 different possible digits, then there are g” different possible elements. 3ele3 QBlement: An element that has one or more of its digits missing. The completion of these g elements is the problem that the machine must solve. An example of a q element is: =1000 inoue The configuration shown is placed somewhere in a 7 x 10 array. 3.1.4 Interrogation Square: A position of a missing digit in 2 g Sloment. The interrogation squares in the above example are marked by the symbol C) i 3.165 N-Gram (abbreviation n-gm): A spacial configuration of i Gigits. These digits must have coordinates that are integers only. zl 10 7 el Some n-grams are ‘i eee is a trigram; ae 10 ° 1 3 12 and 10 are tetragrans. There is a one to many mapping from o commen the set of all n-grems to the set of all elements, Hach n-gram maps to all elements thet contain it, Associated with each n-gram, elemont pair ie a number, which tells how many times the n-gram is contained in the element. For example, let us take the element:assssss5S8 ssssssSsso5 ss=1000sss sssl000ss65 sssssS5588 assessssss sassassss8 The symbol "s" denotes a blank space.) the @ignan 9 19 contained in the element three times; the digran 1 is contained onve; the trigran °C twice; the digran ©, four times, ote. 3.166 P negram (prediction n-gram: abbreviation, p n-gn): An n~ gram that is to be used in prediction. Such an n-gram will have t digit that is predicted enclosed in a square, Some examples of p n-grams ars: a: -@; "ae To ote. corresponds to a statement that every time the The p digram digit 1 appears, the digit 1 should appear just below it, Similar’ 9 the p trigram states that, whenever the pair of digits = 0 B interen digits appear, then a 1 should appear just below the zero. In general, most p n-grams are not accurate in their predic~ tions. The p n-grams will, at the beginning, bs fairly useful in prediction. The p trigram ~)% will never be useful in prediction, If the machine were given the g element sssss8as5853 sssssssss58 ss=L100Cisss sssl000ss8 ssssssssss sessssssss ssSS8558858-lo- then the p trigran ~ Q would correctly predict that the occupant of the interrogation square should be 1. The p digram @ would dmeorrectly predict that the occupant of the interrogation square should be 0. 3.1.7 N-gram count: As time goes on, various elements are presented to the machine as correctly worked examples of arithmetic problems. These include correctly completed g elements that had been presented to the machine as questions to be answered. ‘The total number of times that a certain n-gram has appeared in all elements presented to the machine up to time t, will be called the n-gram count of that negrem at time t, Often an n-gram will appear several times in an element. If m elements have been presented to the machine up to time t, then the ram count of certain simple n-grams [e.g. 0 1] may be many times as large as mm. 3.148 BP Negram count: If one removes the square surrounding the predicted digit of a p n-gram, then en n-gram results. The n-gram count of this n-gram, at time t, will be called the p n-gram count of that p n-gram at timo t. 3ele9 Cases: The number of cases of a pngram, ab time t, is the number of times that this pygram has been applicable to predic— tions of the contents of interrogation squares. A p n-gram may have more then one gase in a g element if that q element contains nore than one interrogation square. 3e1e10 Consistency: From a p n-gram, romove the prediction digit and the square surrounding it. Substitute for the prediction digit each of the possible digits, in turn, other than the predic- tion digit of that p n-gram, If the n-gram counts of each of theeget resultant n-grams, up to time t, are zero, then we will say that a p n-gram means that no counterexamples to its predictions have Seem dee been observed. . | tho p n-gram of interest is consistent at time t. Consistency of 3.1.11 N-tuple (abbreviation; ntp): An ordered set of n-grams and p n-grams. The total number of n~grams and p p-grams is NW. Some examples are: eee which is called a ; secrete tea Oneal ee “tripte," , +, 9, i,0)wnien ts caltea = "pantuple," (. » 90) watch is called a "pair" or "double," and G ») which is called a "singlet" and consists of a single n-gram or B breren. 3.1612 Structure (abbreviation;str.): A set of positive integers i placed at various integral coordinate positions on @ two-dimensional Cartesian grid. Some examples of structures are: y uf Zz r El LBL tt 2 : , El, Gist, GB 3.1,13 Multiplication: An n~tuple multiplied by a structure yields a set of n-grams or p n-grans, The set may contain ono or more members, or no members at all. To perform the multiplication, select one digit from each n-gram or p n-gram of the n-tuple. Place the chosen digit of the i°® component of the tuple in all of the coordinate squares of the structure that are occupied by the digit 4. Hach such digit should be surrounded by the properly | oriented digits of the rest of its n-gram or p n-gram. If the resultant configuration does not cause any of the digits+ — -12- to overlap, we will have an n-gram or p n-gram. Chosing digits from the components of the n-tuple in various ways will result in different n-grams or p n-grams after miltiplica~ tion by the structure. The set of all such resulting n-grams or * p-n-grams constitutes the result of multiplying the n-tuple by the structure. For examples, See appendix I. : Zelelh Utility (abbreviation, U): After the machine has operated for some time, it will be found that certain p n-grame will have peen very useful. in prediction, and others have been less so. it is possible, in various ways, to assign a value to the effective~ ness of a particular p n-gram in prediction. As @ simple approx~ imation, we may use the “average nunber of cases per unit time" as such a measure, We may, in addition, postulate thet p n-grams that ere not consistent are to have U = 0, since they will not be used in prediction in the machine that is being described at prese In the operation of the machine, p n-grams will continually ts created by combining strs, ntps and ngms in various ways. These methods of combination will be described later in some detail. We would like to assign U's to strs, ntps and ngms, so that, when they are combined to form pngms, the ultimate U of this pngm will be well approximated by a kind of average of the U's of the strs, ntps, and ngms from which it was constructed. If a pngm has just been created and has had no cases yet, its U will be determined by the U's of the components from which it was constructed. As the machine is given more q elements and more eases of this p n-gram arise, the value of U will drift from its initial "a priori" value and be controlled to a groater extent by empirical information on its utility in prediction.-13+ The ‘U's will be assigned to ngms, strs and ntps so as to op- timize the "a priori" approximations of the ultimate Usof the pnams that they are combined to form. An example will te given of a simplified situation in which U's are assigned to structures and n-tuples. Let S$, be a set of structures and let U, be their as yet undetermined utilities. (i =1, 2, » m) Let nj be a set of n-tuples and U, be their utilities — i also unlmown as yet. (j= 1, 2, «+, r) Let U,, be the utility that was observed for the p n-gram that is formed through multiplication of nj by S$). This Uj; should be obtained after the machine has been in operation for @ long tine, so that U,; 1s close to the ultimate U. : ' + We want to chose our U5 sand h, 8 so thab Uy; approximated by U, + U, , as well as possible. Woe have m+ 7 4 quantities to adjust and mr quantities to optimize. This is a is problem which is solvable by known means, Since m end r may be large, it may be necessary to use some ingenuity in arriving at a reasonable solution. It is, however, quite adequate for the values of the U's to be very approximate and first approximations to the U's are also available, so that computation may not be out of the question. A simple epproximation that seems to work is:3.2 Mode of operation. 3.2.1 Steady state operation: 3.2ele1 The machine uses five memory banks. l 2. 3. 5. 342.142 To tion square Contains pngms. With each pngm is contained its i pgm count, the mmber of cases that it has had, ite U, and the a priori U which was obtained from the ngms, strs, ntps or pngms, from which this pngm was constructed. This memory bank is called the "pngm memory. Contains ngms, their ngm counts, and their U's. Contains ntps and their U's. Contains strs and their U's. Contains all elements and q elements that have ever been prosonted to the machine, ‘This memory benk is called the "array memory." make ‘predictions, the machine examines the interroge— of the q element, finds a p n-gram that fits the prob- lem, and makes the prediction that corresponds to that p n-gram, Upon very rare occasions, there will be two p n-grams that fit the same interrogation square, and these p n-grams will give different predictions. In such a case, the probability distribution between the two predictions may be made proportional to the ratio of the respective counts of the two p n-grams. Such cases Will be rare because. as soon as the correct answer is known, one of the opposing p n-grams will lose its consistency —~ and that particular pair of p n-grams will never disturb one another again.a ee -1s- For example, take the q element ~1011 Dioo. Suppose we have the p n-grams “a and a , both being consis tent up to the present tine. Both give different predictions for the interrogation square. If the p n-gram count of a is 9 and that of ‘a. 7 then the probability of the prediction 1 may be teken to be yk, that of the prediction 0, yh. It should be noted that, in certain cases, the predictions of the machine will be poor, because of inadequate history. In such eases, there is nothing that can be done to im- prove a particular prediction very moh, If there are competing pn grams, so that a probability distribution mst be given, rather than a single prodiction, we have an example of a case in which the best prediction possible is not a vory good one, [Link] In addition to moking predictions, the machine is at all {imes combining ond transforming n-grams, structures, and n-tuples, to produce sew n-grans, structures, n-tuples and, ultimately, p n-grans. To describe those processes, let us first assume that the ma— chine has been operating for some time and has a large supply of useful phems, ngms, strs and ntps. Some important motkods of combination and transformation are: 3.201.301 Old structures are transfor od into new structures. Before describing these transformations, mention should be made of what will be called the "distance" between two structures. The application of this notion of "distance" is that, ifod es there is a certain empirically observed U associated with a certain structure, then the a priori U's associated with structures that are a amali “distance” from it are not much smaller than the em— pirical U of the original structure. The a priori Uwill, in. general, be a decreasing function of the "distance" from the original structure. 3.2:1.3-lea New structure is "close" to the old one in a simple [31 T2[3] 1s "close" to sy = [LZ and to geometric sense, Some examples are? s,= Rleal [3] - It is easy to devise a measure for such "closeness." A pos— sible measure might be: If two structures are identical, except that an integer 1, in the first, is in a different position from the seme integer 1, in the second, than the "distance" between these two structures is the Euclidean distance between the centers of the squares in which these two integers occur. Using this definition of "distance," the "distance" between S$, and S, is 1, between S, and S$, is 1, vetween S, and 8, isV2. gis 3.201.3-1.b Hew structure consists of the old structure with «a additional integer added. For exanple, the old structure might be s, = ffslel, the new % ° ER "Distance" between old and new structures would be a function of (1) the Euclidean distance between the new integer and the closest integer of the old structure and (2) the numerical differ- ence between the new integer and the one numerically closest in-we att teger of the ola structure. The "distance" between S, and 3, would then be (1,0). It should be noted that the " stance” defined in 3.201.316 has one component, while that defined in [Link].1.b has two. These two kinds of "distance" will never be compared to one enobh: For a "distance" that has two components, it may be convenier: to use some single combination of the components for a priori U de- termination, say a weighting coefficient for one of them. It should be noted that "distance" is being used as the in— verse of the intuitive notion of "closeness," and isn't meant to have necessarily any properties that a "metric" has —- e.g., t "aistances" need not satisfy the triengle inequality. 3.2.1.3e1ec New structures may be created from old by the muivi-— plication of an ordered set of n structures by a single structure in the normal manner of multiplication of an n-tuple by a structure. Some examples are: 1/2 | 3) 1 om: (—.a)- F “8 Tad Gi] «(Gm) - EE] 3.2ele3eled Creation of new structures from old by rotations ané/cr reflections. Some examples: Al by reflection. = a by rotations. 1 3.201.342 Creation of new n-tuples from old n-tuples and n-grams.~18- 3:2.13-22 Juxteposition of n-tuples or n-grams or p n-grems with n-tuples, or n-grams or p n-grams, to obtain new n-tuples. For example: ~1 and a combine to form the n-tuple (+ oe By o 1 Y ‘ combines with ( a) to form i e we 3,[Link].b Permutation, omission, repetition. Binary permutations are the simplest, and therefore result in the least expected decrement in U. For example (2, 8, 8,5) > (¢,5,2, 8). Any more complex permutation is expressable as the result of one or more binary permutations, but the a priori U decreases with each extra binary permutation that is needed. The simplest omission consists of omitting one component? owe (0, BY 25) > (4,5,h)+ Omissions of greater than one component can be made by repeated application of a single compo~ nent omission operator. The simplest kind of repetition is the single repetition: ecg. (a, 8,8, 5) > (4, Bs B,345)- More complex repetitions may be oxpressed as the result of several simple repetitions. Eee (a, Bo) > (a, By Bo) > (a, B, B, 82) or (a, 8a) —> (0, %, 8, &) > (a, a, 8, 8S) 3.221.343 Creation of new n-grams and p n-grams through milti- plication of an n-tuple by @ structure.~19- 3.2ele30 Creation of a p n-gram from an n-gram or p n-gram by addition of an interrogation square. Some examples are: ~lol _,~101 gp =Gio _, fio o1o ofi\o 110 11 : 3e2ele305 Creation of a p n-gram op an n-gram by omission of an Interrogation square. This is the inverse process of h. d Some examples are? ~101 ~101 Ee hed 10 ojo 7 010 110 ~*~ iio’ 3e2ele306 Some inversion techniques. 3.2ele3e608 P n-grams or n-grams "divided" by structures to yield n-tuples. If 8, is a structure, an n-tuple, Nan n-gram, ei ‘0 He 7 80 Me A i Then we may write Ny as @ definition of 0 areas i 28,6 ; B 7 “e a ’ Por a given 8 and x, , ‘there will usually not exist @ ; ‘0 ae value of XN, +3. If one value of Ny = S, doee exist, usually 0 o : there will be soveral values of N, for which N,. $8, is the : ‘o O | same, For example, \a rf =z \ t fa. © \* Me i, ¢) | o I? ° Let Ney = a,l ret oN, = SD @ wThen Ng. Also Nes > [Link].b P n-grams or n-grams divided by n-tuples to yield structures. As in (a), if Ng, = Sy x Nty then Ne, # Nt, 2S, by definition. Usually, if Ng, ¢ Nt, ‘does exist (and it usually will not) ‘0 then it will have several values. For instance, as in (a): Os us ef = (8) (rT2] at i 71 oe GL. [Link]-6.¢ Netuple "divided" by an n-tuple to yield a new n=ty If Nt, = (a, 6) 4s an n-tuple and (a) and (B) are both n-tuples, then we define (a) = (8B) (division on the left o 7 (8) = (@) (division on the right) Some examples? (Gee) Let my = (e907 ° Let Ney = [9.7 R L 2 aera eet Then Wt, - Nt, = (3) also Nt,In the present case Nt, > Nt meaningless, Usually two n-tuples cannot be divided into one another in this way. When the n-tuple obtained as a result of this division is a "single" or "mono-tuple," either a p n-gram or n-gram may be obtained through this division process. [Link] Another process that is going on at all times is the ss- signment of U's to all ngms, ntps, strs and pngms, These U's =usz ve continually reevaluated, as new problems and data are given to the machine. A partial description of this process of U evaluation was given in section 3.1.13. A more detailed description will be given here. Hach method of creating pngms will have associated with iv s method of getting the a priori U's associated with these pngms —— also a weight to be given to this a priori U, when combining it with empirical data. For en example of this weight determination, suppose that Us, ts the Uof str S,, yy the Uof ntp Ny. Then the a prior: U of the pngn S$, x Ny will be 205, 4)» where f is @ function that will be optimized for the operation of multiplying stre by ntps. At first, we will let f = AUs +B Uy and optimize A and 4 j B. As the machine gets more data, it will be possible to use nore coefficients -~ say 2 £ = AU, + BUy + CU" + DU, YU, A By N Sy SN,22 For this discussion we will assume t AU, +BUy - 35 Ny Let U,, be the empirically observed U of the pngm 8 x Ny. n a i Then otk a = (23 - (205, + 2%,,)) a , Viewed as a prediction is the mean square error of AU, + BU, 4 of U5 The weight to be assigned to AU, + BUy as an a priori pre- 4 More explicitly, if 7 is the total number of interrogation squares that have appeared on all q elements up to the present time, and ©,, is the total number of cases of the pngm S, x Nj, i then the value given to U,; is It will be noted that, as 7 —p02, U,,—> i as desired. Also, for 7 = 0. j is, indeed, the a priori value of U,, - The above discussion is not an exact one, and was given to illustrate the use of weights in the application of a priori U's to the computation of true U's. A better method of computation is available, It will not be given here, however.“23+ Another aspect of U computation is illustrated by the creation of new structures from old by chosing structures that are a short "distance" from the old ones. If Ug is one of the U's of struc~ 4 ture S,, end S; is @ structure at a distance a,, from S,, then the corresponding @ priori U to be associated with 8, is ky jUs, » where & is a decroasing function of a,j. We may write 4 naa yy = 1), then find an a such that this a priori U is as good an approximation as possible to the empirically obtained U's — averaged over all pairs of neighboring structures upon which one has data. 3.20105 Woe will now describe the behavior of a simplified machine that has pngms, ngms, strs and ntps, but has only five ways to pro= duce new ones from old. Let these methods be written (1) str, ntp —> pngm (2) nem, nay —> ntp (3) str, ngm —> ntp (kh) str —> str (5) ngm —> png Let us further suppose that we only have binary ntps end stra; that the product of a str and ntp always exists and is single valued; that the fourth operation is single valued —- producing a single str from another single str. See 3.2.1. 3.3. Operation (1) may be normal multiplication of an ntp by a str to obtain a pngem, Operation (2) may be simple juxtaposition of two ngms to ob= tain an npt. See [Link].2.8.~2h,- Operation (3) may be division of an ngm by a str to obtain en ntp. See 3.261.368, Operation () may be creation of a new str by taking one that is some fixed distance (say one unit) from the old one, See 3.2s1.3.1.a- Operation (5) may be the creation of a new pngm by adding an interrogation square to an ngm. Ses [Link]. For the first operation 2 non (2 (0 Us + By); ) ~ rts, * Bae weasa @k BS 7 (ats, * Pale) is the U of the 1° str and is to be determined. 4 Uyz, 18 the Uof the j°" ntp and is to be determined. Ay a By’ are constant coefficients and are to be deternines. P is the number of interrogation squares that have occurred up to the present time. 8, is the 1° str. Nty is the 3° ntp. U,; is the U of the png that 4s formd by S, x Nty. ©, 18 the munber of cases of the pngn thet ts formed by 3, x Nty, providing this pngm is consistent. Obhor- wise C,, = 0. J m is the number of strs in the memory. n is the mmber of ntps in the memory. 6? is the mean sovare deviation of Uj; from the a priori U, which is Ans, + Pie, :-28~ A, n) are all to ve By Us, (Eades Typ Ge be adjusted, so that @* is minimal. The value of U,, is taken to be aj 302016502 ( +S, 7 reo? is small, then ar ang we may write ~ Aids, * Batve Pade coe A Yay (M5, + 218m) * Sa pues i Wyte After we have found optimum values of A,, By and the U, 's and a Uyp.'8. We may proceed to the second and third operations. [Link] pet \ [fy +BY -4, 2 > 2 ane, * Po be, Hits 5 5 ‘Je + > = [b, + B3tye,) ~ ea] Ay, Boy Ag Bz are constants to be determined, Bs 4 Ng, is the 2? nem, Une, is the Uof Ng,- is the Uof 8, and has already been fixed.-26— vy io the total number of ngms in the memory. Nts is the U of the ntp (Ng,, Ney). Uy, 18 the U of the ntp that is formed by "dividing" Jey 4 by the str S,. B is defined by the equation, It is the total error in vhe a priori estimates of U. We are then to determine A,, By, Ay, By and all of the Vy, ‘gs so that E is minimized. By For the fourth operation, 3.262.501, n 2 = Ose - 05,) Sy is the 4°? str. 2 Ae the str that results from the application of the fourt: operation upon S,. Ugo is the Uot sf. i K is a constant to be adjusted. B, is defined by the equation and is the total error in the a priori estimates of U. We must adjust K so that E, is minimal. n A solution is Tyo, 92010565 Ke 2 v 2 "8 [Link] Let us review the operation of this simplified machine. There are essentially three tasks that the machine must perform. First of all, it must make predictions. In order to do this, it-27- must create new pngms, ngms, strs and ntps from old ones. It must also reevaluate and keep up to date the U values of all old and new pngms, ngms, strs and ntps. Expressed briefly, whon the machine is given an element, it , places this element in its array memory and waits for further in~ puts. When it is given a q element, it places the q element in its array memory, then updates the consistency of all pngms affected by this q element and recent: elements, It also updetes U's of elt pngms, ngms, strs and ntps affected. It then scans through its pngm memory to see if it can make the required prediction. If it can, it does, and stops. If it can't, it makes new pngms that fit the q element, tests them for gon! conoy and updates all U's and consistencies. It repeats this subroutine of forming now pngms thet fit, testing them, end updet- ing, until it finds a relevant pngm that is consistent —- at which time it makes a prediction and stops. In greater detail, tho rules of operation are: 1. When she machine is given a new element, it stores this element in its "array memory" end waits for the next input. 2. When the machine is given a new q element, it first stores the q element in its "array memory." Next, it scans through the array memory, from the present @ element, back to, but not includ~ ing, the previous q element. It notes which pngms have become in~ consistent because of the elements and q element scanned. Tt thea searches through its pngm memory, to see if it has any consistent pngns that apply to the interrogation square of interest. If it has, it makes the appropriate prediction, and re~ coloulatos the G,,!s that have been affected by the new-found in-28+ consistencies and/or new pngm cases If there is any ambiguity, it first goes to mule 5 to resolve it, then proceeds to rule 3 - If there is no ambiguity, it goes to rule 3 directly. 3ea If the G,,'s have been changed, the U's of pngms, ntps « and strs are recomputed in accord with equations [Link].1 and 3e2.1.5-2, and the machine goes to rule 3.b - 3.b Tho machine recomputed the U's of ngms, in accord with equation [Link].3, then goes to rule 3.¢ « re K, of equation 3-2.1.5-4, is reoptimized end the machine goes to rule 3d - 3.4 If a prediction has been made for the present q element, the machine stops and waits for the next input. If not, it goes to mule k. The machine constructs new pngms of high a priori U, that apply to the interrogation square in quest on, uding the methods of section [Link]. It devises several now appropriate pngms that 4t does not have in its pngm momory and places them in that memory. Tt then scans through the entire array memory to see 1f any of the new pngms are consistent. If any of them are, it makes the appro~ priate prediction. (In case of ambiguity, it refers to rule 5.) It thon recalculates the 0,,'s that have been affected by thé new- found inconsistencies and/or new pngm cases and goes to rule 3, Independently of whether or not @ prediction has been made, S. If the predictions of two pngms conflict, teke the pre~ diction of the one with most cases. If the case numbers are equal, bake the one with the greatest count. If the count numbers are aqual, no prediction should be made. If the case numbers aro equal~29- and greater than zero, the prediction accuracy may be expected to be poor. 3.2.2 Initial conditions. In the previous sections we have outlined the "steedy state", operation of the machine. The processes described assumes that the machine already has a stock of pnems, ngms, ntps and atrs, along with their U's, and any other needed parameters. To stert off =he machine, we will have to give it some elementary abstractions to puild upon, A set that is probably adequate to start with is: (1) Bech digit is made an ngm with a priori U of ye a bem ing the number of different digits. Initial values of W must also be assigned. (2) The str , is assigned an initial U of, say, .5- jie will also have to assign some initial values to the various combination parameters. For instance, the "K" of equation 3e26105eL, as well as Ay, Ap, Az, By» Boy By that occur in equations 3.201.542 and 3.261.543, may pe given the value .5. In a sim way we may assign almost arbitrary initial values to various parameters that occur, exercising no great degree of care. These initial values become unimportant after the machine has been given several elements and q elements, since the values ere soon modi— fied so as to optimize them with respect to this empirical date. l, Bxamples of machine operation. Having described in a little detail the operation of the na~ chine, we will now analyse, in e general way, its response to & particular training sequence of elements end q elements.~30- The first part of the training sequence will consist of sie- ments of the general form: esOll =l1loo1 =0 zaso oo Stereo soll, lion, oO, ssqgio0oo, Liojl.. They will be presented anywhere in the 7x 10 array. The digits following the "=" are a random sequence of O's, 1's and spaces, with the row below having the same sequence of O's, 1's and spaces, as that following the "=" digit, except for J's. 4.1 Twenty sample problems. 1. Suppose that the first example presented to the machine = 293. Following rule (1) of section [Link], it the elenent stores this element in its array memory and waits for the next inp. 2, Next, let us present ~ 3H . By rule (2) of 3.2616, t ° again stores this in its array memory. Following the rest of zule 2, we note that the machine has, initially, no pngms at all only the ngms 0, 1, = and the str (i] . There are not yet any Oys's to change, The machine goos to 3. , does nothing, then skips to 3.4 , does nothing again, end goes to rule k. Rule l is most critical, since it is at this point that new pngms are created. From the ngos 0, 1, =, the machine creates the pngns [l, by operation 5 of [Link]. For simplicity, we may aseign a U attenuation factor of unity to the process of op— eration 5 . To illustrate the operation of the instructions, we will as- sume that we stop with the set of pngms we have just made, end scen through the array memory to test consistency. If (|, foreye example, were consistent, this would mean that every square of every array presented to the machine (other than interrogation squares) was occupied by 0. Clearly neithor (),,[H), nor [E] are consistent, so the machine makes no prediction, In any c&se,, we go back to step 3. We do have some new G's (case numbers of pngms), since three new pngms have been created, Rules 3.a, b, and c do not, however, require that anything be done, since none of the transformation and combination rules that result in equa- pions 362.165+2, 36201253, and [Link]-l have yet been made use of. Since no prediction has been made yet, we go from 3.d to step l again and devise some new pngms. We may use the combination rules of [Link] in a rather sys~ tematic manner to create new pngms, ngms, strs and ntps. Operation 1 isn't of much help yet. The only ntps we have are (0), (2), (=), ([9), (0), (E)). The only str we have is 1, which leaves all of the ntps essentially invariant. It creates no new pngns or nems, Operation 2 can create the set of ntps that-is the Car~ tesian product of the set of all ntps with itself. We obtain (0,0), (0,1), (=, (1), (0, TEN), ete. -- 36 ntps in all. Operation 3. Again for lack of a useful str, we can do nothing that obtains anything new. Operation obtains some new, useful strs, From obtain [A]. ZT], 211 of which are within J2 or Li). : We can go a slightly greater distance and obtain Operation 5 yields nothing new, since we have no new ngms yet. and6 7 et With these new strs, we can start through the list of opera~ tions again and obtain pngms, Operation (1) now yields a very large set of pngms and ngms of reasonably lerge a priori U. Some examples: : oa fax &, tea st z u a x(ELU= gy Since our q element is “0G, oniy the pngms 0 ete., are relevant. Of the rest of the operations, only (5) yields pngms, but, in trying it out on the ngms just generated, we find that we obtain no new pngms, We have enough pngms to try again for s consistent one to cover the 4 element of interest. Following the machine's instructions, we scan through the ar~ ray memory to find if any of the relevant pngms are consistent. The only consistent ones are . We thon make 1? the prediction 1 for the q element and go on to step 3 again. 1, For step 3.a wo observe that there are now many new 0, y's. AL of thom, however, are zero, except those of ‘FI, ° A few, like py and 9%, are consistent, but they have no cases yet. Most of the G, j's are zero because they are inconsistent. Let us examine the methods by which our three pngms wero created,Through equation [Link].1 the U values of i? E- hac] ae {7 TT), ED. ae gE ©, (Dv, a), an, (0,1), (G).0), (0,1), (1,0) will increase, while the U's of all other strs and ntps that were tried will decrease. More ac— curate values of A, end B, can now be calculated. Equation [Link].2 will now give the new values of U of ‘jy, and as well as those of any other pngms that have os, ne beon tried. For step 3.b we compute the U's of the ngms that wore used, through equation [Link].3. Also, more accurate values of A5, Bo, A, By con mow be calculated.aie For step 3.c we reoptimize the value of K, in accord with equation [Link]. The machine then stops and waits for the next input. 3. Suppose the next input is ~ Smt 2. the machine goes through the same routine as before. The only consistent pdigms that can be devised ere ° mo o Since the predictions given by them conflict, we go to rule 5 , which tells us to compare their case numbers. They are both zero. Next we compare their counts. They are both zero, so we make no prediction, Tt should be noted that 0 [i] and A, which caused aiffi- culty during the last example, are no longer consistent. 4. ‘The next example is =00110 ooMio. We note that the pngm a which caused difficulty during the previous example, 1s now inconsistent. The only consistent pdign’ is Bb and so our prediction is 1. 3. The next example is =l1lool Qoo21. The only consistent pdign is a and so our prediction is 1. The next set of examples will teach a new operation to the machine. 6. ~10 o1 1. ~oo1 110~35- 8. ~o101 1ol1o ~1l1o ool 10. ~Oll 100 When the machine is presented with example 10, it soon finds that there are no pdigms that are consistent for examples 1 through 10. In particular, all of the pdigms that were of high U for ex— amples 1 through 5 are now inconsistent. As a result, all of the U's of ngms, strs an@ nbps that wore a result of these pdigms be~ ing useful, are reduced considerably. The machine starts again from scratch, Since all pdigms are inconsistent, it must try ptrigms next. ‘Tho only consistent ptrigm that is relevant is ~@ act The resultant prediction is therefore zero. The ptrigm of Interest wes derived in the following manner: ma «(9 a8) t fa 0 ~fj. ~o aed @ : with [7] attached, and = (> {)- = (S-)- L~36- By this process we see that G4, all increase in U. Also 4}, Fy (0,1), (1,0), which are the strs and ntps by which 9 was formed, also increase in U. It should be noted thet in normal machine operation the order of decreasing a priori U is not necessarily monograms, digrams, trigrams, ete. It is only when there are no lower order ngms that have been found to be useful, that this is true, For example, if the digram 2 end the monogram 1 were of equal U, then multiplying them both by the str [7] a respectively. These two ngms would have equal a priori U. In the would yield the ngms and 11 present cage, the machine is young and inexperienced and it has no digrams of high U, so all ngm and pngms must be built up rather arduously from the basic digits. It is this condition that ex~ plains why the a priori U of an ngm is, at the present time, a decreasing function of n. Another important point that should be noticed is the method that has been used to obtain pngms to fit a given q element. The method consists of applying a set of combination and transforma— tion rules to a set of pngms, ngms, ntps and strs to obtain a new set of pngms, roughly in order of decreasing a priori U. Usually a large number of pngms are obtained, and from this large set the machine selects out those thet apply to the q element of interest. This procedure is, then, an exhaustive search, and as such, is not particularly efficient.-37- ‘The problem of obtaining a suitable pngm is at once a "well defined problem" of the first and second kinds. We have a set of operations, We may take any of this set and put them in any or~ der. We thon have a definite criterion to decide whether the re~ sult (if any) of these operations is a pngm that fits the q ele~ ment. The definiteness of this criterion makes it a problem of ‘the first kind, If we have two pngms that fit the q element, wo can compare their a priori U's to determine which is better. For this reason we have a problem of the second kind — since we want to find a pngm of high U. ll. For this example, let us go back to the "=" operation and see how the machine behaves with =1o011 OGoii. As before, there are no consistent pdigms. The only consistent ptrign is “+ ané so the prediction is 1. I whe stre (L[2\ ana are used again, since eu Ey) tla) x (=, Ro a ¢ @ Also, tho str 1 is useful, since + = BR x (1). a 1 12, The next example is ~1Do1 o1lio . There are no consistent, compact ptrigms, so the machine tries now strs, The str [Z]_2) has been useful, so neighboring strs are tried. The str [E]_| 2] is close and proves useful.(Notation note: The symbol "4" in a pngm indicates that this pngm does not concern itself with the digit that appears in the ' square occupied by "@". The symbol is used as a spacing device.) Since (+ a) has already proved useful, the pngm that has Hit been constructed is of high a priori U. The prediction is 0. 13. The next example is 1001 1ffo1 . ° - Ble. oO i (49) SE Gg) -ao . =4° wth (] added. o The ntp (-, . ) is found to be of very high U, since there o are many cases of its use. Bget (-3) -ma= (8) ana 7 AO iy. The next example is ! ~Qioo OO ta: The ptrigm is used. The ntps (-. *) and (3) increase , ° ° in U.-39- 15. The next example is ~oo1l 21100. It is possible for the machine to create the pngm ora ill a: (~13) since [L] | [2] is close to [LT [2] , but the pngms {a and ie have higher a priori U since they are easily constructed from high U digms, and stra Hoe ge 10 3) x($, 3) and 33 =-E x(3,3) = a] =(3) - In any case, the prediction is 0. 16, The next example is ~oo1ll Pieter 11 11a 4 4 The prens Gp oF G/G) are Used, and so the prediction is 0. 17. The next example introduces the machine to a new operation: @iio0o0e. o1100 11iifil. The p tetragrams te ana 7 Poth fit the q element, but iD is inconsistent, so the prediction is 1. 18. The next exemple is @10011 oo1ll1o0 roipji.~ho- There are no compact p tetragrams that fit. The p betragrams of highest a priori U, that fit, are 1 a 1 L 1 4 1 oe 1 1 1 1 1, @., 99@, 0s, 19sH, 1460- In case of conflict, we go to rule $. None of the above p tetra— grams have any cases, but the first two each have counts of ons, 80 they determine the prediction, which is 1. 19. This example is @i1oir o1o02l 11igi.- The consistent p tetragms of highest count are Be 1 0 and » so the prediction is 1, yg 1 20. ‘The last detailed example is @i0010 1Lid01 1 ent The consistent p tetragrams of highest count are + ao ° ° The prediction is 1. Further examples would involve learning operations of the @i ° 00 ° 190 1 o. type ° Pe For these examples, p hexagrams of the types on 19 Wa end would probably be discovered, ore L 0 @an- If, however, a sufficiently large number of examples of @® and @ are given, the machine mst occasionally use pngms of the type + gq oO a since the p hexagrams would be inapplicable. A case of such ihapplicability is + o1l rio 110 1. 1. since the p hexagram 10 4s not consistent, nor is 10 - 10 iff After meny examples of @ and @, we may present the machine with ordinary arithmetic addition. Some examples are + 11010 + o11l01 O11L01 ona lo1io 1 10000 1 11000 2 00111 2 00011. the first two lines are the numbers to be added, The fourth line is their sum, and the third line contains the "carries." This particular method of presenting addition leads to pngns 1 a of the type ae and 1 A vory interesting problem for the machine would be to present it with addition problems without "carry" lines, Some examples are: + 11010 olL1lOl or O11014#11010=10012 1 002111ye- This particular problem has not yet been investigated eb any length. I 1s not certain whether the machine would learn adai- tion in this form, using the present methods of creating new prams; or whether new methods are nesded. 4.2 Discussion of machine response to training sequence, Let us examine the response of the machine to the examples. tn general, the machine always tries to make predictions using the simplest possible compact pngms. In example 15 we would 1ike the machine to learn the connec~ tion between the symbol "~" and the dign 3, but the mechine chooses a simpler method of prediction. This method is again used tm example 16. In examples 18 and 19, ‘the connection between the symbol @ and the ngms of interest is not made because there are nore compact, consistent pngms evailable. In example 20, the con~ nection between @ and the pngm 1 is made, but the resultant i pngm is only one of several that will serve equally well. In general, the machine will not use a particular pngm for prediction unless it is the simplest methed available. Tt has, of course, ite own idea as to What the word "simplest" means. oe eventually, the machine is given problens in which it is necessery no to recognize the logical connection between, say "~" and vie tee will do eos Bub until then £t will continue to use "simpler" pre~ @iction methods. 5. Program for future work. 5.1 First of all, several new definitions will be introduced. They are: (1) Pngm set: a set of unordered pnems.-y3- An example might be: 10 1. 00 1g, i, cf, (2) Nga set: an unordered set of ngms. An example might be: 10 ea 00 ol Sle eeteaetes Ia eeeeeeee vJe( yuan (eee Jer Waleed (3) Ntp set: a set of ntps. An example might be: (u) str set: a set of stra. An example might bet Piz, Gla. (5) Perhaps most important of all is the redefinition of the ntp, so that a component of enntp may be a pngm, pngm set, ngm, ngm set, str, str set, another ntp, or an ntp set. This latter definition makes the language of the machine able to express almost anything. It is particularly useful in express— ing mathematical ideas. We may, for example, define sets of ob- jects, sets of sets of objects, sets of sets of sets of objects, etc. The integer, r, may be defined as the set of all sets of > objects -- the set of all r-tuples. Tho concept "one greater than” may bo defined as the set of all pairs of sets, such that the first set is the sot of all r-tuples; the second set, the set of all ‘ rel = tuples. The concept "integer" may be defined as the set of all sets that represent integers.aah 5.2 Some additional combination methods will be used. An important one is the idea of a "function." It combines two ntp sets to pro~ duce anew ntp set. If (0,,8,;) and (B 5154) [1 = 1,.0.,n], [j =1,...,m] are two ntp sets, then we may define a new ntp set (44 BG) in which all i,j pairs are taken for which B, = %- Also, Boolean sums and products of sets can be used to form new setse 5.3 Another important development is the modification of the present machine, so that it will work problems in which the correct enswer is not a single digit, but a probability distribution over several digits. Aside from being able to work probleme that the present machine cannot work, it will have the advantages of (1) Being independent of occasional errors in the information given to it, The presently described machine can have much of its prediction ability destroyed by a single error in the input date, (2) Such a machine is readily adaptable to modifying its own methods of prediction, since the efficacy of a new method of pre— diction is a probablistic questions S.l, Some of the problems that will be investigated ares (1) subtraction, (2) Omission of “carry” line for both addition and subtraction. (3) Multiplicetion, ~ () Division. (5) Change to "linear" notation, e.g. ° lo + 1012211. (6) Gombining operations by use of parenthesis.-45- (7) Solution of algebraic equations. (8) Interpolation, extrapolation of functions. (9) Differentiation, Integration. (10) Literal solution of differential equations. (11) Theorem proving. (12) Translation of English into logically tractable form. (13) Translation of logically tractable notation into English. 5.3 A possible early application of the present work ia to devise proper training sequences for children, At the present time, there is little conscious recognition of the sizes of the various "log- teal jumps" thet are necessary in learning some new material. Analysis of machine learning mekes all of this very explicit and clarifies the problem in an important way. 6. An evaluation of this machine investigation as a study tool. Using the set of rather simple abstraction-creating devices described in [Link], the machine is able to learn simple arith~ metic operation up to addition and subtraction. With the addi~ tional aid of the new definitions of section 5.1 and the new ab— straction-creating devices of section 5.2, it is expected that the machine language will be powerful enough to express any problem and any heuristic device. The advantages of this approach to the artificial intelligence problem are: 1, The operation of the device is fairly simple, in the sense that it Reeds no special apparatus to deal with important problems of great difficulty. This contrasts strongly with special machines