Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
The concept of computability
Cleland C. Theoretical Computer Science317 (1-3):209-225,2004.Type:Article
Date Reviewed: Sep 15 2004

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.

Reviewer:  Aladdin Ayesh Review #: CR130127 (0504-0478)
Bookmark and Share
Bounded-Action Devices (F.1.1 ... )
Set Theory (F.4.1 ... )
Would you recommend this review?
Other reviews under "Bounded-Action Devices": Date
Fairness and conspiracies
Best E. Information Processing Letters 18(4): 215-220, 1984. Type: Article
May 1 1985
Separating the eraser Turing machine classes Le, NLe, co-NLe and Pe
Krause M., Meinel C., Waack S. Theoretical Computer Science 86(2): 267-275, 1991. Type: Article
Jul 1 1992
Two nonlinear lower bounds for on-line computations
Dūris P., Galil Z., Paul W. (ed), Reischuk R. Information and Control 60(1-3): 1-11, 1984. Type: Article
Aug 1 1985

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy