Turing's machine (MT) is a computational model who realizes a reading / writing of an automatic way on an entry called tape, generating an exit in this one itself.Is this model formed by an alphabet of entry and one of exit, a special called white symbol (normally b? Or 0), a set of finite conditions and a set of transitions between the above mentioned conditions. His functioning is based on a function of transition, which receives an initial condition and a chain of characters (the tape, which can be infinite) belonging to the alphabet of Entry. The machine is reading a cell of the tape in every step, erasing the symbol in the one that is positioned his compress and writing a new symbol belonging to the alphabet of exit, then to displace the compress to the left side or to the right (only a cell simultaneously). This repeats itself as be indicated in the function of transition, finally to stop in a final condition or of acceptance, representing this way the exit.
History
Alan Turing introduced the concept of Turing's machine in the work On computable numbers, with an application to the Entscheidungsproblem published by the Mathematical Company of London in 1936, in which the question raised by David Hilbert was studied on if the mathematics are decidibles, that is to say, if there is a definite method that could be applied to any mathematical judgment and that he says to us if this judgment is true or not. Turing there designed a formal model of computer, Turing's machine, and demonstrated that there existed problems that a machine could not solve.
