Talk:Church–Turing thesis

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class High Priority  Field: Foundations, logic, and set theory
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as Start-Class on the assessment scale
Top rated as Top-importance on the assessment scale

Contents

[edit] 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^0_2) 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)