| |
A function is computable if there is a method by which a computer can be programmed to calculate the function. This is not a precise definition, and several attempts to sharpen it have led to definitions which have all been proved to be the same. One approach was to look at the functions themselves, and to ignore the computer completely; this approach gave the computable functions their other commonly used name, the recursively enumerable functions. Another definition was that devised by Alan Turing (1912 - 1954), the true pioneer in the field of theoretical computing. He came up with the notion of a Turing machine, a simple mathematical model of the insides of a computer. His definition of computable was simply that a Turing machine could find the value of the function in a time that could be proved to be finite. A computer programmer can be confident that any computer can calculate a computable function in a finite time, though he may not be able to know in advance how long the calculation will take (see complexity).
From the definition of recursively enumerable functions, it can be shown that there are countably many computable functions (in other words, that they can be arranged in an infinite list). This means that there are functions which are not computable. The fact that functions exist which are not computable puts limits on the abilities of computers, which has implications in the field of artificial intelligence if, as some think, non-computable functions are inherent to intelligent thought.
A third way of looking at computability is Church\'s thesis, named after its originator, , Alonso Church (1903). This states that any function for which an informal algorithm can be written to compute the value of the function is computable. For example, the function that is 1 for values of n which are multiples of two and 0 elsewhere is computable, and can be calculated by the informal algorithm that counts from 0 in steps of 2 until either n has been reached or n+1 has been reached; if the former then the function is 1 and if the latter then it is zero. This is a very simple example of a computable function, and it is not difficult to turn this informal algorithm into a formal proof that a Turing machine carrying out that process must terminate. For more complicated functions it is not obvious that this will be the case. The reason that Church\'s thesis is not really a mathematical idea is that it is about the relationship between informal reasoning and the formalized approach of the mathematical arguments, something that is the domain of philosophy. It is also a statement which cannot be proved, for exactly the same reason: the evidence is purely scientific nobody has ever managed to find an function for which it fails. SMcL
Further reading T.H. Crowley, Understanding Computers. |
|
