Church Turing Thesis

9 Key excerpts on "Church Turing Thesis"

• 

  eBook - PDF

  Physics and Computation

  • Armond Duwell(Author)
  • 2021(Publication Date)
  • Cambridge University Press

    (Publisher)

  14 Given the above discussion, it should be reasonably clear that the Church–Turing thesis, even if true, is rather limited. It does not imply anything about what computers can do, when “computers” is understood as it is today as “a system that we use to perform computational tasks” rather than how Turing understood the term. Using Turing’s version of the thesis, recall that it states that if a function is effectively calculable, then it is calculable by a Turing machine. In the contrapositive, if a Turing machine cannot compute a function, then it is not effectively calculable. “Effectively calculable” has the essential connection to a human process lacking insight, intuition, or ingenuity. The thesis, if true, circumscribes what is possible given certain limited means. There seems to be no prima facie reason for thinking that the Church–Turing thesis, if true, circumscribes what is computationally possible in the contemporary sense. One can reasonably expect that human capabilities extend beyond what Turing machines are capable of because we do have insight, intuition, or ingenuity. Moreover, we could expect that systems characterized by physical processes very different from those a Turing machine has available to it would have 13 Turing also offered another argument in Section 9 of his paper (1936). See Copeland (2019) for a discussion. 14 Kripke (2013) argues that the Church–Turing thesis does admit proof, and he attempts to provide one. See Copeland (2019) for an overview of Kripke’s proof. Physics and Computation 9 different computational abilities. It is also of note that the Church–Turing the- sis, even if true, does not provide any indication about what computations can be done efficiently. Recall that computable numbers are computed by Turing machines that never halt! If one wants to be in the business of making claims about what is computationally possible or what is efficiently computable, then one has to go beyond the Church–Turing thesis.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Church's Thesis After 70 Years

  • Adam Olszewski, Jan Wolenski, Robert Janusz, Adam Olszewski, Jan Wolenski, Robert Janusz(Authors)
  • 2013(Publication Date)
  • De Gruyter

    (Publisher)

  This bold conjec-ture became known as “Church’s thesis.” At almost the same time, Alan Turing, who was unaware of Church’s work, proposed a different analysis of effective calculabil-ity [Turing 1936]. Like Church, Turing was trying to show that the Entscheidungsproblem is unsolvable. Instead of using a formal log-ical calculus, he based his analysis on the concept of an extremely simple, abstract “mechanism” now known as a “Turing machine.” Turing subsequently demonstrated [Turing 1937] that Turing (ma-chine) computability is extensionally equivalent (vis-` a-vis the com-putation of the number theoretic functions) to lambda-definability and general recursiveness. The fact that three independent and os-tensibly different analyses of effective calculability were extension-ally equivalent strongly suggested to mathematicians that they had finally captured the decidable (a.k.a. computable) number theoretic functions. Church’s thesis became the Church–Turing thesis. Turing’s analysis had a conceptual advantage over the others, for it seemed closer to the intuitive idea of carrying out a compu-tation. Turing introduced it in the context of an idealized person 134 Carol E. Cleland doing calculations with pencil and paper. Moreover, he explicitly characterized these idealized humans as “machines” and described their activity as “purely mechanical.” In Turing’s words, “A func-tion is said to be ‘effectively calculable’ if its values can be found by some purely mechanical process. We may take this statement liter-ally, understanding by a purely mechanical process one which could be carried out by a machine” [Turing 1939]. Given this, it is thus hardly surprising that the concept of a Turing machine is part of the foundation of theoretical computer science. Not only could the universal Turing machine compute all the computable functions (the Church–Turing thesis) but it also “performed” these calculations in a manner reminiscent of the way in which physical machines operate.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Alan Turing's Systems of Logic

  The Princeton Thesis

  • Andrew W. Appel(Author)
  • 2021(Publication Date)
  • Princeton University Press

    (Publisher)

  Thus when Church finally announced his Thesis in published form in 1936 [1], it was in terms of the latter. In that paper, Church applied his thesis to demonstrate the effective unsolvability of various mathematical and logical problems, includ-ing the decision problem for sufficiently strong formal systems. And then in his follow-up paper [2] submitted April 15, 1936—just around the time Tur-ing was showing Newman his draft—Church proved the unsolvability of the Entscheidungsproblem for logic. When news of this work reached Cambridge a month later, the initial reaction was great disappointment at being scooped, but it was agreed that Turing's analysis was sufficiently different to still warrant publication. After submitting it for publication toward the end of May 1936, Turing tacked on an appendix in August of that year in which he sketched the proof of equivalence of computability by a machine in his sense with that of ^-definability, thus forging the second link in the chain of equivalences [21]. In Church's 1937 review of Turing's paper, he wrote: As a matter of fact, there is involved here the equivalence of three differ-3 One must avoid the collision of free and bound variables in the process, i.e., no free variable z of s must end up within the scope of a λz; this can be don e by renamin g boun d variables as necessary. Turing'S TheSiS 17 ent notions: computability by a Turing machine, general recursiveness in the sense of Herbrand-Gödel-Kleene, and λ-definabilit y in the sense of Kleen e and the presen t reviewer. Of these, the first has the advantag e of makin g the identificatio n with effectiveness in the ordinar y (no t explic-itly defined ) sense evident immediately ... . The secon d and third have the advantag e of suitabilit y for embodimen t in a system of symbolic logic. 4 Thu s was born what is now called the Church-Turing Thesis, accordin g to which the effectively computabl e function s are exactly those computabl e by a Turin g machine.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Turing's Legacy

  Developments from Turing's Ideas in Logic

  • Rod Downey(Author)
  • 2014(Publication Date)
  • Cambridge University Press

    (Publisher)

  To define effectiveness as computability by an arbitrary machine, subject to restrictions of finiteness, would seem to be an adequate representation of the ordinary notion, and if this is done the need for a working hypothesis disappears.” In contrast, Church [1937a] wrote the following in his review of Turing [1936]. “ . . . in particular, a human calculator, provided with pencil and paper and explicit instructions, can be regarded as a kind of Turing machine. It is thus immediately clear that computability, so defined, can be identified with . . . the notion of effectiveness as it appears in certain mathematical problems (various forms of the Entschei- dungsproblem, various problems to find complete sets of invariants in topology, group theory, etc., and in general any problem which concerns the discovery of an algorithm).” Church clearly saw Turing’s [1936] characterization as a definition and not as a hypothesis, conjecture, or a thesis. The term “thesis” first appeared in Kleene [1943] when he used the term “Thesis I” for what we now call “Church’s Thesis.” In his very influential book [1952] Kleene introduced the terms “Church’s Thesis” and “Turing’s Thesis” and the former was used thereafter. 6.6. The Turing completeness theorem. Turing’s monumental achievement [1936] was: 1. to give a precise but informal analysis in [1936: §9] of the intuitive notion of an effectively calculable function; 2. to give a formal mathematical definition of an automatic machine (Turing machine) in [1936: §92]; and 3. to prove them equivalent (although this became obvious by the end of his paper). G¨ odel’s completeness theorem [1930] links a certain semantical notion to a syntactic notion by proving (as a theorem in ZFC set theory) that a formula of the predicate calculus is valid if and only if it is derivable from the axioms and rules of inference of the predicate calculus. We may view Turing’s [1936] work as likewise a theorem in ZFC. First, Turing analyzed in §9 just what an

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Computable Universe, A: Understanding And Exploring Nature As Computation

  Understanding and Exploring Nature as Computation

  • Hector Zenil(Author)
  • 2012(Publication Date)
  • WSPC

    (Publisher)

  1. Church Canons

  In a sense we have to untangle the relation between the concept of computability and the concept of computability, understanding the first concept as informally grasped and the second as rigorously defined. If one takes Gödel’s notion of general recursiveness as the rigorously defined concept and effective calculability as the informally grasped one, then Church’s Thesis expresses the relation between this and that concept of computability for number-theoretic functions: they are co-extensional. To provide a proper perspective for the broader investigation, I will examine the early history of computability hinted at in these remarks.

  1.1. The thesis

  Gödel introduced general recursiveness for number theoretic functions in his 1934 Princeton Lectures via his equational calculus; he viewed it as a heuristic principle that the informal concept of finite computation can be captured by suitably general recursions. Refining and generalizing a notion of finitistically calculable functions due to Herbrand, Gödel defined a number theoretic function to be general recursive just in case it satisfies certain recursion equations and its values can be determined from the equations by simple steps, namely, replacement of variables by numerals and substitution of complex closed terms by their numerical values. When he gave this definition in 1934 Gödel was not convinced, however, that the underlying precise concept of recursion was the most general one, and he expressed his doubts in conversation with Church. Nevertheless, Church formulated the thesis a year later for the first time in print. Here is the classical statement found in the abstract for Church’s talk to the American Mathematical Society in December 1935:

  . . . Gödel has proposed . . .a definition of the term recursive function, in a very general sense. In this paper a definition of recursive function of positive integers which is essentially Gödel’s is adopted. And it is maintained that the notion of an effectively calculable function of positive integers should be identified with that of a recursive function, since other plausible definitions of effective calculability turn out to yield notions that are either equivalent to or weaker than recursiveness.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  The Computing Universe

  A Journey through a Revolution

  • Tony Hey, Gyuri Pápay(Authors)
  • 2014(Publication Date)
  • Cambridge University Press

    (Publisher)

  He had also been able to use his formalism to show that the problem of deciding whether one string of symbols could be converted into another string was unsolv- able, in the sense that there was no lambda expression that could do this. In this way Church had been able to show that Hilbert’s third question, the Entscheidungsproblem, was also unsolvable. Although coming at the problem from very different perspectives, Turing and Church had both proved the problem’s insolvability. The statement – that anything effectively computable is computable by a Turing machine – is known as the Church-Turing thesis. It is called a the- sis rather than a theorem because it involves the informal concept of effec- tive computability. The thesis equates the mathematically precise statement, “computable by a Turing machine,” with the informal, intuitive idea of a problem being solvable by some algorithm on any machine whatsoever. It applies to all computable problems written in any programming language on any computer! The Church-Turing thesis is only a thesis but the majority of computer sci- entists accept its validity because many people besides Church and Turing have arrived at an equivalent result. At about the same time as Church and Turing’s work, mathematicians Stephen Kleene and Emil Post devised alternative for- malisms that led to similar notions of computability. Many others have looked at variants of the simple Turing machine such as machines with multiple tapes or machines with two-dimensional tapes. None of these machines can solve problems that cannot be solved by the basic Turing machine. Fig. 6.6. The “Knights of the Lambda Calculus,” the unofficial badge of LISP programmers at MIT. HALT START B B B B B B L L L A A A A A A A A 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 A A A B B B B B B 0 0 0 0 0 0 M M M M M M Y Y Y Y Y X X X X X X A S S S S R L L L L L L R R R R R R R R R R R L L Fig. 6.5. A representation of a Universal Turing Machine due to Marvin Minsky.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Philosophy of Mathematics

  • Dov M. Gabbay, Paul Thagard, John Woods(Authors)
  • 2009(Publication Date)
  • North Holland

    (Publisher)

  For Church, computability by a machine “occupying a finite space and with working parts of finite size” is analyzed by Turing; given that the Turing machine is the outcome of the analysis, one can then observe that “in particular, a human calculator, provided with pencil and paper and explicit instructions, can be regarded as a kind of Turing machine”. On account of the analysis and this observation it is for Church then “immediately clear” that (Turing-) machine computability can be identified with effectiveness. This is re-emphasized in the rather critical review of Post’s 1936 paper in which Church pointed to the essential finiteness requirements in Turing’s analysis: “To define effectiveness as computability by an arbitrary machine, subject to restrictions of finiteness, would seem to be an adequate representation of the ordinary notion, and if this is done the need for a working hypothesis disappears.” This is right, as far as emphasis on finiteness restrictions is concerned. But Turing analyzed, as we saw, a mechanical computor, and that provides the basis for judging the correctness of the finiteness conditions. In addition, Church is rather quick in his judgment that “certain further restrictions” can be imposed on such arbitrary machines to obtain Turing’s machines; this is viewed “as a matter of convenience” and the restrictions are for Church “of such a nature as obviously to cause no loss of generality”. Church’s apparent misunderstanding is rather common; see, as a later example, Mendelson’s paper [1990]. It is Turing’s student, Robin Gandy who analyzes machine computability in his 1980 paper Church’s thesis and principles for mechanisms and proposes a particular mathematical description of discrete mechanical devices and their computations. He follows Turing’s three-step-argument of analysis, formulation of restrictive principles and proof of a “reduction theorem”

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Memory and the Computational Brain

  Why Cognitive Science will Transform Neuroscience

  • C. R. Gallistel, Adam Philip King(Authors)
  • 2011(Publication Date)
  • Wiley-Blackwell

    (Publisher)

  So far, no one has identified a computation that we – or any other known thing - can do that no Turing machine can. We have developed computations of a complexity undreamed of in Turing’s day, but they can all be done by a Turing machine. In fact, they all are done on modern computers, which are examples of universal Turing machines – Turing machines that can emulate any other Turing machine. This does not necessarily mean that we will never discover such a computation. Brains solve a number of computational problems that we do not currently know how to program a computer to solve – face recognition for example. Perhaps brains can do computations that a Turing machine cannot do. But, if so, we have no clue as to how they do it. Nothing we currently understand about computation in the brain presents any challenge to a Turing machine. In fact, all current formally specified models of what goes on in brains are implemented on contemporary computers. The thesis that a Turing machine can compute anything that is computable is now called the Church-Turing thesis, because Alonzo Church, Turing’s thesis advisor, developed a closely related logical formalism, the lambda calculus, intended, like Turing’s, to formalize the notion of a procedure. Church’s work was done more or less simultaneously with Turing’s and before Turing became his graduate student. In fact, Turing went from Cambridge to Princeton to work with Church when he discovered that they were both working on the same problem. That problem was Hilbert’s Entscheidungsproblem (decision problem), the problem of whether there could be a procedure for deciding whether a proposition in arithmetic was provable or not – not for proving it, just for deciding whether it was provable. The conclusion of both Church and Turing’s work was that there cannot be such a procedure. That is, the decision problem was uncomputable

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  The Most Complex Machine

  A Survey of Computers and Computing

  • David J. Eck(Author)
  • 2018(Publication Date)
  • A K Peters/CRC Press

    (Publisher)

  recursively computable, and see what we can prove about them.” In the end, as I mentioned, it turns out that the recursively computable functions and the Turing computable functions are the same.

  10 I’ll bet you were wondering what I was going to do with the symbols x, y, and z.

  11 I should point out that once each Turing machine has a code number, it becomes easy to show that there are functions f: N → N which cannot be computed by any Turing machine. The trick is to write down a function that behaves differently from every possible Turing machine on at least one input. To define such a function, /, we define f(n) for each input number n as follows: If n is not a code number for some Turing machine, let f(n) = 0. (In fact, it makes no difference how we define f in this case.) If n is the code number of a Turing machine T, then we consider what happens when T is run with input n. Note that we are giving T its own binary code number as input. If T does not produce an output when given input n, because it fails to halt or halts with illegal stuff on its tape, then we define f(n) = 0. Note that such a T certainly doesn’t compute f because f gives output 0 on input n, while T fails to give any output at all. Finally, if T produces output m, then we define f(n)= m + 1. Again in this case, T does not compute f because f and T give different outputs on input n. Since every Turing machine has a code number and since we have set up f so that no machine with a code number computes f, it follows that no machine at all computes f. At the beginning of the chapter, I promised that we would find some interesting uncomputable functions. f

  Sign up to read

  Learn more about book