The unfinished worksheet

Place a small binary calculation somewhere inside a rectangle of seventy cells. One row begins with an equals sign and contains a run of zeros and ones. The row beneath repeats the run. Now erase one lower digit and ask a machine to restore it. A child might say that the answer is obvious because the two rows are the same. The machine has not been given the word “same”, a loop, a coordinate rule or a program for copying. It has only completed examples, an unfinished example and a supply of operations for constructing candidate regularities.

This is the experimental world of Ray Solomonoff’s An Inductive Inference Machine. The report circulated during the Dartmouth workshop in August 1956 and appeared in the 1957 IRE Convention Record. Its setting is more concrete than the title can suggest. An element is a 7 by 10 array filled with symbols such as 0, 1, equals, complement and blank. A q-element, later annotated by Solomonoff as better called a problem, is such an array with one or more interrogation squares. The learner must choose the missing symbols.

The choice of a two-dimensional worksheet is load-bearing. A digit immediately below another can express copying. Two stacked digits beside a complement sign can express inversion. Three rows can express Boolean sum or product. A relation is therefore not only a sequence of values; it is a geometry. The machine has to discover which local shape predicts which cell, even when the whole calculation moves to a different location in the surrounding rectangle.

There is an immediate philosophical gain in the narrowness. “Learn mathematics” is too loose to test. “Restore this symbol after these examples” produces observable success, explicit mistakes and a traceable chain from stored evidence to prediction. It also reveals what the demonstration cannot establish. Solving this worksheet is not evidence that the machine possesses arithmetic concepts in every notation. The learner may exploit a compact local regularity that happens to work before it recognises the operator that a human teacher hoped it would learn.

A language of parts

Solomonoff’s basic unit is an n-gram, but the term does not mean the familiar run of adjacent characters used in later language models. Here it is any spatial configuration of n digits at integer coordinates. The cells need not form a line. A vertical pair, an L shape and two separated positions can all be n-grams. Each maps to every stored array in which that shape and those symbols occur. Its count is the total number of occurrences accumulated through time.

Mark one digit in the configuration as the predicted digit and the object becomes a prediction n-gram, abbreviated pngm in the report. Remove that marked digit, find the remaining configuration around an interrogation square, and the mark says what should occupy the square. The pattern “1 above predicted 1” states a vertical copying regularity. “equals and 0 above predicted 1” is another candidate, but it becomes useless if the stored arrays contain even one matching context with a different lower digit.

A case occurs when the context of a prediction n-gram appears; its prediction count records how often the whole pattern, including the claimed answer, appeared. The simplified deterministic machine calls a prediction n-gram consistent when no alternative digit has ever completed that context in the observations. Consistency is severe: one counterexample flips a candidate from permissible to unusable. Counts can arbitrate when different fitting consistent candidates predict different digits, but they do not rescue an inconsistent rule.

The machinery is more than an inventory of patterns. N-tuples are ordered collections of n-grams or prediction n-grams. Structures are integer-labelled coordinate templates. Multiplying a tuple by a structure chooses a digit from each tuple component and places it at every position carrying the corresponding structure label, together with the surrounding digits of its component pattern. Overlapping incompatible digits invalidate the construction. Compatible overlaps, Solomonoff later notes in annotation, ought to be allowed.

This peculiar multiplication is the report’s answer to a central question: how can parts of old solutions form a trial solution for a new problem? The tuple says which fragments are available. The structure says how their anchor points should be mutually oriented. Because both can acquire utility, a useful spatial relation can travel to new content, and useful content can be tried in new relations. Induction is therefore not a single curve fit. It is a search through a typed language of recombinations.

Five memory banks, not one undifferentiated past

The steady-state machine divides memory into five banks. One stores prediction n-grams with their counts, cases, posterior utility and the prior utility inherited from their construction. A second stores n-grams with counts and utility. A third stores tuples and their utility. A fourth stores structures and utility. The fifth, called array memory, retains every element and q-element presented to the machine.

The division matters because the learner needs two kinds of memory. Episodic storage answers factual questions: has this candidate’s context appeared, and did its predicted digit agree? Structural storage answers generative questions: which fragments and placements have been useful ingredients, so which nearby construction should be tried next? The same completed array can affect both. It directly verifies or refutes prediction n-grams, then indirectly changes the utility of the components from which those predictors were built.

A modern reader may be tempted to call the banks a database, a model and an optimiser. Those labels can help orientation, but they hide the report’s distinctive bet. It does not assume one fixed model family with adjustable numerical parameters. It grows representational objects and records their genealogies. A high-utility predictor can raise the estimated value of a tuple or structure that helped create it. Those components can then generate qualitatively different predictors. Learning changes both the scores and the stock of searchable ideas.

The candidate foundry

The simplified machine has three continuing jobs. It must make predictions, create new n-grams, prediction n-grams, tuples and structures, and keep utility values current. When a completed element arrives, it enters array memory. When a q-element arrives, the machine stores it, updates affected consistencies and utilities, then scans prediction n-gram memory for a rule that fits an interrogation square.

