Off-campus access
Using PhilPapers from home?
Click here to configure this browser for off-campus access.
- Carol E. Cleland (1993). Is the Church-Turing Thesis True? Minds and Machines 3 (3):283-312.The Church-Turing thesis makes a bold claim about the theoretical limits to computation. It is based upon independent analyses of the general notion of an effective procedure proposed by Alan Turing and Alonzo Church in the 1930''s. As originally construed, the thesis applied only to the number theoretic functions; it amounted to the claim that there were no number theoretic functions which couldn''t be computed by a Turing machine but could be computed by means of some other kind of effective procedure. Since that time, however, other interpretations of the thesis have appeared in the literature. In this paper I identify three domains of application which have been claimed for the thesis: (1) the number theoretic functions; (2) all functions; (3) mental and/or physical phenomena. Subsequently, I provide an analysis of our intuitive concept of a procedure which, unlike Turing''s, is based upon ordinary, everyday procedures such as recipes, directions and methods; I call them mundane procedures. I argue that mundane procedures can be said to be effective in the same sense in which Turing machine procedures can be said to be effective. I also argue that mundane procedures differ from Turing machine procedures in a fundamental way, viz., the former, but not the latter, generate causal processes. I apply my analysis to all three of the above mentioned interpretations of the Church-Turing thesis, arguing that the thesis is (i) clearly false under interpretation (3), (ii) false in at least some possible worlds (perhaps even in the actual world) under interpretation (2), and (iii) very much open to question under interpretation (1).Reading list | Discuss | Edit | Categorize |My bibliography
| Export citation | Other links: springerlink.com | Scholar | At my library 
Similar books and articles
Turing's (1936) analysis of effective symbolic procedures is a model of conceptual clarity that plays an essential role in the philosophy of mathematics. Yet appeal is often made to the effectiveness of human procedures in other areas of philosophy. This paper addresses the question of whether Turing's analysis can be applied to a broader class of effective human procedures. We use Sieg's (1994) presentation of Turing's Thesis to argue against Cleland's (1995) objections to Turing machines and we evaluate her proposal to understand the effectiveness of procedures in terms of their reliability and precision. A number of conditions for effectiveness are identified and these are used to provide a general argument against the possibility of a Leibnizian decision procedure.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: springerlink.com dx.doi.org | Scholar | At my library | More options ...
| | Other links: springerlink.com dx.doi.org | Scholar | At my library | More options ... 1. The Physical Church-Turing Thesis. Physicists often interpret the Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system . . . No physically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: journals.uchicago.edu dx.doi.org | Scholar | At my library | More options ...
| | Other links: journals.uchicago.edu dx.doi.org | Scholar | At my library | More options ... A version of the Church-Turing Thesis states that every effectively realizable physical system can be defined by Turing Machines (‘Thesis P’); in this formulation the Thesis appears an empirical, more than a logico-mathematical, proposition. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. These models depend on infinite computation, explicitly or implicitly, and appear physically implausible; moreover, even if infinite computation were realizable, the Halting Problem would not be affected. Therefore, Thesis P is not essentially different from the standard Church-Turing Thesis. 1 Introduction 2 Computability and incomputability 3 The physical interpretation of the Church-Turing Thesis 4 Supertasks and infinite computation 5 Computation on non-well-founded domains 6 Analog computation 7 Quantum computation 8 Retrocausal computation 9 Conclusions.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: bjps.oupjournals.org jstor.org dx.doi.org | Scholar | At my library | More options ...
| | Other links: bjps.oupjournals.org jstor.org dx.doi.org | Scholar | At my library | More options ... Recent work on hypercomputation has raised new objections against the Church–Turing Thesis. In this paper, I focus on the challenge posed by a particular kind of hypercomputer, namely, SAD computers. I first consider deterministic and probabilistic barriers to the physical possibility of SAD computation. These suggest several ways to defend a Physical version of the Church–Turing Thesis. I then argue against Hogarth's analogy between non-Turing computability and non-Euclidean geometry, showing that it is a non-sequitur. I conclude that the Effective version of the Church–Turing Thesis is unaffected by SAD computation.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: bjps.oxfordjournals.org jstor.org dx.doi.org | Scholar | At my library | More options ...
| | Other links: bjps.oxfordjournals.org jstor.org dx.doi.org | Scholar | At my library | More options ... In recent years it has been convincingly argued that the Church-Turing thesis concerns the bounds of human computability: The thesis was presented and justified as formally delineating the class of functions that can be computed by a human carrying out an algorithm. Thus the Thesis needs to be distinguished from the so-called Physical Church-Turing thesis (or Thesis M), according to which all physically computable functions are Turing computable. The latter is often claimed to be false, or, if true, contingently so. On all accounts, though, thesis M is not easy to give counterexamples to, but it is never asked why—how come that a thesis that transfers a notion from the strictly human domain to the general physical domain just happens to be so difficult to falsify (or even to be true). In this paper I articulate this question and consider several tentative answers to it.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Scholar | At my library | More options ...
| | Scholar | At my library | More options ... Church's thesis asserts that a number-theoretic function is intuitively computable if and only if it is recursive. A related thesis asserts that Turing's work yields a conceptual analysis of the intuitive notion of numerical computability. I endorse Church's thesis, but I argue against the related thesis. I argue that purported conceptual analyses based upon Turing's work involve a subtle but persistent circularity. Turing machines manipulate syntactic entities. To specify which number-theoretic function a Turing machine computes, we must correlate these syntactic entities with numbers. I argue that, in providing this correlation, we must demand that the correlation itself be computable. Otherwise, the Turing machine will compute uncomputable functions. But if we presuppose the intuitive notion of a computable relation between syntactic entities and numbers, then our analysis of computability is circular.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: projecteuclid.org projecteuclid.org dx.doi.org | Scholar | At my library | More options ...
| | Other links: projecteuclid.org projecteuclid.org dx.doi.org | Scholar | At my library | More options ... There are various equivalent formulations of the Church-Turing thesis. A common one is that every effective computation can be carried out by a Turing machine. The Church-Turing thesis is often misunderstood, particularly in recent writing in the philosophy of mind.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Scholar | At my library | More options ...
| | Scholar | At my library | More options ... This paper explores Church's Thesis and related claims madeby Turing. Church's Thesis concerns computable numerical functions, whileTuring's claims concern both procedures for manipulating uninterpreted marksand machines that generate the results that these procedures would yield. Itis argued that Turing's claims are true, and that they support (the truth of)Church's Thesis. It is further argued that the truth of Turing's and Church'sTheses has no interesting consequences for human cognition or cognitiveabilities. The Theses don't even mean that computers can do as much as peoplecan when it comes to carrying out effective procedures. For carrying out aprocedure is a purposive, intentional activity. No actual machine does, orcan do, as much.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: csa.com springerlink.com kluweronline.com ingentaconnect.com dx.doi.org | Scholar | At my library | More options ...
| | Other links: csa.com springerlink.com kluweronline.com ingentaconnect.com dx.doi.org | Scholar | At my library | More options ... Horsten and Roelants have raised a number of important questions about my analysis of effective procedures and my evaluation of the Church-Turing thesis. They suggest that, on my account, effective procedures cannot enter the mathematical world because they have a built-in component of causality, and, hence, that my arguments against the Church-Turing thesis miss the mark. Unfortunately, however, their reasoning is based upon a number of misunderstandings. Effective mundane procedures do not, on my view, provide an analysis of ourgeneral concept of an effective procedure; mundane procedures and Turing machine procedures are different kinds of procedure. Moreover, the same sequence ofparticular physical action can realize both a mundane procedure and a Turing machine procedure; it is sequences of particular physical actions, not mundane procedures, which enter the world of mathematics. I conclude by discussing whether genuinely continuous physical processes can enter the world of real numbers and compute real-valued functions. I argue that the same kind of correspondence assumptions that are made between non-numerical structures and the natural numbers, in the case of Turing machines and personal computers, can be made in the case of genuinely continuous, physical processes and the real numbers.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: springerlink.com | Scholar | At my library | More options ...
| | Other links: springerlink.com | Scholar | At my library | More options ... We critically discuss Cleland''s analysis of effective procedures as mundane effective procedures. She argues that Turing machines cannot carry out mundane procedures, since Turing machines are abstract entities and therefore cannot generate the causal processes that are generated by mundane procedures. We argue that if Turing machines cannot enter the physical world, then it is hard to see how Cleland''s mundane procedures can enter the world of numbers. Hence her arguments against versions of the Church-Turing thesis for number theoretic functions miss the mark.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: springerlink.com | Scholar | At my library | More options ...
| | Other links: springerlink.com | Scholar | At my library | More options ... Discussion of Carol E. Cleland, Is the church-Turing thesis true?
 Back
All discussions
Start a new thread
|
There are no threads in this forum |
Nothing in this forum yet.
