A machine that mutates its own program

In January 1958 Richard Friedberg of IBM described an attempt to teach a computer by changing its own instructions: a «Learner» replaces instructions at random in the program of a small machine, «Herman», and keeps those that more often go with success. The machine, with 64 one-bit data locations and 64 fourteen-bit instructions, was simulated on the IBM 704; the author himself calls the result «limited success».

The set-up. Herman's program acts on 64 data locations of one bit each (D0-D63) and 64 instruction locations of 14 bits; before each trial a «Teacher» places random bits in the input locations, after the run checks the relation between input and output bits and tells the Learner of a success or a failure; the Learner changes the program only after a failure, replacing instructions at random and keeping those more often associated with success. All of it is simulated on the IBM 704: 5,000 to 10,000 trials a minute. Problem 1: input D0, output D63, success when the output bit equals the input bit; a random program that finishes in time succeeds in about 50 % of trials. Experiment 1: in the first 60,000 trials (Stage 1) the frequency of success climbs from almost 0 to slightly less than a half as failures on time disappear; the next 90,000 (Stage 2) it fluctuates around 45 %; in the last 50,000 (Stage 3) Herman «hit the jackpot»: the program printed in the paper (Chart 1) is certain to succeed on Problem 1 whatever sequence of input bits it is given. The author does not decide whether Stage 2 was mere random wandering or gradually raised the chance of finding a perfect program. Experiment 2: the variant «Sherman» lacks two features of Herman (the instruction location used as a third address, and an indirect address) which were meant to let a performance record be kept for one instruction independently of the rest; in 800,000 trials it never succeeded in more than half of any 20,000 successive trials, whereas Herman found a perfect program in 150,000. Experiment 3: Experiment 1 was rerun nine times with different initial random numbers; in eight reruns a perfect program was found in 30,000-210,000 trials, about 100,000 on average, and in the ninth the time ran out after 220,000. Harder problems follow. Experiment 4: alternation of Problems 1 and 2 (output the complement of the input), each learned again in turn. Experiment 6: the low-order bit of the sum of two input bits (Problem 4) — a perfect program after 940,000 trials. Experiment 8: Problem 6, output 1 in odd trials and 0 in even ones, in fewer than 20,000; but the alternation of Problems 1 and 2 on successive trials — no perfect program in 2,130,000 trials (863,447 successes). Experiment 5: Problem 3, the two-bit sum of two input bits — no perfect program in 2,420,000 trials, 612,063 successes, which the author says is the expected average for a random program (leaving out time failures), a quarter; Experiment 7: the high-order bit of the sum (Problem 5) — none in 2,740,000, 1,367,321 successes, within the fluctuation of a half. Experiment 9: with every tenth trial ruled a failure, so that even a perfect program would have 90 %, in 1,380,000 trials Herman did not hold a success frequency above 45 % for more than about 50,000 trials at a time; the author calls this a serious deficiency in retaining instructions that are statistically advantageous but not infallibly successful. The paper's conclusion: the results, although fragmentary, show that in a practical number of trials a learning machine of this type can achieve enough success to be suitable for informative experimentation. What the record does not claim: the results of Part II (Friedberg, Dunham, North, 1959), which was not read; that the method beats random search (on the two-bit problem the author sees success at the random level); that this is the first program to change its own instructions; any link with Holland 1975; the tables and Chart 2 were not checked cell by cell. One source, the author's own paper: medium confidence.