Talk:Church-Turing thesis
|
|
The Turing thesis is too specific a concept to be accurately stated by anyone capable of using (in "The method will always produce the result in a finite number of steps.") the expression "finite number of steps". --Jerzy 23:59, 2004 Feb 8 (UTC)
| Contents |
Tautology
User:Anothony DiPierro added:
- Church-Turing Thesis, Tautological Version: Mathematics problems can be solved only by doing mathematics.
Would you like to ellaborate a bit on what this means? I have a suspicion that it's misinterperative. -- pde 01:38, 9 Mar 2004 (UTC)
- The explanation is in the full version. I'll link to the source. Anthony DiPierro 12:57, 9 Mar 2004 (UTC)
As it stood, it added nothing to the article but an invitation to go read an exceptionally long book that includes a lot of irony and sophisticated humor.
If you can't explain its relevance on this talk page, it certainly doesn't belong in the article. Tell us why here.
(BTW, if the information provided were relevant, the way to state it would be
- D.Hofstadter in GEB described the "tautological version" of the thesis as "Mathematics problems can be solved only by doing mathematics."
If you can't think of a better way to document than with a number-only reference to a list entry whose number will change the next time an A-G reference is added, you aren't thinking hard enough.) --Jerzy(t) 18:56, 2004 Mar 9 (UTC)
I think the relevance is obvious. It's a simplified version of the thesis. As for the reference, if you don't like my format, fix it. Anthony DiPierro 23:21, 9 Mar 2004 (UTC)
Hofstadter gives lots of different "versions" of the thesis throughout Chapter 17 of GEB, and you'd have to read the whole chapter to understand where he's going with it. The version that Anthony is trying to add to the article is only the first one, and Hofstadter himself calls it "almost pointless" when he introduces it, clarifying immediately afterwards: "Of course, its meaning resides in the meaning of its constituent terms," which he then goes on to discuss. The Wikipedia article does not go into the same discussion that Hofstadter does, so the meaning of the sentence resides only outside the Wikipedia article. Which means that the sentence is of no use in the article. Ho hum. -- Oliver P. 00:54, 10 Mar 2004 (UTC)
Fine. Keep it out. I think it's a useful statement, and I think it's obvious what it is saying, with or without reading the entire chapter. Anthony DiPierro 02:01, 10 Mar 2004 (UTC)
I think the collision between the Church-Turing Thesis and Godel's Incompleteness Theorem is worth exploring in more detail, and in that context a link to GEB would certainly be appropriate. Stating the tautology alone is potentially misleading, though, since Godel's whole point was that any logical system contains unprovable propositions. Katherine Derbyshire 19:19, 31 Aug 2004 (UTC)
Epistemology
Why is Roger Penrose's view "epistemologically dubious"? I've heard that its physically or neurologically dubious, but the adjective actually employed here seems merely to suggest that it hasn't been adequately justified to the satisfaction of the writer of the phrase -- fine, but either POV or way too abrupt. Either a specifically "epistemological" objection to Penrose ought to be outlined here (however briefly) or the adjective should be dropped. User:Christofurio
- Any unattributed opinion should be dropped. I've taken it out altogether. (See below.) -- Oliver P. 23:51, 12 Mar 2004 (UTC)
- Well, what I meant was that Penrose reached his claim without physical or neurological evidence, and in contradiction to the far more straightforward theory that intelligence is a product of the computations which occur in the brain. He proposes a theory which is "physically or neurologically dubious" and in spectacular contradiction with Occam's razor, hence my claim that it is epistemoloigcally dubious. Perhaps "scientifically dubious" would be a better qualification? -- pde 04:00, 13 Aug 2004 (UTC)
NPOVing
Statements like "it is conceivable but unlikely that it could be disproven", "this proposition is dubious", and "it seems unlikely that physics will admit harnessable hypercomputation" are purely opinion and should be attributed to whoever holds these opinions if they are to be included. And I have no idea what this means:
- In fact, the Church-Turing thesis has been so successful, that it is now almost moot
According to my dictionary, "moot" means "detabatable", "undecided". I don't think this is what was meant. In any case, it's another unattributed POV, so I've taken it out along with the other phrases. -- Oliver P. 23:51, 12 Mar 2004 (UTC)
- Moot means rendered irrelevent. Anthony DiPierro 02:52, 13 Mar 2004 (UTC)
- Thanks. Actually, the dictionary does give a secondary meaning: "having no practical significance", which I suppose amounts to the same as what you say. But it says it's a term in US Law. If it means different things to different people, perhaps it's better to use a different word where there is risk of confusion. -- Oliver P. 06:05, 13 Mar 2004 (UTC)
Chinese origin?
The end of the origins section says "It was however known long before to Chinese mathematicians. " Could we either get some more details supporting this or remove this sentence? This is the first I'd ever heard of it.
(On further examination, it seems the person who added this sentence is an anonymous writer who has made no other contributions to Wikipedia. )
--Crunchy Frog 03:38, 13 Aug 2004 (UTC)
Rewrite of introduction
I did a complete rewrite of the introduction to the article and reformulated the church turing thesis. I tried to provide
- an understandable description of the thesis for the layman
- a precise and brief definition in terms of computable function.
The article still needs more work though.MathMartin 16:24, 7 Nov 2004 (UTC)
Copyrighted content
Some content of the page, the definition of algorithm for example, seems to be copied from [1] (http://plato.stanford.edu/entries/church-turing/) with only slight modifications. What should be done in such a case ? MathMartin 00:32, 8 Nov 2004 (UTC)
Has been there since day 1. I think it should be paraphrased into continuous sentences. Charles Matthews 09:15, 8 Nov 2004 (UTC)
Ah, but it was posted in 2001 to WP, while the Stanford page is copyright date is 2002. That may mean no reason to panic; it is conceivable that it was copied the other way. Charles Matthews 09:17, 8 Nov 2004 (UTC)
Physical CTT
I have some problems with the following text:
- Physical Church-Turing thesis (PCTT) states:
- Every function that can be physically computed can be computed by a Turing machine.
- This stronger statement was proven false in 2002 when William Fouché discovered that a Turing machine cannot effectively approximate any of the values of one-dimensional Brownian motion at rational points in time almost surely (with respect to Wiener measure; see reference below)
First, it is not obvious (to me) why this is stronger than the CTT. Couldn't a function be physically computable without an algorithm given (or known)?
Second, the paper in the references ("Arithmetical representations of Brownian motion", Journal of Symbolic Logic) was published in 2000, not in 2002. Not a big problem, but the same author did published a related paper in 2002 which is not mentioned in the article ( in "Advances in Mathematics").
Finally, and most importantly: The "complex oscillation" functions in Fouche's paper that cannot be approximated by a Turing machine are not functions that can be physically computed. At least, there is no obvious example of a "complex oscillation" that can be. Aleph4 21:19, 18 Feb 2005 (UTC)
"essentially the same?"
The article states:
- Since that time many other formalisms for describing effective computability have been proposed, including recursive functions, the lambda calculus, register machines, Post systems, combinatory logic, and Markov algorithms. All these systems have been shown to compute essentially the same functions as Turing machines...
(emphasis added.) Can we remove "essentially"? It seems to me that either those other formalisms can be proven equivalent in capability to a Turing Machine, or they cannot — "essentially" is just a noise word. On the other hand, if some of these formalisms cannot compute some functions a TM can compute (or vice versa), that is worth mentioning explicitly. Neilc 12:54, 24 Mar 2005 (UTC)
physically computable functions
The article states:
- Various variations of the thesis exist; for example, the Physical Church-Turing thesis (PCTT) states:
- Every function that can be physically computed can be computed by a Turing machine.
- This stronger statement was proven false in 2002 when Willem Fouché discovered that a Turing machine cannot effectively approximate any of the values of one-dimensional Brownian motion at rational points in time almost surely
Can someone elaborate on what this means, exactly? For example,
- What is the definition of the set of functions that can be "physically computed", and how is this distinct from the normal notion of Turing computable functions?
- What does "almost surely" mean in the last sentence?
- What are the implications of this result?
I don't know the answer to any of these questions, but perhaps someone who does can flesh out the article. Neilc 13:04, 24 Mar 2005 (UTC)
???
I thought the church turing thesis was: if two systems, for every measurable case, starting from the same initial state, and given the same sequence of inputs, produce the same sequence of outputs, then the two systems are, in every measurable sense, identical; equivalent. A special case of this being artificial intelligence, laconically stated: if a computer can not be distinguished from a human, it is intelligence.
For whatever theory that is, which I have always known as the church-turing thesis, regarding the philosophy section of the article, the idea dates further back, with respect to artificial intelligence, to Fredrich Nietzsche's essay "On truth", wherein he states that intelligence is simulation. (not analysis) Kevin Baastalk 06:55, 2005 Apr 2 (UTC)
I Need some Help please!!
Hey!!
what's up!! I'm Claudia from Mexico and I need some information about the church-turing thesis and the turing machine. Some friends of mine and I have to do a homework about the turing machine and we need a contact of another country who could help us with some information. We think the information on this page is very good and interesting, that's why we need some of you to help us. We hope to hear from someone who could be our contact very very soon!!! You can write to: cala_sc@hotmail.com please, and I'll tell you what is the information that we need.
Love, Claudia and friends!!!