Church Turing Thesis
The Church-Turing Thesis asserts that any function that can be computed by an algorithm can be computed by a Turing machine, or equivalently, by any computational device that is equivalent in power to a Turing machine. This thesis forms the foundation of theoretical computer science and provides a framework for understanding the limits of computation.
5 Key excerpts on "Church Turing Thesis"
eBook - ePub- Dov M. Gabbay, Paul Thagard, John Woods, Dov M. Gabbay, Paul Thagard, John Woods(Authors)
- 2009(Publication Date)
- North Holland(Publisher)
...We will then take on the problem of identifying an appropriate mathematical concept for this informal notion, i.e., issues surrounding Church’s or Turing’s Thesis. To get aconcrete perspective on the significance of the broad issues, let me mention claims formulated by Church and Gödel with respect to Turing’s work, but also point to tensions and questions that are only too apparent.Church reviewed Turing’sOn computable numbersfor theJournal of Symbolic Logicjust a few months after its publication. He contrasted Turing’s notion for effective calculability (via idealized machines) with his own (via Λ-definability) and with Gödel’s (via the equational calculus). “Of these [notions],” Church remarked, “the first has the advantage of making the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately …” Neither in this review nor anywhere else did Church give reasons, why the identificationisimmediately evident for Turing’s notion, and why it isnotfor the others. In contrast, Gödel seemed to capture essential aspects of Turing’s considerations when making a brief and enigmatic remark in the 1964 postscript to the Princeton Lectures he had delivered thirty years earlier: “Turing’s work gives ananalysisof the concept of ‘mechanical procedure’…. This concept isshownto be equivalent with that of a ‘Turing machine’.”20But neither in this postscript nor in other writings did Gödel indicate the nature of Turing’s analysis and prove that the analyzed concept is indeed equivalent to that of a Turing machine.Gödel underlined the significance of Turing’s analysis, repeatedly and emphatically. He claimed, also in[1964], that only Turing’s work provided “a precise and unquestionably adequate definition of the general concept of formal system”. As a formal system is for Gödel just a mechanical procedure for producing theorems, the adequacy of this definition rests squarely on the correctness of Turing’s analysis of mechanical procedures...
eBook - ePub- Michael Olinick(Author)
- 2021(Publication Date)
- Simply Charly(Publisher)
...With the lambda-calculus, Church and his Princeton student Stephen Kleene argued it was possible to translate each arithmetic formula into a standard form. They then showed that the question of deciding whether it was possible to convert one string of symbols into another string was an unsolvable problem since there could exist no lambda-calculus formula which accomplishes the task. Was Alan scooped again, unable to publish his result because someone else had already done so? It was not clear, however, that Church’s idea of a “formula of the lambda-calculus” was equivalent to Hilbert’s “definite method” of decidability. Turing’s approach was more direct, effective, and built up systematically from first principles. Newman recognized the value and originality of Alan’s work. He wrote the London Mathematical Society, urging the publication of Turing’s paper as his methods were quite different from Church’s and “the result is so important that different treatments of it should be of interest.” On the same day, Newman also wrote Church, praising Turing’s results and suggesting Alan go to Princeton to continue his research. Newman noted that “Turing’s work is entirely independent: he has been working without any supervision or criticism from anyone. This makes it all the more important that he should come into contact as soon as possible with the leading workers on this line, so that he should not develop into a confirmed solitary.” Church agreed to take Alan on as a graduate student. Turing added an appendix to his paper, demonstrating the mathematical equivalence of his work and Church’s approach. At the end of August, Alan prepared to embark for America....
eBook - ePubThis is Philosophy of Mind
An Introduction
- Pete Mandik(Author)
- 2013(Publication Date)
- Wiley-Blackwell(Publisher)
...One of his most significant contributions to the fields of mathematics, computer science, and artificial intelligence is his development in the 1930s of a formal notion of computation. 7.10 Nowadays, we are used to the idea of computing machines. Computers are a pervasive part of our lives. They exist not just as our desktop and laptop computers, but are also built into many of our phones and cars. It is important to keep in mind that back in Turing's day, there were no such machines. In fact, Turing's work on the notion of computation helped pave the way for the electronic computers that we are familiar with. Another thing to keep in mind is that the earliest uses of the word “computer” didn't refer to a kind of machine, but instead referred to a kind a person—a person who computes, that is, a person who figures out the answers to mathematical problems. 7.11 Turing developed his formal notion of computation and his related special notion of a computing machine (a Turing machine) in order to tackle a theoretical problem in mathematics. This problem can be stated as this question: Is there a method (an effective procedure) for determining, for any particular mathematical proposition, whether that proposition can be proven? In tackling this problem, Turing developed a notion of what an “effective procedure” is that can equally be carried out by a person and by a machine. The basic idea here can be thought of in terms of reading and writing symbols according to certain rules. In developing his idea of how a machine can do this, Turing developed the idea of what has since come to be known as a Turing machine. Turing m achines 7.12 Turing did not himself build a Turing machine (although, since then, actual Turing machines have been built). In Turing's mathematical work his machine was more of a thought experiment than an actual machine. At the heart of a Turing machine is a finite-state machine, a machine that can only be in one of a finite number of states at a time...
eBook - ePubArtificial Intelligence
An Introduction
- Alan Garnham(Author)
- 2017(Publication Date)
- Routledge(Publisher)
...The theory specifies what computers can and cannot do and how much time and memory they need for the computations that they can perform. It therefore indicates the limitations of computational theories of the mind. The theory had its origins in several branches of mathematics. A number of mathematicians were independently searching for the smallest set of primitive operations needed to carry out any possible computation. When their proposals were worked out in detail, it was shown that they were equivalent. One approach to the problem of computability was Turing's (1936). Turing formulated his ideas in terms of an abstract computing device called a Turing machine. A Turing machine performs its calculations with the help of a tape divided into squares, each of which can have one symbol on it. The Turing machine's primitive operations are reading and writing symbols on the tape and shifting and tape one square to the left or right. It uses a finite vocabulary of symbols, but its tape can be infinitely long. A Turing machine has only a finite number of internal states. When it reads the symbol on a square its state may change, depending on what state it is currently in and what the symbol is. The structure of a Turing machine is very simple and so are the operations it performs. However, additional bits of 'machinery' - more tapes for example - do not increase the range of computations that a Turing machine can perform. They only increase its speed. Furthermore, these gains in efficiency are of no theoretical interest, since they speed up the machine's operation by only a constant factor. It is possible to describe a Universal Turing Machine, constructed on the same principles as other Turing machines. The Universal Turing Machine can mimic the operation of any other Turing machine. To simulate another machine it must be given a description of how that machine works. This description can be written on to its tape in standard Turing machine format...
eBook - ePubReflections of Alan Turing
A Relative Story
- Dermot Turing(Author)
- 2021(Publication Date)
- The History Press(Publisher)
...Historic England may not have noticed that the King’s reputation for monuments in a consistently elegant style might not be damaged by the addition. The sculpture commemorating Alan Turing proposed for King’s College. (Antony Gormley Studio/Cambridge City Council) Sir Antony was quoted as saying: I am in debt to King’s College and its committee for giving me an extraordinary opportunity to think about this very particular person who unlocked the door between the industrial and the information ages … Of all Cambridge’s colleges, King’s has always been the most advanced and open to the new. The rectangular, blocky style of the sculpture may stand for the ‘logistic’ approach to mathematics and computing, Alan Turing’s major pre-war discovery and the foundation of computer science. The paper which explains it all may get fewer citations in Google Scholar than some of Alan’s other works, but is both the most important, and also the most misunderstood, of Alan Turing’s academic writings. It’s called ‘On Computable Numbers’, 3 which has come to mean that it’s about computing and numbers, which is sort of right, but only sort of. In the context of the Moral Sciences Club discussion which took place about a year before he started working on the paper, it’s actually about logic and the limitations of what can be proved using a mechanical, or robotic, process. Alan Turing invited his readers to imagine a (human) computer equipped with a set of rules and no imagination, and then put forward the idea of a machine which could follow similar rules – a table of instructions – in like fashion. The machine would get its input by reading symbols printed on a tape, and produce its output by writing symbols onto the tape. This type of machine, able only to do what it is told in the instruction table, has limitations, but the idea of the ‘universal’ machine which can process any set of instructions that you give it has profoundly interesting implications in mathematical logic...
