Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
The concept of computability
Cleland C.  Theoretical Computer Science 317 (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
One head machines from a symbolic approach
Gajardo A., Mazoyer J.  Theoretical Computer Science 370(1-3): 34-47, 2007. Type: Article
Jun 1 2007
NL-printable sets and nondeterministic Kolmogorov complexity
Allender E.  Theoretical Computer Science 355(2): 127-138, 2006. Type: Article
Sep 22 2006
Information, ethics, and computers: the problem of autonomous moral agents
Carsten Stahl B.  Minds and Machines 14(1): 67-83, 2004. Type: Article
Jul 25 2005

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2021 ThinkLoud, Inc.
Terms of Use
| Privacy Policy