Talk:Church–Turing thesis

Rewrote introduction

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)

Thank you Selinger, the article is much improved. Turing completeness badly needs similar treatment. --TedColes (talk) 07:57, 25 August 2014 (UTC)

Burgin's theory

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:

We may compare these three approaches to what we have in our everyday life. From this perspective, DNA computing is like a new model of a car. Quantum computations are like planes at the stage when people did not have them. At the same time, super-recursive computations are like rockets, which can take people beyond the “Church-Turing Earth”. Thus, it is possible to say that we have rockets that might take us to the Moon and even to other planets of the Solar system if we know how to navigate them. However, we will need new physical ideas for realization of super-recursive algorithms to a full extent. Using our metaphor, we may say that spaceships that will take us to stars are now only in perspective.

...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)

Most likely this should be discussed in conjunction with hypercomputers; I need to pick up Burgin's book from the library to make sure. It's well known that if you eliminate the any of the requirements {discrete, finitistic, deterministic} from the definition of algorithm then you can get a broader class of functions. So It's not nonsense; but all the previous work I have seen relies on a nonstandard reading of Church's thesis to argue that Church's thesis is incorrect. — Carl (CBM · talk) 19:44, 7 February 2008 (UTC)

It appears from this arxiv paper that Burgin is interested in, among other things, limit recursive functions. It is very well known that there are limit recursive (i.e. $\Delta _{2}^{0}$) functions that are not computable; the common belief is that this does not impinge on Church's thesis. — Carl (CBM · talk) 19:50, 7 February 2008 (UTC)

Misunderstanding

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.

Whether uppercase is "shouting" is a matter of cyber-youth opinion only, but clearly the typography is not the issue, the UC could be changed to LC italic). BillWvbailey (talk) 18:45, 6 March 2008 (UTC)

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)

I agree here; a Turing machine does not have an infinite memory, but rather an indefinitely-extendible finite memory. It is certainly possible to literally build a Turing machine, if desired. — Carl (CBM · talk) 17:16, 5 March 2008 (UTC)

The statement was correct as it stands. Carl, I've built "TM's" both in hardware and software, and programmed the U on my little hardware machine. What these devices lacked was extensible memory, under any conditions that the machine requires (without interference). These machines do not exist except in concept. In theory my little machine could have computed any computable algorithm, excepting for the memory restriction. I do not understand your objections to what is written there. It is correct. If it is computable, a TM can compute it. If it is computable, a computer cannot necessarily compute it. The TM is sufficient; the computer is not. Bill Wvbailey (talk) 16:05, 6 March 2008 (UTC)

I was referring to this sentence: "Thus it is not possible to build a calculation device that is as powerful as the simplest theoretical computing mechanism (a Turing machine).". Since it is literally possible to build a Turing machine, this sentence isn't optimally worded.

One common way to define what it means for a Turing machine to compute something is that if the machine is provided with additional tape whenever required, it will perform correctly (cf. Davis, 1958, p.6). If the tape is not provided, that doesn't show that the result can't be computed, because this definition of Turing computation has the assumption the tape will be provided. — Carl (CBM · talk) 16:42, 6 March 2008 (UTC)

I think the key word is "build" -- not "conceptualize". (I suspect that I could find a source for that statement, but where...?) It's not possible (for us) to build (construct, fabricate, make from real stuff) a true TM --only a pale imitation with finite and space-time limited memory -- unless you know something I don't. Gandy's argument carries the notion a step further: That the speed of light also intrudes, ergo we cannot use the universe in its entirety for memory. (I've done some simulations with delayed memory, and the results aren't pretty ... the calculation grinds to a halt and potentially makes errors (how long to wait before doing the computation? An engineer's nightmare)-- even if the memory is 3-dimensional, it still has extent). The companion article to this is huge and dense and cites the living hell out of literature behind the "thesis" from day one (Church) and was our (Softtest123 and my) best effort at bringing together all the controversy (mainly because I got sick of reading bullshit so I went and did the deep research). Church, Turing, Post, Kleene, Goedel etc etc are all there, as are Gandy, Sieg, etc etc. The present lede is my attempt to boil down "the thesis" and offer attribution galore. Bill Wvbailey (talk) 18:45, 6 March 2008 (UTC)

But it is possible to build a Turing machine. There is no need for the machine to have an actually infinite tape - the tape can simply have a special mark at either end, and if the machine hits the mark it pauses and alerts the operator to add more tape. It's the operator's responsibility to supply the tape when it is requested, and then press a button to continue the computation. This is well known, but not usually important in computability theory (see [4] for example). — Carl (CBM · talk) 19:40, 6 March 2008 (UTC)

I agree that we can always add more tape (there's a drawing in The Emporer's New Mind alluding to this) but I (and others) do not believe we ever build a true TM, due to the space-time limitations of our universe (re Gandy's Principles). Which means that there are computations forever out of our reach, even by TMs. But anyway, I'll consent to leaving the paragraphs out until/if I can find some attribution for them.

I had nothing to do with the text after footnote 37, so cannot vouch for it. There is a good article in Sci Am that might serve as a source: Scott Aaronson, March 2008, The Limits of Quantum Computers, Scientific American, pp. 62-67. In particular there's a nice Venn-like drawing on p. 67 of P, BQP, NP and NP-complete in Pspace. Bill Wvbailey (talk) 15:03, 7 March 2008 (UTC)

I agree with Carl’s suggestion (7 February 2008) to discuss Burgin's ideas in the article on Church's thesis. So, I made corresponding additions. With respect, Multipundit (talk) 03:06, 3 April 2008 (UTC)

Church's thesis in Intuitionistic Logic

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)

I am familiar with this sort of axiom, but I don't think we have an article on it. If we do, then a note at the top of this article would be very appropriate. — Carl (CBM · talk) 16:43, 6 March 2008 (UTC)

A paradoxical situation

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)

CT thesis does not "depend on the definition of algorithm"

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)