If a fitting consistent predictor exists, the machine uses it. If none exists, construction begins. The report’s simplified algebra lists five routes: multiply a structure by a tuple to obtain a prediction n-gram; join two n-grams into a tuple; divide an n-gram by a structure to recover a tuple; transform one structure into a nearby structure; and turn an n-gram into a prediction n-gram by marking one digit as the interrogation position. The report describes other transformations too, including rotations, reflections, adding points and inversion-like operations.

The report calls this an exhaustive and inefficient search: transformation sequences can produce a large candidate set, from which the machine selects patterns fitting the question. The enumeration is not neutral, however. Candidates are tried roughly in decreasing prior utility. The “prior” is local to this mechanism: it estimates usefulness before the new candidate has enough direct cases, using the utilities of its parents and the transformation that produced it. Empirical performance later revises that estimate. The machine can therefore spend scarce computation first on offspring of methods that worked before.

The loop has an attractive economy. It searches only after an actual question exposes a gap. Candidate generation is aimed at patterns that fit that question. It uses the stored past to test those candidates, rather than keeping every logically possible configuration alive in advance. Yet the economy is heuristic. The report does not provide a theorem that the search will find a predictor within a bounded time, or even that its chosen transformation language contains the intended arithmetic relation.

Utility turns success into a search order

Utility, written U, measures how effective an abstraction or prediction method has been. For a prediction n-gram, Solomonoff first suggests the average number of cases per unit time, or its logarithm, with inconsistent predictors assigned zero in the simplified machine. For tuples, structures and n-grams, the problem is harder: their value is indirect because they contribute to predictors whose later performance can be observed.

The report’s basic approximation decomposes the observed utility of a predictor built from structure S_i and tuple N_j into contributions associated with its parents. It seeks values that make a combination such as U(S_i) + U(N_j) approximate U_ij. The appendix prefers a multiplicative form because one excellent parent should not make every product excellent when paired with a useless partner. In logarithms, multiplication again becomes addition.

A transformed structure can inherit discounted utility from a successful neighbour. Solomonoff illustrates a factor decreasing exponentially with a chosen distance: a small geometric move from a useful pattern begins with more credit than a remote rearrangement. He is careful that this “distance” need not be a mathematical metric. It is a family of transformation-specific notions of closeness, and his later annotations openly question several proposed formulas.

Utility also gives the machine its own notion of simplicity. A young machine begins with isolated symbols and a primitive structure, so larger n-grams require more construction and tend to have lower prior utility. With experience, a large but frequently useful fragment can become a high-utility primitive for later work. Size alone therefore does not permanently define simplicity. A method is simple for this learner when its construction path uses parts and transformations that the learner has already found useful.

This point prevents a casual slide into the 1964 universal prior. The 1957 simplicity order is empirical, representational and path-dependent. It depends on initial objects, permitted transformations, chosen utility equations and the curriculum of examples. Later algorithmic probability assigns weights through descriptions on a universal machine. That is a different theory with a different object of analysis.

The curriculum teaches what the representation can notice

The report walks through twenty illustrative problems. Early examples train identity: the row below the equals sign copies the row above. Later examples introduce complement, then Boolean operations. As counterexamples invalidate compact patterns, the machine searches for larger contexts that include an operation symbol or multiple input rows. Pieces learned during the earlier tasks can accelerate construction during later ones.

Solomonoff repeatedly notes that the machine may choose a simpler predictor than the relation a teacher intends. In a Boolean-sum exercise, a local tetragram might predict the missing bit without connecting it to the operator symbol. If that compact rule is consistent, the machine has no reason to construct the more semantic relation. Only examples on which the local shortcut fails make the operator relevant. A training sequence is therefore not a neutral list of facts. It controls which distinctions become necessary and how large each “logical jump” must be.

The paper even proposes using machine training sequences to illuminate curricula for children. That speculation should be kept in scale. The simplified machine’s learning dynamics are not a model of child cognition validated by experiment. The defensible insight is methodological: when every intermediate representation and failed predictor is explicit, one can inspect the jumps demanded by a lesson. The same exercise may expose that a curriculum relies on an unstated invariant or assumes a concept before supplying examples that distinguish it.

Ordinary binary addition without a visible carry line becomes a decisive test. With carries written as a separate row, local patterns can predict output bits. Remove that row and a dependency can travel across columns. Solomonoff says the problem had not been investigated enough to know whether the existing pattern-construction methods would learn it. The honest uncertainty marks the difference between a promising representational programme and a demonstrated general learner.

Executable demonstration: the pattern foundry

The laboratory below implements a bounded analogue of one part of the report. It takes small rows of binary training pairs, constructs vertical prediction patterns with optional operator context, checks consistency, counts cases and ranks surviving candidates by a transparent utility score. It does not reproduce Solomonoff’s five-bank machine, tuple multiplication or the appendix’s utility integrals. Its purpose is to make the central fit, test, rank and reuse cycle inspectable.

