![]() ![]() ![]() ![]() From this seminal result followed many other impossibility results. Turing showed that there does not exist a machine that detects whether or not another machine halts. It turns out a program to do this is an impossibility. Students often encounter the following problem: “My program has been running for a long time is it stuck?” This is called the Halting Problem, and students often wondered why we simply couldn’t detect infinite loops without actually getting stuck in them. In a previous life as a university professor I had to teach programming a few times. To understand what can be computed it is helpful to identify what cannot be computed. No number of additions or extensions to this machine could extend its computing capability. It took some time, but eventually it became clear to everyone that Turing was right: The Turing machine could indeed compute all that seemed computable. Nowadays we would recognize the set of instructions as the machine’s program. If it encounters the blank symbol at the end of the input, it goes to the state “did not find it” and halts. For example, if the machine needs to decide whether the tape contains the text string “TC” it can scan the tape in the forward direction while switching among the states “previous letter was T” and “previous letter was not C.” If while in state “previous letter was T” it reads a “C,” it goes to a state “found it” and halts. The instructions depend on the current “state” of the machine. The device reads an individual symbol on the tape and follows instructions on whether to change the symbol or leave it alone before moving to another symbol. The Turing machine writes onto the tape data that it needs to access later in the computation. The string also serves as the memory of the computer. Initially, the string of symbols on the tape corresponds to the input, containing the data for the problem to be solved. The strip of tape is analogous to today’s hard drives that store bits of data. Each box contains a symbol (such as A,C,T, G for the letters of genetic code) or a blank space. His hypothetical device is now known as a “Turing machine.” The centerpiece of the machine is a strip of tape, divided into individual boxes. It took the genius of Turing to show that a very simple machine could in fact compute all that is computable. ![]() It seemed overwhelmingly difficult to build such machines. Some prominent mathematicians proposed elaborate designs for universal computers that would operate by following very complicated mathematical rules. For example, 6 can be expressed as the product of 2 and 3, but 7 cannot be factored into smaller integers and is therefore a prime number. Another example of a computable problem, important to modern encryption, is whether or not bigger numbers can be expressed as the product of two smaller numbers. For example, we can compute a car’s most energy-efficient route to a destination, and (in principle) the most likely way in which a string of amino acids will fold into a three-dimensional protein. In Turing’s time, mathematicians debated whether it was possible to build a single, all-purpose machine that could solve all problems that are computable. ![]()
0 Comments
Leave a Reply. |