I would disagree with this. It does depend on what is meant by "algorithm". In order to give a negative solution to, e.g., the entscheidungsproblem, a formal definition was needed which would capture the intuitive notion of algorithm (as I'm sure you know). The C-T thesis states that Turing machines (etc.) capture this intuitive notion. So really the C-T thesis makes the claim that this definition of algorithm is correct. If you take the point of view that an algorithm is, by definition, a Turing machine, then what does the C-T thesis even state? skeptical scientist (talk) 00:19, 12 May 2008 (UTC)

Yes, of course an algorithm is not a Turing machine. But, in the end, the C-T thesis isn't really about algorithms at all, it's about functions. Compare the two quotes at the beginning of this article - they don't mention algorithm at all.

In the end, the C-T thesis states that a number-theoretic function is computable by a human being with pencil and paper (ignoring resource limitations) if and only if it is computable by a Turing machine. Put another way, a number-theoretic function is effectively calculable if and only if it is Turing computable. That statement doesn't even refer to algorithms, much less depend on how they are defined. It is true that the term algorithm is intimately related to this, but not in the way that the language that I removed suggested.

One contemporary reference that carefully discusses this subject is "Computability and Recursion" by Soare [5]; see section 3. Soare states things differently than I do; he views Turing's analysis of human calculation as a proof, and states a thesis on page 11 that doesn't involve Turing machines at all. I prefer to identify "effectively calculable function" with a process a human can follow with pencil and paper, so that the thesis becomes "every effectively calculable number-theoretic function is computable by a Turing machine". — Carl (CBM · talk) 01:08, 12 May 2008 (UTC)

Yes, but I would tend to think of "effectively calculable" and "calculable by following some algorithm" as two different ways of saying the same thing. The problem, really, is that "algorithm" had no precise definition until Turing carefully analyzed a human computing agent, which is why, e.g., Church put forward his thesis and Godel then found it inadequate. So it's not so much that the C-T thesis depends on the definition of algorithm as that its an argument for a particular way of making the definition of algorithm precise. skeptical scientist (talk) 05:11, 12 May 2008 (UTC)

I agree with everything you said. It may help to look at the text I removed to get the context of my original comments; I think they make more sense once you see what I was responding to. — Carl (CBM · talk) 11:58, 12 May 2008 (UTC)

The Emporer's Clothes

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)

Yes, the terms "effectively calculable" and "algorithm" are often left as undefined terms. Then the thesis states that these terms apply to the same functions as the formal definition of "computable function" does. From that point of view, the thesis could be viewed as a definition of "effectively calculable", except that this term already has an informal definition in English. — Carl (CBM · talk) 21:24, 7 October 2008 (UTC)

Analog computers

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)

The Church-Turing thesis is only concerned with one type of function: a function that takes a natural number (or string of 0s and 1s) as input and returns a natural number as output. It is not concerned with real-valued functions per se. — Carl (CBM · talk) 22:20, 11 October 2008 (UTC)

---

This paper may be of interest: Olivier Bournez, Manuel Campagnolo, Daiel Garca and Emmanuel Hainry, 2004?, "The General Purpose Analog Computer and Computable Analysis are two equivalent paradigms of analog computation", off the web. With 24 references:

"In the last decades, the general trend for theoretical computer science has been directed towards discrete computation, with relatively scarce emphasis on analog computation. One possible reason is the fact that there is no Church-Turing thesis for analog computation . . .." (p. 1)

To apply a touring machine to an analog computer discreetize the signals to values within the noise threshold of the system then since it's a mathematical construct it gets more states (tape) depending on the quantization step size. This is done on existing real computers with analog to digital converters and the use of floating point numbers. — Preceding unsigned comment added by 198.2.5.101 (talk) 20:38, 12 May 2016 (UTC)

Bill Wvbailey (talk) 16:18, 12 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:

• always give some answer rather than ever give no answer;
• always give the right answer and never give a wrong answer;
• always be completed in a finite number of steps, rather than in an infinite number;
• work for all instances of problems of the class. —Preceding unsigned comment added by 62.176.172.210 (talk) 10:46, 24 October 2008 (UTC)

"Analog computation yields results in form of real numbers" - what makes you so sure? The "real" in "real number"?137.205.101.22 (talk) 16:04, 26 July 2017 (UTC)

Article Cleanup

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)

The title should have an en dash. Please feel free to remove the spaces around em dashes in the text. — Carl (CBM · talk) 11:25, 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 agree, "effectively calculable", with emphasis on the word "calculable", has the broader meaning of "calculable by any means (any sort agent using any sort of tools) whatever"; this includes hand calculation, as opposed to "computation", i.e. by a computing-machine. Your suggestion looks good to me; sometimes less is more. BillWvbailey (talk) 17:11, 2 May 2014 (UTC)

Real computers are not Turing machines

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.

The paragraph you removed is completely correct. Turing machines do not model interactive I/O, since they produce only a single result; this is obvious. Any "CS books" that state otherwise are wrong, or oversimplifying. TMs are an idealized model of deterministic algorithms; a single Turing machine cannot model a general computation, or a real computing system. A system of TMs connected by message passing can; but that is a quite different model than a single TM, and not reducible to it (primarily because the message passing introduces nondeterminism).

Note that your suggestion about the tape modelling a sequence of inputs is not sufficient to describe a machine that performs both input and output continuously, and where outputs can feed back to inputs via some external process. Furthermore, any deterministic model obviously cannot describe nondeterministic computation (consider cryptography, for instance, where the need to model processes that generate random values is a fundamental requirement). According to the best physical theories we have, random processes are physically realisable, which implies that there are physically realisable processes that cannot be modelled by a TM.

Note that the "Turing thesis myth" referred to is not the thesis in its original form; just its overextension to apply to all computations rather than just deterministic algorithms. Neither Turing nor Church made the mistake referred to here. The Goldin and Wegner paper is well-written, and what it is saying is actually rather uncontroversial. --David-Sarah Hopwood ⚥ (talk) 05:42, 11 August 2009 (UTC)

You are correct that Turing machines capture the notion of deterministic algorithm. Moreover, oracle Turing machines capture perfectly well the workings of computers with a stream of inputs. And Church's thesis does become incorrect if one generalizes it too much. So we are in agreement about all those points.

