| |
Using the concept of the Turing machine, Alan Turing (1912 - 1954) investigated the theoretical limits of what computers could do—an amazing feat, considering the primitive state of computers at the time. The Turing machine, a simple model of the computer, provided one of the main ways in which the study of computability could be approached, and was perhaps the easiest to comprehend intuitively because the Turing machine concept was related to the concrete idea of the computer.
A Turing machine consists of a device that will carry out a program with an infinite strip of paper running through it. On this piece of paper are boxes, each of which is blank, or contains a 0 or a 1. The Turing machine can read the paper and write on it, putting 0 or 1 into a blank space or erasing a written figure. The Turing machine is programmed with instructions of the form ‘if you read the sequence 01001 then move six boxes to the right and erase the symbol in this box’. The Turing machine, like a computer, uses the binary number system, so only needs 0 and 1.
This is very close to the way a real computer works. The actual machine represents the Central Processing Unit of the computer, where the calculations are carried out, and the paper represents the memory store, where the memory locations are either blank (unused) or contain 0 or 1. However, the Turing machine is only a theoretical device, because it is impossible to build a computer which has an infinite memory capacity.
One of the most surprising results in computability is that the main approaches to discover what a computer can do all came up with the fact that the same functions are computable, whether based on concrete models of the computer like the Turing machine or on theoretical considerations of functions. SMcL |
|
