Chapter 3: The World of Simple Programs

Section 9: Register Machines

Halting [of register machines]

It is sometimes convenient to think of register machines as going into a special halt state if they try to execute instructions beyond the end of their program. (See page 1137.) The fraction of possible register machines that do this starting from initial condition {1, {0,0}} decreases steadily with program length n, reaching about 0.76 for n=8. The most common number of steps before halting is always n, while the maximum numbers of steps for n up to 8 is {1, 3, 5, 10, 16, 37, 215, 1280} where in the last case this is achieved by

{i[1], d[2, 7], d[2, 1], i[2], i[2], d[1, 4], i[1], d[2, 3]}

From Stephen Wolfram: A New Kind of Science [citation]