I do think there is a lot of room for improvement in this article, especially in clearly explaining minority views about Church's thesis. However, I'll point out that the first paper linked in the except above explicitly says that the claim you are arguing against is "part of the mainstream theory of computation" – the paper explicitly identifies its viewpoint as out of the mainstream. There has been an increasing trend in the hypercomputation community to describe certain types of computation as going beyond ordinary computation, even when the rest of the computation community believes they can be modeled with ordinary computation methods. Again, this is something this article could cover more clearly. I'll put a more technical response below about the points you made. — Carl (CBM · talk) 12:48, 11 August 2009 (UTC)

technical response to the examples you mentioned

The key is that Church's thesis is not really about Turing machines, it is about functions (and says any function that can be computed by an algorithm is actually a computable function). So in every case one must identify what function is actually being computed. The thesis is not about computational processes.

In the case of a machine that takes input repeatedly over time, there are two ways one can model this with a Turing machine:

• Put all the inputs on an oracle tape ahead of time, so that the computation can access them whenever desired.
• Add another variable to the function being computed: that variable is filled with a list of the previous inputs, and the function produces the next output. One then iterates this function to model the computation process.

Either of these works perfectly well to model interactive computations with Turing machines.

A random-number generator, achieved in hardware, can be treated in the Turing machine formalism by adding to the Turing machine an oracle tape whose contents are assumed to satisfy appropriate randomness properties. Indeed, this is how real computers use RNGs: they access them just like an oracle whenever they want some more random bits.

So it does seem to me that these sorts of things can be modeled perfectly well with ordinary Turing machines; this is probably why the mainstream viewpoint is also that TMs can model ordinary computers. — Carl (CBM · talk) 12:48, 11 August 2009 (UTC)

Hard to understand, poorly formatted

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.

• We need less footnotes.
• References seem all messed up.
• I expected to find the original unmodified statement followed perhaps by a more modern re-statement of the thesis.
• Please add a link that explains the difference between a thesis, an hypothesis and a theorem.
• The part about Boundedness, Locality and Determinance needs a clarification. —Preceding unsigned comment added by 90.80.39.42 (talk) 12:29, 31 August 2009 (UTC)

lede

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 greatly shortened the lead-in paragraphs and moved the cutout stuff into the article. I pulled out the content of some footnotes that seemed useful commentary and put it into the text, and fleshed out "The part about Boundedness, Locality and Determinancy". I fiddled with quotes and text here and there. Bill Wvbailey (talk) 20:08, 31 August 2009 (UTC)

Plans

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.

1. Overall structure. It is difficult for me, reading through the article at present, to see the overall structure and flow. The sections don't seem to complement each other in quite the way I expect, and the flow of ideas is not pleasing. I feel this is the most important improvement to be made.
2. Differing opinions on the status of the thesis. The present article has in its lede the claim that the CTT is a hypothesis that cannot be proven. That is one significant viewpoint, but there are at least three other viewpoints in the literature. To achieve a neutral, comprehensive article, these viewpoints should also be covered. Please don't argue for or against them here; the thing that we have to figure out is how broadly they are reflected in the literature, not whether they are correct. The article does mention some of these, but in a way that spreads them out.
   1. That, although the CTT is not amenable to formal proof, it nevertheless can be proved informally, and has been. Thus there is no reasonable doubt that the thesis is false, and we can be sure that no counterexamples will ever be found
   2. That the next step is to develop axioms for informal computability to enable formal proofs of the CTT. There are published proofs of the thesis along these lines.
   3. That the CTT has already been disproved.
3. Different forms of the thesis When recursion theorists talk about the Church-Turing thesis, they mean "any function from the natural numbers to the natural numbers that is effectively calculable by a human is computable by a Turing machine". However, many on the CS community go farther. We discuss some of their extensions in the article, but in places that make them hard to find (e.g. in the section "Success of the thesis"). These should be presented more clearly, especially because a major source of confusion for readers (and editors of this article...) is the different meanings attributed to the phrase "Chuch-Turing thesis".
4. Contemporary literature The article at present has very little on developments after 1940 or so. It does not include references to Kalmár's published disproof of the thesis in 1959. There is enough secondary literature these days to really back up the central claims made in our article with references to texts and literature surveys.

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)

I agree with the issues you identified and your proposal to address them. I'm sure you'll be able address the varying opinions on the provability and (un)proved status in a WP:NPOV manner. I did a little reading on this myself, so I may be able to contribute here and there. Also, the "satellite" article Church-Turing-Deutsch principle should probably be expanded to include all physical forms of CTT, e.g. Penrose's "Turing principle". Alternatively we could include all that discussion here, and make CTD a redirect here, although it's probably a sufficiently distinct topic. YMMV on that aspect. Pcap ping 16:08, 14 September 2009 (UTC)

I've done a little work towards addressing 3, i.e. separating the variations. Pcap ping 18:40, 15 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:

In conclusion, I will recall that I was present at the Amsterdam Colloquium of 1957 when my good fried Laszlό Kalmar presented his argument against the plausibility of Church's thesis [11] (cf. Webb [29], p. 209); I immediately concluded, as fast as I heard it, that he had not given an effective procedure for deciding as to the truth or falsity of (x)T(n,n,x). He would not be able to tell me in advance in a finite communication (no matter how long we both should live) what set of atomic rules would completely govern the concrete steps in his search for proofs by "arbitrary correct means" of (x)T(n,n,x). I refrained from embarrassing him at the Colloquium by asking him for them on the spot."(REFLECTIONS ON CHURCH'S THESIS 1987:495).

Thanks, BillWvbailey (talk) 19:36, 15 September 2009 (UTC)

I will see if I can get an electronic copy of Kalmar's paper. I have looked at a tiny portion of the recent compilation Church's thesis after 70 years, and plan to look at more. But caution is required with those papers, as Peter Smith's harsh review explains. They're of very mixed quality. — Carl (CBM · talk) 02:21, 16 September 2009 (UTC)

Carl, thanks. I've downloaded Smith's criticism-paper. A few of them I've read. He's correct: the Shagrir paper re Goedel and Turing Computibility is really good -- I downloaded it, read about half and skimmed the rest (he missed the van Heijenoort addendum but certainly got the rest -- now that he's got access to Goedel's nachlass via Dawson). I took the liberty of adding this as a reference into the article and then adding a tentative ref to the collection.

