Paper Info
Title
Computation, hypercomputation, and physical science
Abstract
Copeland and others have argued that the Church–Turing thesis (CTT) has been widely misunderstood by philosophers and cognitive scientists. In particular, they have claimed that CTT is in principle compatible with the existence of machines that compute functions above the “Turing limit,” and that empirical investigation is needed to determine the “exact membership” of the set of functions that are physically computable. I argue for the following points: (a) It is highly doubtful that philosophers and cognitive scientists have widely misunderstood CTT as alleged.1 In fact, by and large, computability theorists and mathematical logicians understand CTT in the exact same way. (b) That understanding most likely coincides with what Turing and Church had in mind. Even if it does not, an accurate exegesis of Turing and Church need not dictate how today's working scientists understand the thesis. (c) Even if we grant Copeland's reading of CTT, an orthodox stronger version of it which he rejects (Gandy's thesis) follows readily if we only accept a highly plausible necessary condition for what constitutes a deterministic digital computer. Finally, (d) regardless of whether we accept this condition, the prospects for a scientific theory of hypercomputation are exceedingly poor because physical science does not have the wherewithal to investigate computability or to discover its ultimate “limit.”
Year
DOI
Venue
2008
10.1016/j.jal.2008.09.007
Journal of Applied Logic
Keywords
Field
DocType
Hypercomputation,Church–Turing thesis,Gandy's thesis,Mechanical computability,Algorithms,Turing limit,Physical science,Physical computability
Physical science,Church–Turing thesis,Hypercomputation,Algorithm,Super-recursive algorithm,Computability,Scientific theory,Turing degree,Philosophy,Turing,Epistemology
Journal
Volume
Issue
ISSN
6
4
1570-8683
Citations 
PageRank 
References 
1
0.35
4
Authors
1
Name
Order
Citations
PageRank
Konstantine Arkoudas118619.63