Try identity only. The local rule “upper 1 predicts lower 1” survives, and adding the equals sign changes little. Then choose identity followed by complement and ask a complement question. Bare vertical copy or inversion rules encounter conflicting cases across operators. The operator-aware pattern survives because it distinguishes the two tasks. Finally choose the noisy identity set. Every deterministic candidate for the corrupted context can be contradicted, reproducing the brittleness Solomonoff identifies.

One error, many ruins

The current machine’s sharpest defect comes from its definition of consistency. A single erroneous digit can invalidate a good prediction n-gram. Its utility falls to zero, and the credit of parts used to construct it may fall too. The damage can therefore spread from one rule into the generative search order. Solomonoff says plainly that an occasional input error can destroy much of the machine’s prediction ability.

His proposed repair is to let answers be probability distributions rather than single digits and to train on statistical sequences. A predictor could then remain useful after an exception, while its probability reflects the observed record. This change would also support self-modification because comparing prediction methods is itself probabilistic. The proposal is consequential, but it sits in the programme for future work. The companion must not silently attribute that robust machine to the demonstrated deterministic model.

Another limit is combinatorial. Even small n-grams can be combined, shifted, reflected, rotated, expanded and divided in many ways. Utility is supposed to keep promising constructions near the front, but the report offers neither a completeness guarantee nor a resource bound. A low-utility component may be essential to a later solution. A high-utility family may generate a flood of plausible but irrelevant descendants. Heuristic search creates leverage by accepting the risk of missing useful ideas.

There is also underdetermination. Many prediction n-grams can be consistent with a finite array memory. The report resolves some conflicts by cases and counts, and more generally by prior utility. None of these operations proves that the selected pattern captures the intended rule outside the observed curriculum. Later learning theory would make this issue formal by specifying target classes, evidence protocols and convergence or probability criteria. Gold’s 1967 identification-in-the-limit results, for example, show how strongly learnability depends on the information stream and the class of languages.

These limits do not make the report trivial. They locate the research problem. A learner needs a language expressive enough to build useful abstractions, a credit system that makes good constructions reachable, and a curriculum that exposes misleading shortcuts. Improving any one can worsen the others: a richer language expands search; a sharper prior can bury novelty; more discriminating examples cost time and may contain noise.

1957 is not 1964 in miniature

Solomonoff is now best known for universal inductive inference, where computable generative descriptions contribute probability and shorter descriptions receive greater weight. Reading that mature theory backwards into this report is tempting because both projects concern prediction, probability and simplicity. It is historically and technically wrong.

The 1957 proposal searches a handcrafted language of spatial patterns. Its priors come from the empirical utilities of components, transformations and a chosen notion of structural distance. Its simplified prediction rule is deterministic and rejects any contradicted pattern. The report contains no universal Turing machine mixture, no weight of 2 to the negative program length, and no convergence theorem for universal prediction.

The connection is a research trajectory, not identity. This report asks how a machine might create new good ideas from old ones and makes training order and reusable abstraction explicit. In 1960 Solomonoff moved towards a general theory based on descriptions. The 1964 papers formalised induction as probability over symbol sequences and models. The later theory replaces this worksheet language with a far broader computability-based construction, while inheriting the ambition to make prior plausibility and prediction mathematically explicit.

Turing’s 1950 discussion of a child machine is a useful prerequisite. Turing suggests replacing the attempt to programme an adult mind with an initial system plus education, reward, punishment and experimentation. Solomonoff supplies one concrete answer to the follow-up question: what might the internal reusable units and variation machinery look like? The answer is not neural development or symbolic theorem proving. It is a memory of local patterns and transformations whose future priority depends on predictive success.

Gold’s later work supplies a complementary warning. Learning claims change with the presentation of evidence, the permitted hypothesis class and the criterion of eventual success. Solomonoff’s arrays provide both positive patterns and counterexamples to particular completions. A learner receiving only positive sentences in an arbitrary language-identification stream faces a different problem. The lesson is not that one theorem refutes the earlier machine; it is that “induction” names a family of protocols whose guarantees cannot be transferred without translation.

Memory studio

Questions that test understanding

Place in the canon

Church and Turing established limits and models of effective computation. Shannon made uncertainty and coding quantitative. Turing then proposed learning machines as a route to intelligent behaviour. Solomonoff’s 1957 report adds a missing operational layer: a learner needs a representational workshop in which useful parts of old solutions can be varied, recombined, tested and credited.

The next step in Solomonoff’s own line is a change of formal object, not a larger pattern workshop. Universal induction asks how all computable explanations of a sequence can contribute to prediction under a principled weighting. That move will reconnect to the algorithmic information papers already in this collection. Paper 0011 earns its place because it shows the earlier engineering problem in unusually explicit form: intelligence requires memories and answers as well as mechanisms for manufacturing candidate abstractions from experience.

For intelligence and agency research, the most durable question is allocation. Which remembered structures deserve computation now? The machine answers by combining current fit with inherited utility. That makes its agency modest but real in an operational sense: it selects among internally generated possibilities according to a history of consequences. Nothing in the report establishes consciousness, understanding or autonomous goals. It does show how past success can reorganise future search without a programmer specifying every later rule.