I have at least one quibble with Smith's review -- he dismisses Post's "empirical hypothesis" hypothesis too readily (he doesn't attribute it to Post, but that's the original source of it) (cf p. 9).

There seems to be an industry sprouting up around the CTT reminiscent of what's happened to the philosophy of mind. I've now encountered the "Mild Physical CTT" and the "Bold Physical CTT" (both in Piccinini 2007), the Machine CTT or "MCT" (mentioned in the Smith review of Hodges and Fitz (cf p. 6 in Smith), the "Sequential Interaction Thesis" of Goldin and Wegner (2005) (interesting discussion (refutation) of the Strong CTT, at least their interpretation of it; but the article breaks down at pages 15ff), the (Classical) Strong CTT, and "the Strong CTT" mentioned in this article (I haven't been able to corroborate the 2nd version with the fact tag on it.) It's like Pandora's Box -- open the lid and all the evils of the world fly out; you can't catch them and put them back. Bill Wvbailey (talk) 15:01, 16 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)

old version

(moved from above)

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)

This is actually just an old version of our article. I didn't look up the exact revision, but this one is quite close. — Carl (CBM · talk) 02:21, 16 September 2009 (UTC)

"If quantum computers are physically possible"

Should we be that cautions here? See Quantum computing#Developments. Pcap ping 18:44, 15 September 2009 (UTC)

This is yet another thing that should be addressed in the plans listed above.

Quantum computers (as are actually being designed) can be simulated by ordinary Turing machines, and so have no implications for the Church-Turing thesis. This is because these quantum computers only maintain their data to within a fixed tolerance. If it were possible to have a quantum computer that could measure things perfectly, that might have implications, but there is apparently no belief that a "perfect accuracy" quantum computer could actually be built. Moreover, the implications would not be to the ordinary Church-Turing thesis, which relates human computability to Turing machine computability; it would only affect things like the physical Church-Turing thesis. — Carl (CBM · talk) 02:08, 16 September 2009 (UTC)

I think the "Variations" section explains what you wrote above clearly enough... There's the small matter that Lance Fortnow believes that Bernstein and Vazirani "made up" the (classical) strong CTT just so it can be immediately replace by the quantum version. [8]. Not sure if this view is worth adding to the article... Pcap ping 03:03, 16 September 2009 (UTC)

The same blog post has a reply by Ronald de Wolf which refutes Fortnow's claim by quoting a paper by Peter van Emde Boas, which was published before Bernstein-Vazirani and makes the same claim. In any case, it's not important enough to mention in the article. --Robin (talk) 19:28, 17 September 2009 (UTC)

I found that ref too and already added it to the article. It's not exactly the same claim though. Occasionally, it pays to read blog comments... Pcap ping 22:12, 17 September 2009 (UTC)

Physical CTT

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

No one has claimed that this thesis has been "proved". I'm not even sure if that makes sense. How could one prove something like that? --Robin (talk) 04:08, 6 December 2009 (UTC)

This is no weasel

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)

I agree with Pcap. "Strong" is part of the name of the thesis, not an adjective we're adding to make it sound cool. --Robin (talk) 13:43, 8 December 2009 (UTC)

This is not widely accepted terminology. On the other hand, the adjective "Complexity Theoretic" is factually accurate and therefore does not require supporting citations. AshtonBenson (talk) 18:42, 8 December 2009 (UTC)

"factually accurate and therefore does not require supporting citations" is WP:OR. Pcap ping 21:01, 8 December 2009 (UTC)

I think this is a no-brainer. Google shows 2 hits for "Complexity-Theoretic Church-Turing Thesis" but 16800 hits for "Strong Church-Turing Thesis." What more can I say than that? --Robin (talk) 22:38, 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)

It's a bit more than that. It's an assertion that not only is the standard deterministic TM universal, but it also simulates all other "reasonable" or "realistic" models of computation with at most polynomial slowdown. The usual hypothesis, without the word "strong", doesn't say anything about the slowdown. --Robin (talk) 22:32, 8 December 2009 (UTC)

That's what I was saying. The article here talks about probabilistic machines, while I thought the strong thesis was about ordinary machines. — Carl (CBM · talk) 01:03, 9 December 2009 (UTC)

Oh, I see. I'm not too sure which one is the proper version of the strong CTT, but it seems the probabilistic TM statement is backed up by the textbook by Kaye/Laflamme/Mosca. Most complexity theorists probably wouldn't mind either formulation, since it is believed that polytime deterministic TMs can simulate polytime probabilistic TMs. --Robin (talk) 03:27, 9 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

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)

See #"If quantum computers are physically possible" for this. Pcap ping 23:28, 8 December 2009 (UTC)

Oh, thanks! — Miym (talk) 23:34, 8 December 2009 (UTC)

Wegner and the "driving home for work" problem

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)

This sort of real-time-input sort of computation can be modelled with an oracle machine. See the discussion at Talk:Algorithm characterizations under "can an algorithm produce infinite output?", in particular CBM's answer. Also see the section "Choice c-machines, Oracle o-machines" in the Turing machine article. BillWvbailey (talk) 00:02, 23 March 2010 (UTC)

Yes, Wegner's paper addresses c-machines and o-machines. He makes the point that those are no longer algorithmic Turing machines since they can't be implemented as automatic processing with all input being explicit at the beginning of the computation. He also states (quite convincingly) that the equivalence of functions and algorithms is only made for a-machines in Turing's paper. So his point is that c- and o-machines can model real-time computations, but don't fall within the scope of the C-T thesis - you need additional constructs for that. Diego (talk) 08:49, 23 March 2010 (UTC)

This is interesting. For a more satisfying/convincing discussion than I can give you, you probably should enlist the editors CBM, Trovatore, JRSpriggs et. al. I'll need to read the articles to form an opinion; I'm not au courant RE the contemporary research. But those guys are the practicing mathematicians who are au courant and can address this better than I can.

By random happenstance I found this in the article Halting problem contains the following (boldface added for emphasis):

