Turing Machine
Alan Turing
Turing machine is a primitive abstract computer. It was invented by a mathematician Alan Turing in an attempt to find out whether all of mathematics could be reduced to mechanical computation. He set out to devise the simplest possible machine that could perform computation. He came up with a machine that was relatively simple device and yet could perform all the mathematical operations. Turing believed that the machine could do anything that a human brain can, including having consciousness.
Turing Machine
The Turing machine consists of a tape, head, state register and a finite table. The tape consists of cells to hold symbols. The symbols can be finite in number or can be blank. Each Turing machine has its own finite set of symbols.The head is positioned over a cell on the tape. This tape head can read and write symbols. The tape head can also move back and forth to access the adjacent cells. Turing machine is always in one of finite states. The state register stores the state of the machine. Initially Turing machine is in the start state and it stops when it moves into one of the halt states. The finite table contains instructions.
Turning machine has become the reference design of computation. So a system that is able to perform the same operations as the Turing machine is called Turing complete. There is no hierarchy of power in computational systems. If a system is Turing complete then it can do anything we can define in terms of an algorithm.
Alonzo Church has postulated a thesis that states that there cannot be a more powerful computational system. Some might propose that human mind to be one. A register machine can simulate a Turing machine simulating a register machine. The concept is akin to writing a programming language in itself, which is quite possible. Running an interpreter in itself is a confusing experience. To fit the human mind within this framework would that if Church is correct that there is no more powerful computer than a Turing machine, a mind can theoretically be simulated.
Despite the absence of differences in computational power, there are substantial difference in what the system looks like. People familiar with computers who have not reflected on the topic often assume that the second one, the register machine, is the only possible computing device, since this is how modern computer systems are implemented.
Related Articles
One Comments to “Turing Machine”
[…] Turing machine is a powerful model proposed by Alan Turing in 1936. It is the best mathematical model for computability theory. It can do whatever a typical computer can do but it cannot solve some problems that are beyond the theoretical limits of computation. Decidability is a kind of computability theory that investigates power of algorithms to solve problems. It is also necessary to know the unsolvability of some problems. The unsolvable problems, once found, may be simplified or altered so that an algorithmic solution can be found. Reducibility is a primary method of proving that certain problems are computationally unsolvable. […]