Moore designed his pinball machine to complete the analogy to the Turing machine. The starting position of the pinball represents the data on the tape being fed into the Turing machine. Crucially (and unrealistically), the player must be able to adjust the ball’s starting location with infinite precision, meaning that specifying the ball’s location requires a number with an endless procession of numerals after the decimal point. Only in such a number could Moore encode the data of an infinitely long Turing tape.
Then the arrangement of bumpers steers the ball to new positions in a way that corresponds to reading and writing on some Turing machine’s tape. Certain curved bumpers shift the tape one way, making the data stored in distant decimal places more significant in a way reminiscent of chaotic systems, while oppositely curved bumpers do the reverse. The ball’s exit from the bottom of the box marks the end of the computation, with the final location as the result.
Moore equipped his pinball machine setup with the flexibility of a computer—one arrangement of bumpers might calculate the first thousand digits of pi, and another might compute the best next move in a game of chess. But in doing so, he also infused it with an attribute that we might not typically associate with computers: unpredictability.
Some algorithms stop, outputting a result. But others run forever. (Consider a program tasked with printing the final digit of pi.) Is there a procedure, Turing asked, that can examine any program and determine whether it will stop? This question became known as the halting problem.
Turing showed that no such procedure exists by considering what it would mean if it did. If one machine could predict the behavior of another, you could easily modify the first machine—the one that predicts behavior—to run forever when the other machine halts. And vice versa: It halts when the other machine runs forever. Then—and here’s the mind-bending part—Turing imagined feeding a description of this tweaked prediction machine into itself. If the machine stops, it also runs forever. And if it runs forever, it also stops. Since neither option could be, Turing concluded, the prediction machine itself must not exist.
(His finding was intimately related to a groundbreaking result from 1931, when the logician Kurt Gödel developed a similar way of feeding a self-referential paradox into a rigorous mathematical framework. Gödel proved that mathematical statements exist whose truth cannot be established.)
In short, Turing proved that solving the halting problem was impossible. The only general way to know if an algorithm stops is to run it for as long as you can. If it stops, you have your answer. But if it doesn’t, you’ll never know whether it truly runs forever, or whether it would have stopped if you’d just waited a bit longer.
“We know that there are these kinds of initial states that we cannot predict ahead of time what it’s going to do,” Wolpert said.
Since Moore had designed his box to mimic any Turing machine, it too could behave in unpredictable ways. The exit of the ball marks the end of a calculation, so the question of whether any particular arrangement of bumpers will trap the ball or steer it to the exit must also be undecidable. “Really, any question about the long-term dynamics of these more elaborate maps is undecidable,” Moore said.