"Since the negative answer to the halting problem shows that there are problems that cannot be solved by a Turing machine, the Church-Turing thesis limits what can be accomplished by any machine that implements effective methods. However, not all theoretically possible machines are subject to Church-Turing's thesis (e.g. oracle machines are not). It is an open empirical question whether there are actual deterministic physical processes that, in the long run, elude simulation by a Turing machine. It's also an open question whether any such process could usefully be harnessed in the form of a calculating machine (a hypercomputer) that could solve the halting problem for a Turing machine amongst other things. It is also an open empirical question whether any such physical processes are involved in the working of the human brain, thus whether humans can solve the halting problem.[2]"

Bill Wvbailey (talk) 00:23, 24 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,

"While the Strong Turing Thesis is true when computers are limited to the task of computing functions or algorithms (as they were originally), it does not apply in the context of highly interactive computing systems of today and tomorrow, such as the internet, multimedia document processors, or robotic cars."

But this "limitation" is a key part of the Church-Turing thesis. The ordinary Church-Turing thesis is what they call the "Turing thesis":

"Whenever there is an effective method (algorithm) for obtaining the values of a mathematical function, the function can be computed by a TM."

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

Every effectively calculable function is a computable function

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)

Indeed, part of the argument by Wegner and Goldin is that such distinction is not always made - specially in the text books for CS curricula, where the "general meaning" of algorithm (such as how to make a martini, or how to drive a car by a reactive computer) is assumed but then the "TMs can compute any algorithmic problem" is still hold without qualification. See their writings on "the Turing Thesis Myth". They also argue that some forms of non-TM computing can be described by other formulations, and thus those formulations are more expressive. Diego (talk) 15:02, 24 March 2010 (UTC)

Dershowitz-Gurevich Theorem

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)

Because most people recognize that the very idea of "proving" Church's thesis is absurd: CT is a definition, not a formal conjecture. Can you prove that Dedekind's construction of the real numbers is "true"? Computationalist (talk) 12:09, 6 October 2010 (UTC)

The paper is not "that old" - I think their work will take a long time to make much of an impact in elementary textbooks. It would takes time for people to shift in viewpoint from "an algorithm is anything that can be done by a human with pencil and paper" to "an algorithm is anything that satisfies these three postulates". It's hard to predict whether such a paradigm shift will ever occur.

FWIW many people consider Turing's original paper to be a "proof" of the theory - and many do not. And that paper has been around for almost 80 years. — Carl (CBM · talk) 23:57, 19 November 2010 (UTC)

Removed "concurrency" link

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:

• At the beginning, initialize an integer variable x to zero
• Send yourself two letters in the mail: one that says "add one to x" and one that says "stop"
• Whenever you get an "add one" letter back, follow its instructions and send yourself another "add one" letter
• When you receive the "stop" letter, stop

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)

Hewitt and fellow theorists Milner, Hoare, etc. have been publishing papers about this in conferences, referreed journal articles and books since 1973. Consequently, the results are well known and well established in computer science. These theoreticians addressed the issue of "[What is computation?" They proved that effective computation goes beyond what Turing Machines can do regardless of whether it is peformed using humans or computers. For example, their theories apply to computer operating systems that are not supposed to stop and consequently are not intended to compute a mathematical function.

Also, it is important not to be confused that their published results depend on "randomness" of the kind in non-deterministic Turing machines. Indeterminacy in computation does not require randomness like coin flipping in non-deterministic Turing machines.171.66.77.131 (talk) 01:28, 20 November 2010 (UTC)

The point here is that the Church-Turing thesis is about computable functions, not about arbitrary sorts of "computation". For example, there is no difficulty at all implementing an operating system as a Turing machine; the only "difficulty" is in properly representing the problem as a function problem first. As I often point out, a Turing machine cannot make martini, but this is irrelevant to the the Church-Turing thesis.

In any case, I explained the mathematical issue so that others wouldn't be confused. I have no illusion that mt explanation will be compelling to whoever it is that wants to add Hewitt's work to numerous wikipedia articles. So I will be intentionally limiting my responses to IP editors who promote Hewitts work. This isn't because I have anything against Hewitt's work, only because that work (e.g. the Actor model) simply isn't relevant to the mainstream understanding of the Church-Turing thesis. — Carl (CBM · talk) 02:35, 20 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:

The outputs of a closed computatonal system made up of effective components are recursively enumerable.

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 theorem quoted above is not stated exactly (see Common sense for concurrency and inconsistency robustness using Direct Logic(TM) and the Actor Model). It should be:

The possible outputs of a closed computational system made up of effective components are recursively enumerable.

A Turing Machine can enumerate all the possible executions of a closed system even though it cannot perform them individually. For example, the integers are recursively enumerable even though a non-deterministic Turing Machine has bounded non-determinism (i.e. there is a bound on the size of integer that can be computed starting on a blank tape). Proving that a server will actually provide service to its clients depends on unbounded non-determinism. That's why Hoare reversed the semantics of CSP from bounded non-determinism [Hoare CSP 1978] to unbounded non-determinism [Hoare CSP 1985]. Consequently, CBM was wrong: a Turing Machine cannot implement an operating system.

However, the above editor is certainly correct that CBM was fundamentally mistaken and that it is ridiculous to try to represent an operating system as a recursive function. And so it is probably correct that Church would agree that the lambda calculus is in need of extension.67.169.144.115 (talk) —Preceding undated comment added 22:15, 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)

I have now changed the page "protection" settings to prevent IP users from editing the page for a period of 1 month. — Carl (CBM · talk) 21:49, 28 November 2010 (UTC)

Church Turing Thesis in Computer Science

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)

ArXiv is not a competitor to Wikipedia in any way. It is an uncensored article repository. Wikipedia is an encyclopedia. There is no similarity. Please refer to Wikipedia:What Wikipedia is not. AmirOnWiki (talk) 14:47, 14 October 2011 (UTC)

a little cleanup

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)

Church-Turing thesis is nothing but a normal (correct) mathematical definition

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)

