The long-standing issue of the formalist account of computability, as it is presented by Turing machines, is discussed in this paper. It provides good background information on the early work of Hilbert and Cantor, which is required knowledge for every computer scientist.
The paper uses this background to identify the weaknesses in Turing’s account of computability. This weakness can be summarized by the fact that “Turing’s account of computability is founded upon an idiosyncratic philosophical view about the nature of mathematics.” In other words, Turing’s account is based on a philosophical study of mathematics, rather than the study of physical machines. This paper, indeed, can be classified as belonging to the physical school of computation, which attempts to find alternative bases and understandings of computation theory, such as quantum computing and chaotic neural networks.
A section on hypercomputation, discussing the realization of physical computational theory through the development of physical devices that are not necessary bound by Turing machine requirements, concludes the paper. It also highlights the difficulties facing the developers of physical computation devices, such as verification. The hypercomputation section is the most interesting section of the paper, and worth developing further.
Recent research in quantum computing, chaotic neural networks, and nano-technology provides rich materials that are challenging to traditional computability theory, and encourage a new computational theory to emerge.