Squeezing arguments
Analysis 71 (1):22-30 (2010)
| Abstract | Many of our concepts are introduced to us via, and seem only to be constrained by, roughand-ready explanations and some sample paradigm positive and negative applications. This happens even in informal logic and mathematics. Yet in some cases, the concepts in question – although only informally and vaguely characterized – in fact have, or appear to have, entirely determinate extensions. Here’s one familiar example. When we start learning computability theory, we are introduced to the idea of an algorithmically computable function (from numbers to numbers) – i.e. one whose value for any given input can be determined by a step-by-step calculating procedure, where each step is fully determined by some antecedently given finite set of calculating rules. We are told that we are to abstract from practical considerations of how many steps will be needed and how much ink will be spilt in the process, so long as everything remains finite. We are also told that each step is to be ‘small’ and the rules governing it must be ‘simple’, available to a cognitively limited calculating agent: for we want an algorithmic procedure, step-by-minimal-step, to be idiot-proof. For a classic elucidation of this kind, see e.g. Rogers (1967, pp. 1–5). Church’s Thesis, in one form, then claims this informally explicated concept in fact has a perfectly precise extension, the set of recursive functions. Church’s Thesis can be supported in a quasi-empirical way, by the failure of our searches for counterexamples. It can be supported too in a more principled way, by the observation that different appealing ways of sharpening up the informal chararacterization of algorithmic computability end up specifying the same set of recursive functions. But such considerations fall short of a demonstration of the Thesis. So is there a different argumentative strategy we could use, one that could lead to a proof? Sometimes it is claimed that there just can’t be, because you can never really prove results involving an informal concept like algorithmic computability.. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | No categories specified (fix it) | |||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,672 |
| External links |
  Try with proxy. Try with proxy. |
| Through your library | Configure |
Similar books and articlesRobert Black (2000). Proving Church's Thesis. Philosophia Mathematica 8 (3):244--58.
R. Urbaniak (2011). How Not To Use the Church-Turing Thesis Against Platonism. Philosophia Mathematica 19 (1):74-89.
Eli Dresner (2008). Turing-, Human- and Physical Computability: An Unasked Question. Minds and Machines 18 (3).
Stewart Shapiro (1983). Remarks on the Development of Computability. History and Philosophy of Logic 4 (1-2):203-220.
Michael Rescorla (2007). Church's Thesis and the Conceptual Analysis of Computability. Notre Dame Journal of Formal Logic 48 (2):253-280.
Wilfried Sieg (1997). Step by Recursive Step: Church's Analysis of Effective Calculability. Bulletin of Symbolic Logic 3 (2):154-180.
Robert I. Soare (1996). Computability and Recursion. Bulletin of Symbolic Logic 2 (3):284-321.
Nachum Dershowitz & Yuri Gurevich (2008). A Natural Axiomatization of Computability and Proof of Church's Thesis. Bulletin of Symbolic Logic 14 (3):299-350.
Analytics
Monthly downloads |
Added to index2010-05-10Total downloads43 ( #26,146 of 549,068 )Recent downloads (6 months)1 ( #63,185 of 549,068 )How can I increase my downloads? |
My notes
Discussion