Take a look at History of the Church-Turing thesis where the issue of whether it's a definition (Turing), Kleene 1952 (two proofs from formal systems leading to a single "Church-Turing" proof) or Post (a natural law) is debated. Along your line of reasoning, Goedel makes an observation (cf Goedel 1946 Remarks before the Princeton Bicentennial conference on problems in mathematics) that "in the concept of general recursiveness (or Turing's computability . . . one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e. one not depending on the formalism chosen" (Feferman et. al. 1990 [Volume II]:150). But he doesn't take it further. As for my opinion, I'm with Post (it's a natural scientific law determined by repeated observation but still open to counter-evidence). Here's why: there's still these niggling little problems of "analog computation" and "quantum mechanics" and "consciousness", so I wouldn't be too hasty to jump to the conclusion "the thesis" is just a matter of definition. Bill Wvbailey (talk) 00:17, 30 January 2012 (UTC)

Incorrect definition on disambig

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)

PCTT == Church–Turing–Deutsch principle?

Is the Physical Church–Turing thesis (PCTT) equivalent to the Church–Turing–Deutsch principle? Bayle Shanks (talk) 08:20, 26 May 2013 (UTC)

The physical Church-Turing thesis actually comes to two broad flavours: bold and weak. The CT-Deutsch is a form of the bold PCTT. See http://plato.stanford.edu/entries/computation-physicalsystems/#PhyChuTurTheBol Honestly, the section on PCTT in this article isn't well written. After reading the Stanford article above, you may be able to do better.  :) Ross Fraser (talk) 23:59, 28 May 2013 (UTC)

Lede: Sounds as if Turing created "only" universal TM

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)

