Alan Mathison Turing: the cradle of Computing
The computer revolution began effectively to be held in 1935, on a summer afternoon in England, when Alan Mathison Turing (1912-1954), a student of King’s College, Cambridge, during a course taught by mathematician Max Neumann, took note Entscheidungsproblem of Hilbert. Meanwhile, as was briefly mentioned in the previous item, a part of the mathematical community was seeking a new kind of logical calculus, which could, among other things, put in a sustained mathematical basis heuristic concept that is to carry out a calculation. The result of this research was fundamental to the development of mathematics: it was whether it is possible to have an efficient procedure to solve all the problems of a particular class that was well defined.
All these efforts eventually form the theoretical foundation of what came to be called “Computer Science.” The results of Gödel and Turing motivated decision problem first try to characterize exactly which functions are capable of being computed. In 1936, Turing was acclaimed as one of the greatest mathematicians of his time, when he foresee his colleagues that you can perform computational operations on the theory of numbers through a machine that has built the rules of a formal system. Turing defined a theoretical machine that has become a key concept within the Theory of Computation. He emphasized from the beginning that such mechanisms could be built, and its discovery is just opening a new perspective to the effort to formalize mathematics, and at the same time strongly marked the History of Computing. The genial perception of Turing was the replacement of the intuitive notion of an effective procedure for a formal idea, mathematics.
The result was the construction of a mathematical concept of algorithm notion, a notion that he modeled building on the steps that a human being is when performing a particular calculation or computation. It formalized the concept of algorithm.
The Turing Machine
One of the first models of the abstract machine was Turing machine. As Turing himself wrote: “Computing is written symbols on paper. Assume that the paper is a grid, the flatness can be ignored, and it is not essential. Suppose the number of symbols is finite. The computer behavior is determined by the symbols which he notes at one point, and his mental state at that time. Suppose there is a maximum number of symbols or squares that he can watch every moment. To observe more successive operations are required.
Let us assume a finite number of mental states. Let’s imagine that the actions taken by the computer will be divided into such elementary operations that are indivisible. Each action consists of changing the computer system and paper. The state of the system is given by the symbols on paper, the symbols observed by the computer and your mental state. Every operation, no more than a symbol is changed, and only the observed change. Besides changing symbols, operations must change the focus of observation, and it is reasonable that this change should be made for symbols located at a fixed distance of the above. Some of these operations involve mental state changes the computer and then determine what the next action. ”
Turing’s work was documented in On Computable Numbers with an application to the Entscheidungsproblem, published in 1936. He described in mathematically precise terms how powerful it can be an automatic formal system with very simple rules of operation. Turing determined that mental calculations consist of operations to transform numbers into a series of intermediate states progressing from one to another according to a fixed set of rules until an answer is found. Sometimes it is using paper and pencil, not to lose the status of our calculations.
The mathematics rules require stricter definitions than those described in metaphysical discussions about the states of the human mind, and he focused on the definition of these states so that they were clear and unambiguous, that such definitions could be used to command the machine operations. Turing began with a precise description of a formal system in the form of “instructions table” that specify the moves to be made for any possible configuration of states in the system. Then proved that the steps of a formal axiomatic system similar to logic and machine states which make the “movements” in an automatic formal system are equivalent to each other. These concepts are all underlying the current technology of digital computers, whose construction became possible a decade after the publication of the English mathematician.
An automatic formal system is a physical device that automatically handles the symbols of a formal system by its rules. The theoretical Turing machine establishes both an example of his theory of computation as evidence that certain types of computing machines could be built. Actually a Universal Turing Machine ‡ except for speed, which depends on the hardware, can emulate any current computer, from supercomputers to personal computers, with their complex structures, powerful computing capabilities, since no matter the time spent. He proved that for any formal system exists a Turing machine that can be programmed to emulate it. Or in other words: for any well-defined computational procedure, a Universal Turing Machine can simulate a mechanical process to perform such procedures.
From a theoretical point of view, the importance of Turing machine is the fact that it is a formal mathematical object.
Through it the first time, it gave a good definition of what it means to compute something. And this raises the question of what can be accurately computed with such mathematical device, subject outside the scope of this work and entering the field of computational complexity.
Would you like to read more about this topic? This book might interest you: Computer Science.