Moore designed his pinball machine to finish the analogy to the Turing machine. The beginning place of the pinball represents the information on the tape being fed into the Turing machine. Crucially (and unrealistically), the participant should have the ability to regulate the ball’s beginning location with infinite precision, which means that specifying the ball’s location requires a quantity with an infinite procession of numerals after the decimal level. Solely in such a quantity may Moore encode the information of an infinitely lengthy Turing tape.
Then the association of bumpers steers the ball to new positions in a means that corresponds to studying and writing on some Turing machine’s tape. Sure curved bumpers shift the tape a technique, making the information saved in distant decimal locations extra important in a means harking back to chaotic methods, whereas oppositely curved bumpers do the reverse. The ball’s exit from the underside of the field marks the top of the computation, with the ultimate location because the outcome.
Moore geared up his pinball machine setup with the flexibleness of a pc—one association of bumpers would possibly calculate the primary thousand digits of pi, and one other would possibly compute the very best subsequent transfer in a recreation of chess. However in doing so, he additionally infused it with an attribute that we would not usually affiliate with computer systems: unpredictability.
Some algorithms cease, outputting a outcome. However others run perpetually. (Think about a program tasked with printing the ultimate digit of pi.) Is there a process, Turing requested, that may study any program and decide whether or not it’s going to cease? This query grew to become often called the halting downside.
Turing confirmed that no such process exists by contemplating what it will imply if it did. If one machine may predict the conduct of one other, you would simply modify the primary machine—the one which predicts conduct—to run perpetually when the opposite machine halts. And vice versa: It halts when the opposite machine runs perpetually. Then—and right here’s the mind-bending half—Turing imagined feeding an outline of this tweaked prediction machine into itself. If the machine stops, it additionally runs perpetually. And if it runs perpetually, it additionally stops. Since neither choice may very well be, Turing concluded, the prediction machine itself should not exist.
(His discovering was intimately associated to a groundbreaking outcome from 1931, when the logician Kurt Gödel developed the same means of feeding a self-referential paradox right into a rigorous mathematical framework. Gödel proved that mathematical statements exist whose fact can’t be established.)
In brief, Turing proved that fixing the halting downside was inconceivable. The one common option to know if an algorithm stops is to run it for so long as you’ll be able to. If it stops, you have got your reply. But when it doesn’t, you’ll by no means know whether or not it really runs perpetually, or whether or not it will have stopped should you’d simply 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 mentioned.
Since Moore had designed his field to imitate any Turing machine, it too may behave in unpredictable methods. The exit of the ball marks the top of a calculation, so the query of whether or not any explicit association of bumpers will entice the ball or steer it to the exit should even be undecidable. “Really, any question about the long-term dynamics of these more elaborate maps is undecidable,” Moore mentioned.