Not correct. As to where the primitive recursive functions came from: Kleene, Church etc in the US carrying on the work of Hilbert and Bernays, Ackermann and Roza Peter etc in Europe (see footnote 3 to Goedel's 1931 "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I" where he details the sources of the formalism he uses in this paper). After the discovery of the Ackermann function (1928) -- it could not be computed by means of the primitive recursive functions (so-named by Peter), Goedel added what has become known as the "mu operator" (unlimited search operation) at the suggestion of Herbrand (1934). So what was there was more correct than what is there now, but perhaps it needs either a footnote or the addition. For more sources see an example of Hilbert's system at Hilbert 1927 "The foundations of mathematics" in van Heijenoort:464ff. For a discussion of the history of "general" recursion see Kleene 1952:270ff; Ackermann discovered his function in 1928, Peter added work in 1935, in particular Kleene:274: "The characterization of all "recursive functions" was accomplished in the definition of 'general recursive function' by Goedel in 1934, who built on a suggestion of Herbrand". Kleene 1936 and 1943 simplified this definition (cf pages 274, 275) to become what we know now as the mu operator. BillWvbailey (talk) 14:42, 28 September 2013 (UTC)

One could maybe argue that Peano should have at least some credit for the primitive recursive functions. Anyway, that's beside the point. The question is who should be credited for "general recursive function". My argument was that Goedel was first to define it, as acknowledged by Kleene. Hence, Goedel should get the credit, especially in the lead. Wasn't Church's thesis first formulated in terms of the Herbrand-Goedel definition? Daniel Vallstrom (talk) 22:32, 28 September 2013 (UTC)

See e.g. [11] and [12]. Daniel Vallstrom (talk) 22:44, 28 September 2013 (UTC)

No, and yes. My response is the first and second paragraphs; the rest is backup.

RE the origins of recursion theory, Kleene gives credit to "a number-theoretic adaptation of Dedekind's analysis of primitive recursion (1888)" (Kleene 1952:242).

RE The Herbrand-Godel definition of general recursive functions: This is the moniker that Kleene uses (1952:274). It's in the literature, so I'd go with this, if you feel the need to "assign credit". But this definition is not what we should be talking about -- it's just a very general definition (see below); it is not a formal system (formalism-- symbols, formation rules, logic, deduction via logic and modus ponens, recursion etc). And formal systems are what we're after when we're discussing the "Church-Turing Thesis". In other words, if we're going to equate Turing machinery to calculations executed by mathematicians with pencil and paper (recursion, λ-calculus), we first must formalize our “pencil-and-paper systems” and then "arithmeticize" these formalisms (e.g. into Goedel numbers). The recursion theory we're familiar with nowadays begins with Church's reduction of the Herbrand-Goedel statement (Goedel's original statement in his 1934 is quite vague and generalized, I read it); it adds Kleene's mu-function to a primitive-recursion formal system (see §50 in Kleene 1952) to produce e.g. Kleene's "general recursive" formal system (cf his Formalism of Recursive Functions as a Generalized Arithmetic" at Kleene 1952:277). This is the system that Kleene uses to prove his equivalence of “general recursion” to Turing machines and postulate a “Church-Turing Thesis”, his Theorem XXX (see more below).

--- Backup:

RE Church's thesis: In his 1935 he defines "effective computability" in terms of his "λ-definability". He tried to push his thesis -- that the definition of "effective computability" should be his "λ-definability" on Goedel but Goedel wouldn't have it So he proved that "recursive functions" and "λ-definability" are equivalent, cf his Theorems XVI "Every recursive function of positive integers is λ-definable" and Theorem XVII "Every λ-definable function of positive integers is recursive [in footnote 17: This result was obtained independently by the present author and S. C. Kleene at about the same time] (page 99 in The Undecidable). To prove this Church had to accept the Herbrand-suggested, Goedel-stated notion of "general recursive function”. Church gives a definition of "recursive function" as follows: "A function of positive integers for which a set of recursion equations can be given is said to be recursive [Footnote 9: This definition is closely related to, and was suggested by, a definition of recursive functions which was proposed by Kurt Goedel, in lectures at Princeton, N. J., 1934, and credited by him in part to an unpublished suggestion of Jacques Herbrand. The principal features in which the present definition of recursiveness differs from Goedel's are due to s. C. Kleene . . . it follows readily from Kleene's results in that paper that every function recursive in the present sense is also recursive in the sense of Goedel (1934) and conversely." (page 95 in The Undecidable). This definition of "recursive function" is then given by Kleene 1952 as follows: "We say then that a function φ is general recursive, if there is a system E of equations which defines it recursively (§54, with l=0)." (Kleene 1952:274). This reference to §54 is key, because this section defines a formal system, a "formalism", in the sense of Hilbert-Bernays, i.e. symbols, a logic, formation rules, modus ponens, and recursion relations (cf Kleene 1952:262ff, 263 in particular), and an "agent" with paper and pencil.

RE Turing's thesis: In his 1936 Entsheidungsproblem paper he proves, at the very end, that "The theorem that all effectively calculable (λ-definable) sequences are computable and its converse are proved below in outline" (p. 149 in The Undecidable). Turing went on to restate this in his 1939 Ordinal's paper. Here he eschews recursively-defined functions and sticks with λ-definability, and goes on to acknowledge his 1937 and Post's 1936 as "intuitive defintions" of "effective calculability" and assert his own "thesis": "It was stated above that 'a function is effectively calculable if its values can be found by some purely mechanical process' . . . The development of these ideas leads to the author's definition of a computable function, and to an identification of computability with effective calculability. It is not difficult, though somewhat laborious, to prove that these three definitions ["general recursive" (Herbrand-Goedel), λ-definability (Church-Kleene-Rosser), mechanical computation (Post 1936, Turing 1937)] are equivalent (Kleene 1936, Turing 1937)" (page 160 in The Undecidable).

RE Church-Turing thesis: The equivalence of the partial recursive functions and the “computable” (i.e. Turing-computable) functions is stated by Kleene in his theorem XXX and the following paragraph: “Turing’s thesis that every function which would naturally be regarded as computable is computable under his definition, i.e. by one of his machines is equivalent to Church’s thesis by Theorem XXX. Wvbailey (talk) 15:34, 29 September 2013 (UTC)Bill

Oh dear, did I set of that avalanche? o.0 Now I didn't look at all the details in your discussion, but if this is still a matter of disagreement or confusion, shouldn't we also tackle it in Computable function? That is, if it's not easily explained how (and by whom) the definition of recursive functions came to be, then the article about recursive functions should explain it ;-)

Also, I have a totally unrelated question. I guess I'm better adding a new section... --Se'taan (talk) 00:03, 30 September 2013 (UTC)

The general problem: writing "computable" vs. "calculable"

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)

My short answer (advice) is make it clear that "effectively computable" is by mechanism only, whereas the historic usage of "effectively calculable" is "by any means whatever" (man+paper+pencil, or by mechanism, or by a combination). The matter requires one to distinguish the generalized historical notion of "mechanical procedure (process)" versus the specific notion/instance of "procedure (process) carried out by a machine". Goedel 1964 summarized the notion of 'mechanical procedure' this way: "mechanical procedure (alias 'algorithm' or 'computation procedure' or 'finite combinatorial procedure').

Turing 1939 stated it as follows [but see more below]: "We shall use the expression "computable function" to mean a function calculable by a machine, and we let "effectively calculable" refer to the intuitive idea without particular identification with any one of these definitions. . .." He lists these 'these definitions' that are all generally 'mechanical processes': Herbrand-Goedel recursive functions, Λ-definable functions, Post's man-with-instructions-in-boxes+paper+pencil, and Turing's mechanisms. (Turing's 1939 "Oracle" paper in The Undecidable 1967:160).

The long (historical) answer follows:

Definition of "Effectively calculable" in terms of "algorithm": Church 1936 asserts that "It is clear that for any recursive function of positive integers there exists an algorithm using which any required particular value of the function can be effectively calculated." (The Undecidable 1967:95). He goes on to define "the notion . . . of an effectively calculable function of positive integers by identifying it with the notion of a recursive [in the Herbrand-Goedel sense] function of positive integers (or of a λ-definable function of positive integers). He follows this with the converse assertion that "under the same definition of effective calculability, that every function, an algorithm for the calculation of the values of which exists, is effectively calculable." ( Church 1936 in The Undecidable 1967:100).

Definition of "effective method": Rosser 1939 introduces a definition of "effective method", as follows:

" 'Effective method' is here used in the rather special sense of a method each step of which is precisely predeterminted and which is certain to produce the answer in a finite number of steps . . . three different precise definitions have been given to date. [footnote 5] The simplest of these to state (due to Post and Turing) says essentially that an effective method of solving a certain set of problems exists if one can build a machine which will then solve any problem of the set with no human intervention beyond inserting the question and (later) reading the answer. All three definitions are equivalent . . ." (Rosser 1939 in The Undecidable 1967:226).

Definition of "computable function" versus "effectively calculable":

"A function is said to be 'effectively calculable' if its values can be found by some purely mechanical process. Although it is fairly easy to get an intuitive grasp of this idea, it is nevertheless desirable to have some more definite, mathematically expressible definition." Turing then lists four of these as follows: Herbrand-Goedel's "general recursive functions", Church's λ-definability, his own machinery, and Post's model. He asserts that his and Post's "definition correspond "more closely to the intuitive idea . . . We may take this statement ['effectively calculable' if its values can be found by some purely mechanical process] literally, understanding by a purely mechanical process one which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal form, of the structures of these machines. The development of these ideas leads to the author's definition of a computable function, and to an identification of computability [footnote †] with effective calculability.

[in footnote †] "We shall use the expression "computable function" to mean a function calculable by a machine, and we let "effectively calculable" refer to the intuitive idea without particular identification with any one of these definitions. . .." (Turing's 1939 "Oracle" paper in The Undecidable 1967:160).

Definition of "effectively decidable": Kleene 1943 frames this in context of "algorithmic theories" . . . "the theory should give us an effective means for deciding, for any given one of the propositions which are taken as values of the predicate, whether that proposition is true or false. . . . What we need to do is to describe a procedure, performable for each set of values of the independent variables, which procedure necessarily terminates, and in such manner that from the outcome we can read a definite answer, 'Yes' or 'No,' to the question, 'Is the predicate value true?' " (Kleene 1943 in The Undecidable 1967:273-274).

BillWvbailey (talk) 15:07, 30 September 2013 (UTC)

Bill, thanks for your detailed answer. Though there are some parts that I still haven't got (or maybe I just don't remember them, or I'm too tired...), I completely agree with your answer (at least all parts that I got...). As there are no opposing comments by now, I'll take it that "make it clear that effectively computable is by mechanism only, whereas the historic usage of effectively calculable is by any means whatever" is consensus. I'll try to introduce this into the relevant articles occasionally. Thanks again! --Se'taan (talk) 08:25, 22 November 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)

Turing's doctoral work

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)

Missing/Obscured References

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)

