![]() | This ![]() It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
I just made my best effort to rewrite the introduction. Judging from the comments below, the introduction has been in need of revision by an expert for quite some time, i.e., someone who could rewrite it with confidence, rather than just trying to sort of preserve and polish what was there. Still, I tried to stay true to the spirit of the original as far as possible, and re-used as much as possible --- I also borrowed at least one sentence from the article on computable functions.
I got rid of some pseudo-terminology such as "combined hypothesis", which does not mean anything as far as I was able to determine, except perhaps in statistics. I tried to be slightly more precise in the description of the three formally defined classes of computable functions (lambda definable, Turing definable, and general recursive) - in particular, the first two of these classes require an encoding of the natural numbers (either as lambda terms, such as the Church numerals, or as symbols on a tape of the Turing machine). The old intro had glossed over this a bit too much in my opinion --- although certainly I am also only alluding to it and not giving fully formal definitions. I tried to strike a balance between concision and precision. To see the full and precise definitions, the readers will have to follow the links to the respective articles.
I also renamed the next section "Statement in Church's and Turing's words", because that is exactly what the section contains. The old title, "Formal Statement", didn't make sense, because by its nature, the Church-Turing thesis is an informal statement that can never be formalized. Selinger ( talk) 00:17, 25 August 2014 (UTC)
I'm not sure why we even bother with a link to nonsense about Burgin's supposed refutation of the thesis. If anyone is in for a good laugh, skim through the appallingly poorly written The rise and fall of the Church-Turing Thesis. [1] To quote his modest conclusion:
...riiiight... His work is almost universally regarded, at best, as something between a misunderstanding, a new word for an old concept and a marketing fraud. See for instance Martin Davis' unkind review of Burgin's book [2] and his description of Burgin's misunderstanding [3]. Pascal.Tesson ( talk) 19:34, 7 February 2008 (UTC)
I have removed the following paragraphs:
One conclusion to be drawn is that, IF a computer can effectively calculate an algorithm THEN so can an equivalent Turing Machine. But the converse is not true: It is NOT true that IF a Turing machine can calculate an algorithm THEN so can a computer; no computer is as computationally powerful as a Turing Machine since a computer does not have the required infinite memory nor infinitely-sized variables.
Thus it is not possible to build a calculation device that is as powerful as the simplest theoretical computing mechanism (a Turing machine). Note that this formulation of power disregards practical factors such as speed or memory capacity; it considers all that is theoretically possible, given unlimited time and memory.
Why? Because 1. it is poor style to shout (uppercase) in an encyclopedic article, and 2. it is false and obviously stems from a a poor understanding of the subject matter. A Turing Machine (TM) is not the simplest theoretical computing machine (e.g. finite automaton is far weaker). In fact, a TM is the most complex abstract computing machine known to mathematicians and computer scientists. Now, a TM does not suppose infinite time nor memory. A TM is one (the most successful in many mathematicians opinion) formalization of the concept algorithm, and as such is inherently infinite viewed as a set of input/output pairs. On the other hand, the computation of an output from an input is always finite, and if a computation can be effected on a TM, then it can on a regular computer to. Finiteness (of its description) is part of the TM's definition, and it can always be simulated in any standard computer programming language. Hence the computation can theoretically be done on a computer if it can be done on a TM, and vice versa.
Note that a TM should not be thought of as a physical machine, but as a formal mathematical object intended for reasoning about algorithms, i.e. how a physical computer works. It is thus in a sense true that a TM disregards practical factors such as time and space, but only because they are not attributes of the concept algorithm. On this conceptual level it is the dicotomy finite/infinite which is essential, and this issue is indeed properly covered by the TM theory. Time and space considerations enters when one attempts to analyze one specific algorithm: they are attributes of the concept computation. Barra ( talk) 16:24, 5 March 2008 (UTC)
The term Church's thesis (CT) is used in intuitionistic logic to describe an additional axiom, saying that all functions are computable. There should be either a pointer in the introduction or a disambiguation page. -- Thorsten ( talk) 15:59, 6 March 2008 (UTC)
To keep the discussion together in one place, I will remove this duplicate section and point to the discussion on this exact topic at Talk:Algorithm#A_paradoxical_situation. — Carl ( CBM · talk) 20:38, 19 March 2008 (UTC)
I removed (perhaps not the first time) a claim that the CT thesis somehow depends on the definition of algorithm. This isn't true; the CT thesis is a specific claim about one specific meaning of algorithms, the one that is discussed in the introductory part of any recursion theory text. It is trivially possible to make the "other CT theses" true or false if other definitions were employed; but those other versions are not "the Church-Turing thesis". That is about a specific notion of algorithm and a specific notion of computability. — Carl ( CBM · talk) 10:53, 9 May 2008 (UTC)
Is it just me, or are there other mathematicians out there that regard the Church-Turing thesis as nonsense? The phrase'effectively calculable' is only defined in terms of other English words, which are themselves not defined. The author then seems to lose interest in the pretence of rigour by not defining the word 'machine'. —Preceding unsigned comment added by 86.9.138.200 ( talk) 20:02, 7 October 2008 (UTC)
Have anyone tried to disprove Turing thesis by pointing to analog computers? Analog computation yields results in form of real numbers while Turing machine is obviously not capable of computing with this kind of "infinite precision". Martin. —Preceding unsigned comment added by 85.216.202.14 ( talk) 22:09, 11 October 2008 (UTC)
Hm, it doesn't look like the restriction to the domain of natural numbers is mentioned anywhere on the web page. Even "effectively calculable" page seems to ignore the restriction:
An effective method (also called an effective procedure) for a class of problems is a method for which each step in the method may be described as a mechanical operation and which, if followed rigorously, and as far as may be necessary, is bound to:
I'm a little troubled by the formatting here. Shouldn't the title have a hyphen-minus in it instead of an en-width dash? And, also, full spaces around the em-width dashes in the article body are not so good. 66.102.80.246 ( talk) 03:04, 13 October 2008 (UTC)
I would like to suggest removing the phrase "in more modern terms" be removed from the opening sentence ("In computability theory, the Church–Turing thesis (also known as the Turing–Church thesis,[1] the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a combined hypothesis ("thesis") about the nature of functions whose values are effectively calculable; or, in more modern terms, functions whose values are algorithmically computable."). The description "effectively calculable" is not archaic and "algorithmically computable" is more of a computer science preference than a more precise term.
Instead, I suggest: "In computability theory, the Church–Turing thesis (also known as the Turing–Church thesis,[1] the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a combined hypothesis ("thesis") about the nature of functions whose values are effectively calculable (also called functions whose values are algorithmically computable).
Jimperrywebcs ( talk) 16:02, 2 May 2014 (UTC)
I am moving this section out of the article until I have time to fix it. The idea that Turing machines do not actually model real computers is a very uncommon POV. Many CS books will state that Turing machines are indeed a theoretical model of real computers, in which resource limitations have been removed. The idea that input/output prevents Turing machines from modeling computers is odd, since an oracle Turing machine can view the tape as a sequence of inputs coming from a console, and read from the oracle tape whenever it desires more input. — Carl ( CBM · talk) 12:56, 24 October 2008 (UTC)
In what has been called the "Turing thesis myth," [6] [7] the Church-Turing thesis has often been misinterpreted as a claim that real computers can be modeled as Turing machines. This is incorrect. The Church-Turing thesis concerns the computability of mathematical functions. Real computers may do input and output continuously during computation, and thus are modeled as interaction machines, a model distinct from and not reducible to the Turing machine. However, a Turing machine does model what a computer can do between any input and output events. For formal models of computers with input and output functionality, see super-recursive algorithm, and anytime algorithm.
In my opinion, this article is very hard to understand. Most of the questions I had before coming here are still unanswered after reading it, and worst: now I'm confused. Someone with a strong background in this area, please rewrite this article in a more clear, helpful way.
I am going to work on rewriting the lede, and moving much material out of it ot he main article. The lede is meant to be a summary of the article in plain language, so that even someone who can't read the whole article can get a sense of what's going on from the lede. The present lede has 15 footnotes and focuses primarily on historical terminology; it needs to be more concise and direct. — Carl ( CBM · talk) 12:50, 24 October 2008 (UTC)
I have been reading up on various aspects of the Church-Turing thesis and I am almost at a point where I can start to do some significant work on this article. It's been on my plans for a while, but I thought I should go ahead and point out those plans to everyone else.
In the article as it stands, much of the important information is present, but the organization is not optimal, and some important things are missing. If it were graded as an undergraduate essay, I do not think it would get an A. I'd like to improve the article so that it would be an obvious A. Here are some of the issues that I would like to address.
It will be a while before I have the time to really dig into this article, but I think it is a place where, with some more work, we can get an exceptional article that will be extremely informative and beneficial to many readers. — Carl ( CBM · talk) 11:03, 14 September 2009 (UTC)
Carl, if you can recommend any contemporary readings I'm interested. I've read the Gandy and Seig papers but I need something with a broader brush. (Kalmár's proof sounds really interesting, can this be found anywhere but a library? In the process of a google-hunt I ran into this: http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.ndjfl/1093637645. Here Kleene 1987 at the very end of his paper, says he heard Kalmar give a talk about his proof and was going to publically punch a hole in his "proof" . . .but:
Thanks, Bill Wvbailey ( talk) 19:36, 15 September 2009 (UTC)
I think I found a pretty good paper. It was published in a journal that also published some hypercomputation crankyness, but this paper is not of that kind. I like it that it clearly distinguishes between human-CTT and physical-CTT. Soare's paper also does this, but the discussion is less clear there. Official ref is: Antony Galton, The Church–Turing thesis: Still valid after all these years?, Applied Mathematics and Computation, Volume 178, Issue 1, 1 July 2006, Pages 93-102 Pcap ping 09:58, 17 September 2009 (UTC)
Rewrite of Intro
As the plans described above seem to be on hold (it's now April 2010), I've reorganized the intro to improve it's readability for the casual reader who doesn't need/want to read further than the intro. I've also linked to the Wikipedia article on computability. I'll wait a few months before editing further to see if any of the plans above come to fruition. Ross Fraser ( talk) 07:57, 21 April 2010 (UTC)
What appears to be a rewrite of the wiki Church-Turing thesis article appears here: http://www.fact-archive.com/encyclopedia/Church-Turing_thesis. It's interesting to see their crack at it. Wvbailey ( talk) 21:47, 15 September 2009 (UTC)
Should we be that cautions here? See Quantum computing#Developments. Pcap ping 18:44, 15 September 2009 (UTC)
Humph. Given certain assumptions about the answers to certain unsolved physics problems leads to the ability to solve the halting problem for the Turing machine. Therefore, this thesis is not proved. 75.45.17.132 ( talk) 02:54, 6 December 2009 (UTC)JH
This change replaced Strong Church Turing Thesis" with "Complexity-theoretic Turing Thesis" claiming that "strong" is a weasel word. I've reverted it because WP:WEASEL does not apply to terminology quoted as such. Pcap ping 04:53, 8 December 2009 (UTC)
Maybe somebody could clarify for me – I am not deeply into computer science – I thought the "Strong Church-Turing thesis" is that any reasonable deterministic universal computation system can simulate any other reasonable deterministic universal computation system with a polynomial gain in execution time. — Carl ( CBM · talk) 22:04, 8 December 2009 (UTC)
Certainly we cannot call it "Computational Complexity-Theoretic Church-Turing Thesis" if no-one else calls it that: few Google hits, 0 Google Scholar hits, 1 hit in Google Books. The article claims that "This thesis was originally called Computational Complexity-Theoretic Church–Turing Thesis by Ethan Bernstein and Umesh Vazirani (1997)". However, the original paper does not seem to use exactly this term; it uses more vague and variable phrases such as "the modern (complexity theoretic) formulation of the Church–Turing thesis", "a modern strengthening of this thesis", "the complexity-theoretic form of the Church–Turing thesis", and "the modern form of the Church–Turing thesis". — Miym ( talk) 22:58, 8 December 2009 (UTC)
By the way, for some reason I have got the impression is that only quantum computing people have ever claimed that there exists a "strong CT thesis", and the only reason for them to define it is to show how to refute it. Did the strong CT thesis really exist before the quantum computing era? Did someone present it before they knew how to refute it? Using a quantum computing book as a source does not really help to convince me... — Miym ( talk) 23:00, 8 December 2009 (UTC)
Peter Wegner and Dina Goldin have written several papers about the C-T thesis, claiming a generalized misunderstanding of its meaning among CS theory [9] and showing how it could be superseded by the interactive computation model. [10] In particular, the "driving home for work" problem (creating a computer system to control an automatic car through real traffic) shows a simple and clear example of a computable task that cannot* be solved by a Turing machine but can be "solved" (for some particualr meaning of "solve" and "computable") by an interactive program.
(*using the classical definition of a TM, where all input is given at the beginning).
Does anyone know which ones are the most relevant articles from Wegner, and whether it has been criticized by others? I think stating the "driving home" problem would be a good addition to this article, to show what are the concerns of people opposing the C-T thesis. Diego ( talk) 15:39, 22 March 2010 (UTC)
While it is true that oracle Turing machines are perfectly capable of solving problems requiring repeated input, this is not really relevant to the ordinary Church-Turing thesis. As Wegner and Goldin say,
But this "limitation" is a key part of the Church-Turing thesis. The ordinary Church-Turing thesis is what they call the "Turing thesis":
It would be perfectly reasonable for this article to mention Wegner and Goldin in the section "variations", but not in the top part, which is about the ordinary thesis, namely
It is obvious that there are "algorithms" that are unrelated to computing functions and which cannot be done by a Turing machine. For example, I can write an algorithm to make a good martini. This is why the ordinary thesis is limited to only considering number-theoretic functions. I do not believe Wegner and Goldin argue that this usual version of the thesis is incorrect, and indeed they affirm the thesis in the form "TMs can compute any algorithmic problem." The issue, as they point out in their papers, is that in order to use Turing machines one must first correctly represent the problem to be solved as a function problem. — Carl ( CBM · talk) 00:57, 24 March 2010 (UTC)
I wonder why people continue to say “Church-Turing thesis,” instead of, say, “Dershowitz-Gurevich Theorem” ?
Dershowitz and Gurevich axiomatized the notion of “effectively calculable” using abstract state machines, and proved both Church’s thesis (all effectively calculable (partial) functions are general recursive) and Turing’s thesis (the effectively calculable functions are exactly those which can be programmed on a Turing machine).
I don’t understand why this paper, published in the Bulletin of Symbolic Logic in 2008, isn’t famous. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402
199.212.17.130 ( talk) 11:09, 20 August 2010 (UTC)
I removed some link to a paper about the Actor model. The link was to an unpublished paper by Carl Hewitt about the Actor model. Editors who are unaware should consult the related arbitration case. The outcome of that case authorizes the removal of this sort of material.
However, I think it is important to point out the mathematical reason this material is not included, so that it is more clear why the material isn't appropriate for this article.
The idea that concurrency is related to the Church-Turing thesis is not in agreement with the vast majority of literature on the thesis. The thesis says that any number theoretic function that is computable by a human using paper and pencil is computable by a Turing machine. The thesis is not related to methods of computation, and it does not refer to computations that are not functions or to computations that would require human beings to use special equipment.
The example that Hewitt gives in the unpublished paper is a nondeterministic process that does the following:
Hewitt's model corresponds to a post office that can deliver letters out of order and that can delay any letter indefinitely. So, with those assumptions, it is clear that the number you have in x when you receive the "stop" message will depend on the order in which you receive the letters you have sent. Indeed, any particular number is possible, depending on how pathological the postman is. There is nothing contradictory about this.
But that example has nothing at all to do with computing a function. Indeed, if different invocations of the same process can produce different outcomes, then you are definitely not computing a function, full stop. Moreover, the example is not an algorithm that a human can theoretically carry out using paper and pencil alone. It requires some element of randomness, but an "algorithm" in the sense of the Church-Turing thesis needs to be explicit to the point that a human can follow it without needing to ask for additional information apart from the input of the function. — Carl ( CBM · talk) 23:46, 19 November 2010 (UTC)
If Church were around, he would agree with Hewitt, Milner, and Hoare that the lambda-calculus left out something important for effective computation. The interesting thing is that these modern theorists were able to formally prove and precisely indentify how nondeterministic Turing machines are lacking in computational power that is important in modern computing for networking and many-core systems. Of course, their work is highly relevant to meainstream understanding of the notion of effective computation that Church et. al. were trying to formalize. Actor Model of Computation has an explanation of how the modern work relates to the older Church/Turing/Rosser results:
Milner, Hoare, etc. have published similar results.
You don't seem to understand how ridiculous it is to try to represent an operating system as a recursive function. 171.66.73.165 ( talk) 03:25, 20 November 2010 (UTC)
The material was added again, and remove again. If the material is added a third time, I will take the unfortunate step of protecting the page from editing by IP editors, in accordance with the arbitration case linked above. The work of Hewitt and others is perfectly valid and reasonable; that is not at issue here. The issue is that nondeterminism is not related to the Church-Turing thesis, which is about the computation of functions, not about about computation in general. — Carl ( CBM · talk) 23:21, 21 November 2010 (UTC)
The Church Turing thesis has an important history in computer science. See What is computation? Concurrency versus Turing's Model from the article published in Arxiv (a somewhat competitor to Wikipedia that is often censored here). 76.254.235.105 ( talk) 23:13, 28 November 2010 (UTC)
I have tried to arrange the messy paragraph involving super-recursive, or hyper-Turing, computation. I moved the claims attributed to Eberbach and Wegner to an earlier section, and rephrased them following their article. I removed the claims attributed to Peter Kugel since his article, cited in the reference section, does not support was has been written in his name. I did not touch the text referring to Mark Burgin's claims as I do not have his book at hand, but it should be removed if it cannot be verified. AmirOnWiki ( talk) 14:42, 14 October 2011 (UTC)
The article is perfectly fine. That said, the Church-Turing thesis is nothing but a normal math definition, like any other, e.g. the epsilon-delta definition of a continuous function. Maybe this should be mentioned more clearly in the article. See e.g. R. I. Soare, 1996. Computability and recursion, Bulletin of Symbolic Logic v. 2 pp. 284–321(?). — Preceding unsigned comment added by DanielVallstrom ( talk • contribs) 18:04, 29 January 2012 (UTC)
There is an incorrect definition of the Church Turing thesis here Turing_(disambiguation)-- Mongreilf ( talk) 21:37, 18 June 2012 (UTC)
Indeed Mongreilf. Why don't you fix it? ;) Anyway, I changed the explanation of the Church-Turning thesis to "the hypothesis that everything computable is computable by a Turing machine" --- despite the fact that arguably that explanation is close to nonsense in the sense that one should rather view the thesis as nothing more than a normal math definition. Daniel Vallstrom ( talk) 14:58, 20 June 2012 (UTC)
Is the Physical Church–Turing thesis (PCTT) equivalent to the Church–Turing–Deutsch principle? Bayle Shanks ( talk) 08:20, 26 May 2013 (UTC)
In the bullet list of the lede, the second item reads: British mathematician Alan Turing created a theoretical model for a machine, now called a universal Turing machine, that could carry out calculations from inputs.
Though technically correct, I think this is somewhat confusing for readers new to the topic. It sounds as if Turing had taken someone else's earlier concept of "a Turing Machine" and only specified the "universal Turing machine" from that concept. Would there be a major problem with writing "..., now called a Turing machine, ..."?
I understand that this may slightly reduce historical correctness. However, the rest of the lede only talks about "the Turing machine" and gives no dates whatsoever, so it isn't terribly historically correct anyway ;-) (And that's perfectly fine! The lede is not the place for historical details.) Therefore, I think new readers would benefit from the change, and anyone familiar with the concept won't suffer. And it's the new readers for whom the lede is written, right?
Agree / Disagree, anyone? -- Se'taan ( talk) 00:48, 28 September 2013 (UTC)
Agree. The term 'universal' specifies Turing machines capable of simulating others, like a compiler or an interpreter. Which seems confusing, and beside the point. I'll change it.
Ummm... the line after is also wrong. The recursive functions are due to Gödel, with Herbrand, not Church et al., I'm pretty sure. I'll fix that too. Daniel Vallstrom ( talk) 08:28, 28 September 2013 (UTC)
--- Backup:
Here comes probably the most frequent dispute in writing about the Church-Turing thesis: Shouldn't we settle on an easily distinguished name for the "intuitive notion of computability" and "the notion captured by the formalisms"? I don't mean "we" as in "the scientific world", but as in "the whole of Wikipedia, even if the scientific world hasn't yet settled". The biology articles about some species (and about the term "species") sometimes do this, too, even though there is no universally accepted usage of the terms. They do it just so the articles get better, and these articles state this usage in wikipedia as "nonstandard, but only because nothing's yet agreed upon".
I know it may seem to be a stickler's question, but this is particularly disturbing when reading several articles about computability, and they all use different meaning for those words. I was working on Effective method which shortly mentions the Church-turing thesis. That article makes a distinction, introduced [13] by User:Lambiam on the edit of User:CBM, which is "effectively calculable" for the "intuitive" notion and "effectively computable" for that of the formalisms. Likewise, Effectively calculable redirects to Effective method, whereas Effectively computable redirects to Computable function (as does Total recursive function, so I guess Computable function should descibe the formal notion, which I think it does. Someone please give me a reality check if this is not the case).
To put it in short: Should we rewrite the lead so that it consequently uses "calculable" to mean "calculable with some effective method" and "computable" to mean "computable with a Turing machine"? Note that we make a more clear description of Effective method at the very article. This is not merely an "intuitive" notion, there is some agreement on it. It's just not a full formal definition.
On a different matter, maybe someone could help me out: Does the Church-Turing thesis only apply to the computability of number-theoretic functions, or of functions in general? See Talk:Effective method#Is the Church-Turing thesis restricted to number-theoretic functions?. I need to edit this in [Effective method]], and you'll stumble across that sentence anyway when you look at the article. Thanks! -- Se'taan ( talk) 01:18, 30 September 2013 (UTC)
Goodness me, what a load of Russell-like sophistry this article is. There is still no real definition of of finite, that is a finite number of steps to prove a theory. Kantor got it right when he devised an algorithm to count all of the rational numbers between 0 and 1. While the number of rationals is bigger than any number you can specify (i.e. show it explicitly). Why all this nonsense about Turing machines? Does it have a clock tick time of 0 seconds? Is the Turing machine a discrete state machine? If not, then what it does is not countable. SHEESH!!! 27.33.243.64 ( talk) 09:48, 15 December 2015 (UTC)
What is the appropriate term, a dissertation or a thesis? UK convention is that a thesis is to obtain a Doctorate degree and dissertation to complete a Master's. The US convention is the reverse – a dissertation is written for a PhD and a thesis for a Master’s.
Turing was British but obtained his PhD from Harvard in the US. -- TedColes ( talk) 08:54, 19 February 2014 (UTC)
American school, so American definition, no? Zenten ( talk) 10:34, 7 August 2019 (UTC)
There are several missing references to Sieg's papers. These references appear in many footnotes but no Sieg papers appear in the References section of the article. There may be other missing or obscured references and this should be thoroughly checked. For example, there are several references to "Barwise 1980" in the footnotes, but there is no actual stand-alone References entry to that work; instead it appears buried in the Reference for Grady, 1980. Lesgasser ( talk) 17:43, 26 July 2014 (UTC)
There are also an "extended form" of the thesis.
As comment by recently by P. Shadbolt et all (in DOI:10.1038/NPHYS2931) "Famously, the extended Church–Turing thesis (ECT) says that all computational problems that are efficiently solvable with realistic physical systems can be efficiently solved with a classical machine — a statement clearly in conflict with our hopes for the capabilities of quantum computers", Shor, P. W. in Proc. 35th Ann. Symp. Found. Comput. Sci. 124–134 (IEEE, 1994). -- Krauss ( talk) 03:09, 14 December 2014 (UTC)
As BQP != BPP was proven in the last few years (2018 I think) the extended Church-Turing thesis must be invalidated. There are problems with efficient solutions in BQP (quantum computations) without efficient solutions on a probabilistic Turing machine. — Preceding unsigned comment added by 2A00:23C4:8585:7D01:1C42:5F57:F923:8501 ( talk) 14:50, 19 February 2021 (UTC)
SMmoto is correct that by 1939 both Church and Turing were well aware of each other's work -- but to accept Turing's paper (1936) Church was the only possible referee, and he had already published (paper appeared) on 15 April, pre-empting Turing by . To quote Hodges: "A new idea had found its way into two human minds simultaneously and independently" (Hodges 1983:111). For Hodges' take on the entire sequence of events see Hodges 1983:111-113. I also remember reading somewhere that a "certification process" had to occur after which the paper was accepted on 28 May 1936 to the London Mathematical Society. Hodges isn't so clear on this. If I find out what happened, I'll add it here. Bill Wvbailey ( talk) 17:19, 2 February 2015 (UTC)
This article does not respect the fundamental principle of Wikipedia the articles must have a neutral point of view in fact, the point of view of the philosophers and logicians are presented in full details, while the point of view of computer scientists is totally lacking. This is amazing, when considering the importance of computer science and the fact that Church and Russell are unanimously considered as being among the founders of theoretical computer science. This point of view may be summarized as follows:
In theoretical computer science, the original Church–Turing thesis has been extended into the (clearly unprovable) principle (also called Church–Turing thesis) that every possible model of computation computes only Turing-computable functions. This principle is supported by the fact that all models of computations that have ever been proposed compute either exactly the same functions as Turing machines (such are recursive functions, lambda calculus, and also random-access machines and quantum computers), or a subclass of the Turing computable functions (such as primitive recursive function and automata).
For being useful for readers interested in computer science, the lead must include something like that (preferably with shorter sentences and less parentheses). The body of the article must also be edited to expand this sentence and correcting some errors introduced by this non-neutral point of view. For example, in section "Informal usage in proofs", the description of what is needed to have a formal proof of the example is wrong. For having a formal proof, it suffices to write the algorithm in the programming language of an abstract machine that has been already proved as equivalent (in the sense of Turing–Church thesis) to a Turing machine. This is essentially what is called pseudocode, when one use the syntax of a well defined programming language for writing the pseudo code. D.Lazard ( talk) 11:23, 20 June 2015 (UTC)
Sorry, I'm not entirely following. By Church and Russell, do you mean Church and Turing? There is also a technical/mathematical error in your statement. The class of functions computed by Turing machines are the same as the class of functions that are computed by automata as Turing machines are a type of automata (albeit the most powerful type, as opposed to finite state automata, push-down automata, etc. which are subclasses). In any event, I don't think this helps the non-technical reader who just wants to get a clear idea about what the Church-Turing thesis is without chasing many Wiki links to other technical subjects.
Also, while I admit that the section on Informal Proofs is a bit wordy and perhaps not all that relevant, it is accurate as far as the example given goes. When the section argues that a formal proof would require (e.g) showing that a Turing machine could be constructed, this is equivalent to your requiring pseudo code for a suitable abstract machine. I'm afraid I don't understand your concern. Ross Fraser ( talk) 04:04, 26 June 2015 (UTC)
For references on the relationship between Turing's thesis and human computers, here are three good sources:
The short summary is that, at the time Turing was writing, the word "computer" itself referred to a human computer, and that this notion was what Turing was seeking to analyze. Turing's analysis of the Entscheidungsproblem relied on his analysis of what a human could compute, and his argument that this notion of computability was captured by a Turing machine. Indeed, as Copeland writes in the SEP article linked above, "The Turing machine is a model, idealised in certain respects, of a human being calculating in accordance with an effective procedure". — Carl ( CBM · talk) 13:18, 20 June 2015 (UTC)
Here is an example in Turing's own words: "A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine." (‘Intelligent Machinery’. National Physical Laboratory Report. 1948. In Meltzer, B., Michie, D. (eds) 1969. Machine Intelligence 5. Edinburgh: Edinburgh University Press. http://www.AlanTuring.net/intelligent_machinery
It shouldn't be surprising that Turing was referring to humans and not computers when he wrote in 1936 as computers weren't around then. After all, Turing was one of the people who invented them. Ross Fraser ( talk) 02:49, 26 June 2015 (UTC)
Hello fellow Wikipedians,
I have just modified 2 external links on Church–Turing thesis. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 5 June 2024).
Cheers.— InternetArchiveBot ( Report bug) 13:41, 7 August 2017 (UTC)
The philosophical implications paragraph begins with this sentence: Philosophers have interpreted the Church–Turing thesis as having implications for the philosophy of mind; however, many of the philosophical interpretations of the Thesis involve basic misunderstandings of the thesis statement.
The only cite is a somewhat vaguely-worded bit of prose that says In particular, see the numerous examples (of errors, of misappropriation of the thesis) at the entry in the Stanford Encyclopedia of Philosophy. For a good place to encounter original papers see David J. Chalmers, ed. 2002, Philosophy of Mind: Classical and Contemporary Readings, Oxford University Press, New York.
This gives the impression that the sentence was written by an editor who then pointed to arguments they personally felt were based on errors or misappropriation, which is obviously
original research. Do we have any sources specifically saying that the Church-Turing thesis has been frequently misunderstood by philosophers? --
Aquillion (
talk)
01:57, 11 October 2017 (UTC)
I removed the following paragraph from the text:
"Kleene himself never stated that Turing had made a mistake in his paper, important in its own right for helping to establish the unsolvability of problems in group theoretic computations, although corrections to Turing's paper were also made later by Boone who originally pointed out "points in the proof require clarification, which can be given"[34] and Turing's only PhD student, Robin Gandy. That Kleene doesn't mention this mistake in the body of his textbook where his presents his work on Turing machines but buried the fact he was correcting Alan Turing in the appendix was appreciated by Turing himself can be surmised from the ending of Turing's last publication "Solvable and Unsolvable Problems" which ends not with a bibliography but the words,"
It wasn't clear at all from the context what the mistake being referred to was. The paragraph also ends mid-sentence. If anyone can find the context and conclusion, feel free to add it back. (Assuming it's worthy of inclusion.)-- Rxtreme ( talk) 04:57, 14 July 2018 (UTC)
In the history section, the text quotes Kleene, who himself uses citations. These citations are given here in parentheses which are then specified after the quote. For example:
"'This heuristic fact [general recursive functions are effectively calculable] ... led Church to state the following thesis(22). The same thesis is implicit in Turing's description of computing machines(23)...'
(22) references Church 1936;[not specific enough to verify] (23) references Turing 1936–7 Kleene goes on to note that:"
This is really difficult to follow. Does Wikipedia have a policy for quoting text with citations in it? One way or another, there has to be a better way than what the article is doing.-- Rxtreme ( talk) 05:07, 14 July 2018 (UTC)
I see the paragraph "One can formally define functions that are not computable. A well-known example of such a function is the Busy Beaver function. This function takes an input n and returns the largest number of symbols that a Turing machine with n states can print before halting, when run with no input. Finding an upper bound on the busy beaver function is equivalent to solving the halting problem, a problem known to be unsolvable by Turing machines. Since the busy beaver function cannot be computed by Turing machines, the Church–Turing thesis states that this function cannot be effectively computed by any method."
But this is trivial - the largest possible loop is n-1 states (-1 because one of the states is the halting state). therefore if it doesn't loop it is n or less states long and the final state is the halting state. The state transitions depend entirely on the initial state. And a turing machine that can run it as a virtual machine can determine if it halts (from whatever initial state it starts in) in N or less steps of the virtual machine. less if it repeats a state - because if and only if it repeats a state does it loop. Kevin Baas talk 18:59, 3 December 2021 (UTC)
![]() | This ![]() It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
I just made my best effort to rewrite the introduction. Judging from the comments below, the introduction has been in need of revision by an expert for quite some time, i.e., someone who could rewrite it with confidence, rather than just trying to sort of preserve and polish what was there. Still, I tried to stay true to the spirit of the original as far as possible, and re-used as much as possible --- I also borrowed at least one sentence from the article on computable functions.
I got rid of some pseudo-terminology such as "combined hypothesis", which does not mean anything as far as I was able to determine, except perhaps in statistics. I tried to be slightly more precise in the description of the three formally defined classes of computable functions (lambda definable, Turing definable, and general recursive) - in particular, the first two of these classes require an encoding of the natural numbers (either as lambda terms, such as the Church numerals, or as symbols on a tape of the Turing machine). The old intro had glossed over this a bit too much in my opinion --- although certainly I am also only alluding to it and not giving fully formal definitions. I tried to strike a balance between concision and precision. To see the full and precise definitions, the readers will have to follow the links to the respective articles.
I also renamed the next section "Statement in Church's and Turing's words", because that is exactly what the section contains. The old title, "Formal Statement", didn't make sense, because by its nature, the Church-Turing thesis is an informal statement that can never be formalized. Selinger ( talk) 00:17, 25 August 2014 (UTC)
I'm not sure why we even bother with a link to nonsense about Burgin's supposed refutation of the thesis. If anyone is in for a good laugh, skim through the appallingly poorly written The rise and fall of the Church-Turing Thesis. [1] To quote his modest conclusion:
...riiiight... His work is almost universally regarded, at best, as something between a misunderstanding, a new word for an old concept and a marketing fraud. See for instance Martin Davis' unkind review of Burgin's book [2] and his description of Burgin's misunderstanding [3]. Pascal.Tesson ( talk) 19:34, 7 February 2008 (UTC)
I have removed the following paragraphs:
One conclusion to be drawn is that, IF a computer can effectively calculate an algorithm THEN so can an equivalent Turing Machine. But the converse is not true: It is NOT true that IF a Turing machine can calculate an algorithm THEN so can a computer; no computer is as computationally powerful as a Turing Machine since a computer does not have the required infinite memory nor infinitely-sized variables.
Thus it is not possible to build a calculation device that is as powerful as the simplest theoretical computing mechanism (a Turing machine). Note that this formulation of power disregards practical factors such as speed or memory capacity; it considers all that is theoretically possible, given unlimited time and memory.
Why? Because 1. it is poor style to shout (uppercase) in an encyclopedic article, and 2. it is false and obviously stems from a a poor understanding of the subject matter. A Turing Machine (TM) is not the simplest theoretical computing machine (e.g. finite automaton is far weaker). In fact, a TM is the most complex abstract computing machine known to mathematicians and computer scientists. Now, a TM does not suppose infinite time nor memory. A TM is one (the most successful in many mathematicians opinion) formalization of the concept algorithm, and as such is inherently infinite viewed as a set of input/output pairs. On the other hand, the computation of an output from an input is always finite, and if a computation can be effected on a TM, then it can on a regular computer to. Finiteness (of its description) is part of the TM's definition, and it can always be simulated in any standard computer programming language. Hence the computation can theoretically be done on a computer if it can be done on a TM, and vice versa.
Note that a TM should not be thought of as a physical machine, but as a formal mathematical object intended for reasoning about algorithms, i.e. how a physical computer works. It is thus in a sense true that a TM disregards practical factors such as time and space, but only because they are not attributes of the concept algorithm. On this conceptual level it is the dicotomy finite/infinite which is essential, and this issue is indeed properly covered by the TM theory. Time and space considerations enters when one attempts to analyze one specific algorithm: they are attributes of the concept computation. Barra ( talk) 16:24, 5 March 2008 (UTC)
The term Church's thesis (CT) is used in intuitionistic logic to describe an additional axiom, saying that all functions are computable. There should be either a pointer in the introduction or a disambiguation page. -- Thorsten ( talk) 15:59, 6 March 2008 (UTC)
To keep the discussion together in one place, I will remove this duplicate section and point to the discussion on this exact topic at Talk:Algorithm#A_paradoxical_situation. — Carl ( CBM · talk) 20:38, 19 March 2008 (UTC)
I removed (perhaps not the first time) a claim that the CT thesis somehow depends on the definition of algorithm. This isn't true; the CT thesis is a specific claim about one specific meaning of algorithms, the one that is discussed in the introductory part of any recursion theory text. It is trivially possible to make the "other CT theses" true or false if other definitions were employed; but those other versions are not "the Church-Turing thesis". That is about a specific notion of algorithm and a specific notion of computability. — Carl ( CBM · talk) 10:53, 9 May 2008 (UTC)
Is it just me, or are there other mathematicians out there that regard the Church-Turing thesis as nonsense? The phrase'effectively calculable' is only defined in terms of other English words, which are themselves not defined. The author then seems to lose interest in the pretence of rigour by not defining the word 'machine'. —Preceding unsigned comment added by 86.9.138.200 ( talk) 20:02, 7 October 2008 (UTC)
Have anyone tried to disprove Turing thesis by pointing to analog computers? Analog computation yields results in form of real numbers while Turing machine is obviously not capable of computing with this kind of "infinite precision". Martin. —Preceding unsigned comment added by 85.216.202.14 ( talk) 22:09, 11 October 2008 (UTC)
Hm, it doesn't look like the restriction to the domain of natural numbers is mentioned anywhere on the web page. Even "effectively calculable" page seems to ignore the restriction:
An effective method (also called an effective procedure) for a class of problems is a method for which each step in the method may be described as a mechanical operation and which, if followed rigorously, and as far as may be necessary, is bound to:
I'm a little troubled by the formatting here. Shouldn't the title have a hyphen-minus in it instead of an en-width dash? And, also, full spaces around the em-width dashes in the article body are not so good. 66.102.80.246 ( talk) 03:04, 13 October 2008 (UTC)
I would like to suggest removing the phrase "in more modern terms" be removed from the opening sentence ("In computability theory, the Church–Turing thesis (also known as the Turing–Church thesis,[1] the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a combined hypothesis ("thesis") about the nature of functions whose values are effectively calculable; or, in more modern terms, functions whose values are algorithmically computable."). The description "effectively calculable" is not archaic and "algorithmically computable" is more of a computer science preference than a more precise term.
Instead, I suggest: "In computability theory, the Church–Turing thesis (also known as the Turing–Church thesis,[1] the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a combined hypothesis ("thesis") about the nature of functions whose values are effectively calculable (also called functions whose values are algorithmically computable).
Jimperrywebcs ( talk) 16:02, 2 May 2014 (UTC)
I am moving this section out of the article until I have time to fix it. The idea that Turing machines do not actually model real computers is a very uncommon POV. Many CS books will state that Turing machines are indeed a theoretical model of real computers, in which resource limitations have been removed. The idea that input/output prevents Turing machines from modeling computers is odd, since an oracle Turing machine can view the tape as a sequence of inputs coming from a console, and read from the oracle tape whenever it desires more input. — Carl ( CBM · talk) 12:56, 24 October 2008 (UTC)
In what has been called the "Turing thesis myth," [6] [7] the Church-Turing thesis has often been misinterpreted as a claim that real computers can be modeled as Turing machines. This is incorrect. The Church-Turing thesis concerns the computability of mathematical functions. Real computers may do input and output continuously during computation, and thus are modeled as interaction machines, a model distinct from and not reducible to the Turing machine. However, a Turing machine does model what a computer can do between any input and output events. For formal models of computers with input and output functionality, see super-recursive algorithm, and anytime algorithm.
In my opinion, this article is very hard to understand. Most of the questions I had before coming here are still unanswered after reading it, and worst: now I'm confused. Someone with a strong background in this area, please rewrite this article in a more clear, helpful way.
I am going to work on rewriting the lede, and moving much material out of it ot he main article. The lede is meant to be a summary of the article in plain language, so that even someone who can't read the whole article can get a sense of what's going on from the lede. The present lede has 15 footnotes and focuses primarily on historical terminology; it needs to be more concise and direct. — Carl ( CBM · talk) 12:50, 24 October 2008 (UTC)
I have been reading up on various aspects of the Church-Turing thesis and I am almost at a point where I can start to do some significant work on this article. It's been on my plans for a while, but I thought I should go ahead and point out those plans to everyone else.
In the article as it stands, much of the important information is present, but the organization is not optimal, and some important things are missing. If it were graded as an undergraduate essay, I do not think it would get an A. I'd like to improve the article so that it would be an obvious A. Here are some of the issues that I would like to address.
It will be a while before I have the time to really dig into this article, but I think it is a place where, with some more work, we can get an exceptional article that will be extremely informative and beneficial to many readers. — Carl ( CBM · talk) 11:03, 14 September 2009 (UTC)
Carl, if you can recommend any contemporary readings I'm interested. I've read the Gandy and Seig papers but I need something with a broader brush. (Kalmár's proof sounds really interesting, can this be found anywhere but a library? In the process of a google-hunt I ran into this: http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.ndjfl/1093637645. Here Kleene 1987 at the very end of his paper, says he heard Kalmar give a talk about his proof and was going to publically punch a hole in his "proof" . . .but:
Thanks, Bill Wvbailey ( talk) 19:36, 15 September 2009 (UTC)
I think I found a pretty good paper. It was published in a journal that also published some hypercomputation crankyness, but this paper is not of that kind. I like it that it clearly distinguishes between human-CTT and physical-CTT. Soare's paper also does this, but the discussion is less clear there. Official ref is: Antony Galton, The Church–Turing thesis: Still valid after all these years?, Applied Mathematics and Computation, Volume 178, Issue 1, 1 July 2006, Pages 93-102 Pcap ping 09:58, 17 September 2009 (UTC)
Rewrite of Intro
As the plans described above seem to be on hold (it's now April 2010), I've reorganized the intro to improve it's readability for the casual reader who doesn't need/want to read further than the intro. I've also linked to the Wikipedia article on computability. I'll wait a few months before editing further to see if any of the plans above come to fruition. Ross Fraser ( talk) 07:57, 21 April 2010 (UTC)
What appears to be a rewrite of the wiki Church-Turing thesis article appears here: http://www.fact-archive.com/encyclopedia/Church-Turing_thesis. It's interesting to see their crack at it. Wvbailey ( talk) 21:47, 15 September 2009 (UTC)
Should we be that cautions here? See Quantum computing#Developments. Pcap ping 18:44, 15 September 2009 (UTC)
Humph. Given certain assumptions about the answers to certain unsolved physics problems leads to the ability to solve the halting problem for the Turing machine. Therefore, this thesis is not proved. 75.45.17.132 ( talk) 02:54, 6 December 2009 (UTC)JH
This change replaced Strong Church Turing Thesis" with "Complexity-theoretic Turing Thesis" claiming that "strong" is a weasel word. I've reverted it because WP:WEASEL does not apply to terminology quoted as such. Pcap ping 04:53, 8 December 2009 (UTC)
Maybe somebody could clarify for me – I am not deeply into computer science – I thought the "Strong Church-Turing thesis" is that any reasonable deterministic universal computation system can simulate any other reasonable deterministic universal computation system with a polynomial gain in execution time. — Carl ( CBM · talk) 22:04, 8 December 2009 (UTC)
Certainly we cannot call it "Computational Complexity-Theoretic Church-Turing Thesis" if no-one else calls it that: few Google hits, 0 Google Scholar hits, 1 hit in Google Books. The article claims that "This thesis was originally called Computational Complexity-Theoretic Church–Turing Thesis by Ethan Bernstein and Umesh Vazirani (1997)". However, the original paper does not seem to use exactly this term; it uses more vague and variable phrases such as "the modern (complexity theoretic) formulation of the Church–Turing thesis", "a modern strengthening of this thesis", "the complexity-theoretic form of the Church–Turing thesis", and "the modern form of the Church–Turing thesis". — Miym ( talk) 22:58, 8 December 2009 (UTC)
By the way, for some reason I have got the impression is that only quantum computing people have ever claimed that there exists a "strong CT thesis", and the only reason for them to define it is to show how to refute it. Did the strong CT thesis really exist before the quantum computing era? Did someone present it before they knew how to refute it? Using a quantum computing book as a source does not really help to convince me... — Miym ( talk) 23:00, 8 December 2009 (UTC)
Peter Wegner and Dina Goldin have written several papers about the C-T thesis, claiming a generalized misunderstanding of its meaning among CS theory [9] and showing how it could be superseded by the interactive computation model. [10] In particular, the "driving home for work" problem (creating a computer system to control an automatic car through real traffic) shows a simple and clear example of a computable task that cannot* be solved by a Turing machine but can be "solved" (for some particualr meaning of "solve" and "computable") by an interactive program.
(*using the classical definition of a TM, where all input is given at the beginning).
Does anyone know which ones are the most relevant articles from Wegner, and whether it has been criticized by others? I think stating the "driving home" problem would be a good addition to this article, to show what are the concerns of people opposing the C-T thesis. Diego ( talk) 15:39, 22 March 2010 (UTC)
While it is true that oracle Turing machines are perfectly capable of solving problems requiring repeated input, this is not really relevant to the ordinary Church-Turing thesis. As Wegner and Goldin say,
But this "limitation" is a key part of the Church-Turing thesis. The ordinary Church-Turing thesis is what they call the "Turing thesis":
It would be perfectly reasonable for this article to mention Wegner and Goldin in the section "variations", but not in the top part, which is about the ordinary thesis, namely
It is obvious that there are "algorithms" that are unrelated to computing functions and which cannot be done by a Turing machine. For example, I can write an algorithm to make a good martini. This is why the ordinary thesis is limited to only considering number-theoretic functions. I do not believe Wegner and Goldin argue that this usual version of the thesis is incorrect, and indeed they affirm the thesis in the form "TMs can compute any algorithmic problem." The issue, as they point out in their papers, is that in order to use Turing machines one must first correctly represent the problem to be solved as a function problem. — Carl ( CBM · talk) 00:57, 24 March 2010 (UTC)
I wonder why people continue to say “Church-Turing thesis,” instead of, say, “Dershowitz-Gurevich Theorem” ?
Dershowitz and Gurevich axiomatized the notion of “effectively calculable” using abstract state machines, and proved both Church’s thesis (all effectively calculable (partial) functions are general recursive) and Turing’s thesis (the effectively calculable functions are exactly those which can be programmed on a Turing machine).
I don’t understand why this paper, published in the Bulletin of Symbolic Logic in 2008, isn’t famous. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402
199.212.17.130 ( talk) 11:09, 20 August 2010 (UTC)
I removed some link to a paper about the Actor model. The link was to an unpublished paper by Carl Hewitt about the Actor model. Editors who are unaware should consult the related arbitration case. The outcome of that case authorizes the removal of this sort of material.
However, I think it is important to point out the mathematical reason this material is not included, so that it is more clear why the material isn't appropriate for this article.
The idea that concurrency is related to the Church-Turing thesis is not in agreement with the vast majority of literature on the thesis. The thesis says that any number theoretic function that is computable by a human using paper and pencil is computable by a Turing machine. The thesis is not related to methods of computation, and it does not refer to computations that are not functions or to computations that would require human beings to use special equipment.
The example that Hewitt gives in the unpublished paper is a nondeterministic process that does the following:
Hewitt's model corresponds to a post office that can deliver letters out of order and that can delay any letter indefinitely. So, with those assumptions, it is clear that the number you have in x when you receive the "stop" message will depend on the order in which you receive the letters you have sent. Indeed, any particular number is possible, depending on how pathological the postman is. There is nothing contradictory about this.
But that example has nothing at all to do with computing a function. Indeed, if different invocations of the same process can produce different outcomes, then you are definitely not computing a function, full stop. Moreover, the example is not an algorithm that a human can theoretically carry out using paper and pencil alone. It requires some element of randomness, but an "algorithm" in the sense of the Church-Turing thesis needs to be explicit to the point that a human can follow it without needing to ask for additional information apart from the input of the function. — Carl ( CBM · talk) 23:46, 19 November 2010 (UTC)
If Church were around, he would agree with Hewitt, Milner, and Hoare that the lambda-calculus left out something important for effective computation. The interesting thing is that these modern theorists were able to formally prove and precisely indentify how nondeterministic Turing machines are lacking in computational power that is important in modern computing for networking and many-core systems. Of course, their work is highly relevant to meainstream understanding of the notion of effective computation that Church et. al. were trying to formalize. Actor Model of Computation has an explanation of how the modern work relates to the older Church/Turing/Rosser results:
Milner, Hoare, etc. have published similar results.
You don't seem to understand how ridiculous it is to try to represent an operating system as a recursive function. 171.66.73.165 ( talk) 03:25, 20 November 2010 (UTC)
The material was added again, and remove again. If the material is added a third time, I will take the unfortunate step of protecting the page from editing by IP editors, in accordance with the arbitration case linked above. The work of Hewitt and others is perfectly valid and reasonable; that is not at issue here. The issue is that nondeterminism is not related to the Church-Turing thesis, which is about the computation of functions, not about about computation in general. — Carl ( CBM · talk) 23:21, 21 November 2010 (UTC)
The Church Turing thesis has an important history in computer science. See What is computation? Concurrency versus Turing's Model from the article published in Arxiv (a somewhat competitor to Wikipedia that is often censored here). 76.254.235.105 ( talk) 23:13, 28 November 2010 (UTC)
I have tried to arrange the messy paragraph involving super-recursive, or hyper-Turing, computation. I moved the claims attributed to Eberbach and Wegner to an earlier section, and rephrased them following their article. I removed the claims attributed to Peter Kugel since his article, cited in the reference section, does not support was has been written in his name. I did not touch the text referring to Mark Burgin's claims as I do not have his book at hand, but it should be removed if it cannot be verified. AmirOnWiki ( talk) 14:42, 14 October 2011 (UTC)
The article is perfectly fine. That said, the Church-Turing thesis is nothing but a normal math definition, like any other, e.g. the epsilon-delta definition of a continuous function. Maybe this should be mentioned more clearly in the article. See e.g. R. I. Soare, 1996. Computability and recursion, Bulletin of Symbolic Logic v. 2 pp. 284–321(?). — Preceding unsigned comment added by DanielVallstrom ( talk • contribs) 18:04, 29 January 2012 (UTC)
There is an incorrect definition of the Church Turing thesis here Turing_(disambiguation)-- Mongreilf ( talk) 21:37, 18 June 2012 (UTC)
Indeed Mongreilf. Why don't you fix it? ;) Anyway, I changed the explanation of the Church-Turning thesis to "the hypothesis that everything computable is computable by a Turing machine" --- despite the fact that arguably that explanation is close to nonsense in the sense that one should rather view the thesis as nothing more than a normal math definition. Daniel Vallstrom ( talk) 14:58, 20 June 2012 (UTC)
Is the Physical Church–Turing thesis (PCTT) equivalent to the Church–Turing–Deutsch principle? Bayle Shanks ( talk) 08:20, 26 May 2013 (UTC)
In the bullet list of the lede, the second item reads: British mathematician Alan Turing created a theoretical model for a machine, now called a universal Turing machine, that could carry out calculations from inputs.
Though technically correct, I think this is somewhat confusing for readers new to the topic. It sounds as if Turing had taken someone else's earlier concept of "a Turing Machine" and only specified the "universal Turing machine" from that concept. Would there be a major problem with writing "..., now called a Turing machine, ..."?
I understand that this may slightly reduce historical correctness. However, the rest of the lede only talks about "the Turing machine" and gives no dates whatsoever, so it isn't terribly historically correct anyway ;-) (And that's perfectly fine! The lede is not the place for historical details.) Therefore, I think new readers would benefit from the change, and anyone familiar with the concept won't suffer. And it's the new readers for whom the lede is written, right?
Agree / Disagree, anyone? -- Se'taan ( talk) 00:48, 28 September 2013 (UTC)
Agree. The term 'universal' specifies Turing machines capable of simulating others, like a compiler or an interpreter. Which seems confusing, and beside the point. I'll change it.
Ummm... the line after is also wrong. The recursive functions are due to Gödel, with Herbrand, not Church et al., I'm pretty sure. I'll fix that too. Daniel Vallstrom ( talk) 08:28, 28 September 2013 (UTC)
--- Backup:
Here comes probably the most frequent dispute in writing about the Church-Turing thesis: Shouldn't we settle on an easily distinguished name for the "intuitive notion of computability" and "the notion captured by the formalisms"? I don't mean "we" as in "the scientific world", but as in "the whole of Wikipedia, even if the scientific world hasn't yet settled". The biology articles about some species (and about the term "species") sometimes do this, too, even though there is no universally accepted usage of the terms. They do it just so the articles get better, and these articles state this usage in wikipedia as "nonstandard, but only because nothing's yet agreed upon".
I know it may seem to be a stickler's question, but this is particularly disturbing when reading several articles about computability, and they all use different meaning for those words. I was working on Effective method which shortly mentions the Church-turing thesis. That article makes a distinction, introduced [13] by User:Lambiam on the edit of User:CBM, which is "effectively calculable" for the "intuitive" notion and "effectively computable" for that of the formalisms. Likewise, Effectively calculable redirects to Effective method, whereas Effectively computable redirects to Computable function (as does Total recursive function, so I guess Computable function should descibe the formal notion, which I think it does. Someone please give me a reality check if this is not the case).
To put it in short: Should we rewrite the lead so that it consequently uses "calculable" to mean "calculable with some effective method" and "computable" to mean "computable with a Turing machine"? Note that we make a more clear description of Effective method at the very article. This is not merely an "intuitive" notion, there is some agreement on it. It's just not a full formal definition.
On a different matter, maybe someone could help me out: Does the Church-Turing thesis only apply to the computability of number-theoretic functions, or of functions in general? See Talk:Effective method#Is the Church-Turing thesis restricted to number-theoretic functions?. I need to edit this in [Effective method]], and you'll stumble across that sentence anyway when you look at the article. Thanks! -- Se'taan ( talk) 01:18, 30 September 2013 (UTC)
Goodness me, what a load of Russell-like sophistry this article is. There is still no real definition of of finite, that is a finite number of steps to prove a theory. Kantor got it right when he devised an algorithm to count all of the rational numbers between 0 and 1. While the number of rationals is bigger than any number you can specify (i.e. show it explicitly). Why all this nonsense about Turing machines? Does it have a clock tick time of 0 seconds? Is the Turing machine a discrete state machine? If not, then what it does is not countable. SHEESH!!! 27.33.243.64 ( talk) 09:48, 15 December 2015 (UTC)
What is the appropriate term, a dissertation or a thesis? UK convention is that a thesis is to obtain a Doctorate degree and dissertation to complete a Master's. The US convention is the reverse – a dissertation is written for a PhD and a thesis for a Master’s.
Turing was British but obtained his PhD from Harvard in the US. -- TedColes ( talk) 08:54, 19 February 2014 (UTC)
American school, so American definition, no? Zenten ( talk) 10:34, 7 August 2019 (UTC)
There are several missing references to Sieg's papers. These references appear in many footnotes but no Sieg papers appear in the References section of the article. There may be other missing or obscured references and this should be thoroughly checked. For example, there are several references to "Barwise 1980" in the footnotes, but there is no actual stand-alone References entry to that work; instead it appears buried in the Reference for Grady, 1980. Lesgasser ( talk) 17:43, 26 July 2014 (UTC)
There are also an "extended form" of the thesis.
As comment by recently by P. Shadbolt et all (in DOI:10.1038/NPHYS2931) "Famously, the extended Church–Turing thesis (ECT) says that all computational problems that are efficiently solvable with realistic physical systems can be efficiently solved with a classical machine — a statement clearly in conflict with our hopes for the capabilities of quantum computers", Shor, P. W. in Proc. 35th Ann. Symp. Found. Comput. Sci. 124–134 (IEEE, 1994). -- Krauss ( talk) 03:09, 14 December 2014 (UTC)
As BQP != BPP was proven in the last few years (2018 I think) the extended Church-Turing thesis must be invalidated. There are problems with efficient solutions in BQP (quantum computations) without efficient solutions on a probabilistic Turing machine. — Preceding unsigned comment added by 2A00:23C4:8585:7D01:1C42:5F57:F923:8501 ( talk) 14:50, 19 February 2021 (UTC)
SMmoto is correct that by 1939 both Church and Turing were well aware of each other's work -- but to accept Turing's paper (1936) Church was the only possible referee, and he had already published (paper appeared) on 15 April, pre-empting Turing by . To quote Hodges: "A new idea had found its way into two human minds simultaneously and independently" (Hodges 1983:111). For Hodges' take on the entire sequence of events see Hodges 1983:111-113. I also remember reading somewhere that a "certification process" had to occur after which the paper was accepted on 28 May 1936 to the London Mathematical Society. Hodges isn't so clear on this. If I find out what happened, I'll add it here. Bill Wvbailey ( talk) 17:19, 2 February 2015 (UTC)
This article does not respect the fundamental principle of Wikipedia the articles must have a neutral point of view in fact, the point of view of the philosophers and logicians are presented in full details, while the point of view of computer scientists is totally lacking. This is amazing, when considering the importance of computer science and the fact that Church and Russell are unanimously considered as being among the founders of theoretical computer science. This point of view may be summarized as follows:
In theoretical computer science, the original Church–Turing thesis has been extended into the (clearly unprovable) principle (also called Church–Turing thesis) that every possible model of computation computes only Turing-computable functions. This principle is supported by the fact that all models of computations that have ever been proposed compute either exactly the same functions as Turing machines (such are recursive functions, lambda calculus, and also random-access machines and quantum computers), or a subclass of the Turing computable functions (such as primitive recursive function and automata).
For being useful for readers interested in computer science, the lead must include something like that (preferably with shorter sentences and less parentheses). The body of the article must also be edited to expand this sentence and correcting some errors introduced by this non-neutral point of view. For example, in section "Informal usage in proofs", the description of what is needed to have a formal proof of the example is wrong. For having a formal proof, it suffices to write the algorithm in the programming language of an abstract machine that has been already proved as equivalent (in the sense of Turing–Church thesis) to a Turing machine. This is essentially what is called pseudocode, when one use the syntax of a well defined programming language for writing the pseudo code. D.Lazard ( talk) 11:23, 20 June 2015 (UTC)
Sorry, I'm not entirely following. By Church and Russell, do you mean Church and Turing? There is also a technical/mathematical error in your statement. The class of functions computed by Turing machines are the same as the class of functions that are computed by automata as Turing machines are a type of automata (albeit the most powerful type, as opposed to finite state automata, push-down automata, etc. which are subclasses). In any event, I don't think this helps the non-technical reader who just wants to get a clear idea about what the Church-Turing thesis is without chasing many Wiki links to other technical subjects.
Also, while I admit that the section on Informal Proofs is a bit wordy and perhaps not all that relevant, it is accurate as far as the example given goes. When the section argues that a formal proof would require (e.g) showing that a Turing machine could be constructed, this is equivalent to your requiring pseudo code for a suitable abstract machine. I'm afraid I don't understand your concern. Ross Fraser ( talk) 04:04, 26 June 2015 (UTC)
For references on the relationship between Turing's thesis and human computers, here are three good sources:
The short summary is that, at the time Turing was writing, the word "computer" itself referred to a human computer, and that this notion was what Turing was seeking to analyze. Turing's analysis of the Entscheidungsproblem relied on his analysis of what a human could compute, and his argument that this notion of computability was captured by a Turing machine. Indeed, as Copeland writes in the SEP article linked above, "The Turing machine is a model, idealised in certain respects, of a human being calculating in accordance with an effective procedure". — Carl ( CBM · talk) 13:18, 20 June 2015 (UTC)
Here is an example in Turing's own words: "A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine." (‘Intelligent Machinery’. National Physical Laboratory Report. 1948. In Meltzer, B., Michie, D. (eds) 1969. Machine Intelligence 5. Edinburgh: Edinburgh University Press. http://www.AlanTuring.net/intelligent_machinery
It shouldn't be surprising that Turing was referring to humans and not computers when he wrote in 1936 as computers weren't around then. After all, Turing was one of the people who invented them. Ross Fraser ( talk) 02:49, 26 June 2015 (UTC)
Hello fellow Wikipedians,
I have just modified 2 external links on Church–Turing thesis. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 5 June 2024).
Cheers.— InternetArchiveBot ( Report bug) 13:41, 7 August 2017 (UTC)
The philosophical implications paragraph begins with this sentence: Philosophers have interpreted the Church–Turing thesis as having implications for the philosophy of mind; however, many of the philosophical interpretations of the Thesis involve basic misunderstandings of the thesis statement.
The only cite is a somewhat vaguely-worded bit of prose that says In particular, see the numerous examples (of errors, of misappropriation of the thesis) at the entry in the Stanford Encyclopedia of Philosophy. For a good place to encounter original papers see David J. Chalmers, ed. 2002, Philosophy of Mind: Classical and Contemporary Readings, Oxford University Press, New York.
This gives the impression that the sentence was written by an editor who then pointed to arguments they personally felt were based on errors or misappropriation, which is obviously
original research. Do we have any sources specifically saying that the Church-Turing thesis has been frequently misunderstood by philosophers? --
Aquillion (
talk)
01:57, 11 October 2017 (UTC)
I removed the following paragraph from the text:
"Kleene himself never stated that Turing had made a mistake in his paper, important in its own right for helping to establish the unsolvability of problems in group theoretic computations, although corrections to Turing's paper were also made later by Boone who originally pointed out "points in the proof require clarification, which can be given"[34] and Turing's only PhD student, Robin Gandy. That Kleene doesn't mention this mistake in the body of his textbook where his presents his work on Turing machines but buried the fact he was correcting Alan Turing in the appendix was appreciated by Turing himself can be surmised from the ending of Turing's last publication "Solvable and Unsolvable Problems" which ends not with a bibliography but the words,"
It wasn't clear at all from the context what the mistake being referred to was. The paragraph also ends mid-sentence. If anyone can find the context and conclusion, feel free to add it back. (Assuming it's worthy of inclusion.)-- Rxtreme ( talk) 04:57, 14 July 2018 (UTC)
In the history section, the text quotes Kleene, who himself uses citations. These citations are given here in parentheses which are then specified after the quote. For example:
"'This heuristic fact [general recursive functions are effectively calculable] ... led Church to state the following thesis(22). The same thesis is implicit in Turing's description of computing machines(23)...'
(22) references Church 1936;[not specific enough to verify] (23) references Turing 1936–7 Kleene goes on to note that:"
This is really difficult to follow. Does Wikipedia have a policy for quoting text with citations in it? One way or another, there has to be a better way than what the article is doing.-- Rxtreme ( talk) 05:07, 14 July 2018 (UTC)
I see the paragraph "One can formally define functions that are not computable. A well-known example of such a function is the Busy Beaver function. This function takes an input n and returns the largest number of symbols that a Turing machine with n states can print before halting, when run with no input. Finding an upper bound on the busy beaver function is equivalent to solving the halting problem, a problem known to be unsolvable by Turing machines. Since the busy beaver function cannot be computed by Turing machines, the Church–Turing thesis states that this function cannot be effectively computed by any method."
But this is trivial - the largest possible loop is n-1 states (-1 because one of the states is the halting state). therefore if it doesn't loop it is n or less states long and the final state is the halting state. The state transitions depend entirely on the initial state. And a turing machine that can run it as a virtual machine can determine if it halts (from whatever initial state it starts in) in N or less steps of the virtual machine. less if it repeats a state - because if and only if it repeats a state does it loop. Kevin Baas talk 18:59, 3 December 2021 (UTC)