When the section "History of the Church-Turing Thesis" was moved out of "Church-Turing Thesis" into its own article, some of the references went with it and nobody noticed that a few were also needed for the "Church-Turing Thesis" article. See https://en.wikipedia.org/wiki/History_of_the_church-turing_thesis . Here are the missing references, located there:

• Barwise, Jon, H. J. Keisler, and K. Kunen, Editors, 1980, The Kleene Symposium, 426 pages, North-Holland Publishing Company, Amsterdam, ISBN 0-444-85345-6
• Sieg, Wilfried, Richard Sommer, and Carolyn Talcott (eds.), 2002, Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman, Lecture Notes in Logic 15, 444 pages, A K Peters, Ltd., ISBN 1-56881-169-1

Bill Wvbailey (talk) 02:23, 27 July 2014 (UTC)

extended Church–Turing thesis

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)

Good catch by SMmoto

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. BillWvbailey (talk) 17:19, 2 February 2015 (UTC)

Non neutral point of view

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)

Many computer science textbooks distinguish between the actual Turing thesis (on human calculability) and the "Strong Turing Thesis" about arbitrary computing machines. The article would be improved by mentioning the strong thesis as well. Here is a reference, actually, for what is going on in all these undergraduate computer science textbooks. "Turing’s Ideas and Models of Computation" by Eberbach, Goldin, and Wegner, 2004, (link currently down: [14]) explains:

"When the first undergraduate computer science textbooks were being written in the 1960s, Turing's contributions to the theory of computation needed to be presented in a more accessible fashion. As a result, the Turing thesis and the Universality corollary were glibly combined into one, resulting in the following (incorrect) strong interpretation of the Turing thesis that one often sees in undergraduate textbooks:

Strong Turing Thesis: a Turing machine can do everything a computer can do.[36]

The current generation of computer scientists has absorbed the strong interpretation of the Turing thesis with their undergraduate education, believing it a heresy to question it. However, this interpretation needs to be distinguished from the actual contributions of Turing or his contemporaries on which it is based."

Similar explanations of the situation with undergraduate CS textbooks can be found in other reliable, published sources, but this one is quite direct about what is going on. — Carl (CBM · talk) 13:10, 20 June 2015 (UTC)

'Formal proof' usually means informal proof I suppose but insomuch as 'formal' actually means formal, as in formalized, pseudocode won't suffice. Granted, invocation of Church's thesis often shows a misconception of what it's about (namely that it's just an ordinary math definition, by Turing, of computability). Daniel Vallstrom (talk) 11:23, 7 July 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)

Human computer

For references on the relationship between Turing's thesis and human computers, here are three good sources:

• Section 9 of Turing's original paper [15]
• The Stanford Encyclopedia article by Jack Copeland [16]
• Section 3 of Soare's paper Computability and Recursion [17]

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)

External links modified

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:

• Added archive https://web.archive.org/web/20151217145831/http://moon.cc.huji.ac.il/oron-shagrir/papers/Goedel_on_Turing_on_Computability.pdf to http://moon.cc.huji.ac.il/oron-shagrir/papers/Goedel_on_Turing_on_Computability.pdf
• Corrected formatting/usage for http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf

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).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 13:41, 7 August 2017 (UTC)

Philosophical implications paragraph.

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)

Turing's Mistake

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)

Citations in quotes

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 just removed the citations - following [18] I added "footnotes omitted." to the short footnote. Per WP:CITESTYLE Wikipedia doesn't have a detailed style guide that would dictate a policy for this. --Mathnerd314159 (talk) 16:19, 6 September 2021 (UTC)

Although I will add, I checked the APA style guide 7th edition and it says you can omit footnote numbers in quotes without any indication. So the note isn't strictly necessary, but I don't think it detracts significantly from the article.

Contrariwise, APA requires the inclusion of parenthetical references in quotes. But parenthetical references are deprecated on Wikipedia, so I think this part of the guideline can be ignored and all references should be omitted from quotes. --Mathnerd314159 (talk) 19:20, 6 September 2021 (UTC)

an n-state turing machine terminates in n or less states or does not terminate.

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)

In your argument, you didn't consider the tape. When the machine re-enters a state again, the tape contents is usually different, and hence so is the further maschine behavior. Examples are shown e.g. at Busy_beaver#Examples, including an animation of a 3-state machine that halts after 14 steps (see File:Busy Beaver 3-state 2-symbol Run.gif for a version expanded in time). - Jochen Burghardt (talk) 22:15, 3 December 2021 (UTC)

No, I do consider the tape. Unless you are using an infinite tape - in which case you have an infinite state turing machine, which is equavelent to all other infinite state turing machines. Finite state can only be taken to mean finite tape lenght as well. if it's an infinite tape turing machine then it's a universal turing machine. Am i misunderstanding something here? Maybe the problem is poorly posed. if it's turing complete then with an infinite tape (or you can think of it as infinite memory)... maybe the term "state" is poorly defined here. i take "state" to mean all of the data on the stack and the tape, put together. so if the stack space is 16 bytes and the tape is say 256 bytes, then the number of states is 2 to the power of 8*(256+16), and at least one of those states is the halting state. so either it repeats before going through all of the states, in which case it never halts, or it eventually reaches one of those halting states, which occures in at most 2 to the power of 8*(256+16) state changes. Because it can't go through any more state changes than that without hitting a state it's already been in. And if it hits a state it's already been in then it's stuck in an infinite loop. Kevin Baas^talk 18:24, 20 December 2021 (UTC)

Your understanding of "state" (although it does make sense) deviates from the usual jargon in the definition of a Turing machine (on which the article is based). The latter assumes a potentially infinite tape, separated from a finite-state control. I guess, this is the misunderstanding here. I agree that your above argument is valid if the tape is restricted to a fixed finite length. See finite automaton for the usual definition of what you (apparently) have in mind. - Jochen Burghardt (talk) 20:33, 20 December 2021 (UTC)