Talk:Church–Turing thesis

From Wikipedia, the free encyclopedia

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 1 Tautology 2 Epistemology 3 NPOVing 4 Chinese origin? 5 Rewrite of introduction 6 Copyrighted content 7 Physical CTT 8 "essentially the same?" 9 physically computable functions 10 ??? 11 I Need some Help please!! 12 Attribution to Turing is required 13 Introduction: "It is generally assumed..." 14 Introduction too long (revision as of May 30 2006) ? 15 church?? 16 Thesis versus proof -- what would be required to disprove the Church-Turing Thesis 17 Quantum computers 18 "Humans are Computers" argument 19 Grammars 20 On the origin of the Church thesis

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

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

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

"Moot" means "debatable." Otherwise, any word can mean anything that you want it to mean.Lestrade 22:22, 16 January 2006 (UTC)Lestrade

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

[edit] Rewrite of introduction

I did a complete rewrite of the introduction to the article and reformulated the church turing thesis. I tried to provide

1. an understandable description of the thesis for the layman
2. a precise and brief definition in terms of computable function.

The article still needs more work though.MathMartin 16:24, 7 Nov 2004 (UTC)

[edit] Copyrighted content

Some content of the page, the definition of algorithm for example, seems to be copied from [1] 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)

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

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

I think essentially must mean that the functions (esp their input and output data) are represented in different ways. This means, that you can translate a program of, say, a Turing-machine to a lambda-calculus expression, but then the Turing-machine accepts words built of its alphabet as input, and such a word can easily (this is vague) be translated to a lambda-expression which, when applied to the first expression, produces the same result (and halts iff) the Turing-machine when fed with the word. The problem is that there are lambda-expressions that don't correspond to any valid input of the Turing-machine, and the translation can do anything if you feed such an expression to it. Thus, you can't really say it would calculate exactly the same function.

On the other hand, the word "essentially" is really a bit confusing, and could induce some doubt in whether these computation models are truly equivalent. So, I'm in a half-mind on whether the word should be removed or kept. -- B jonas 22:33, 13 December 2005 (UTC)

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

see article Almost surely 131.107.0.73 23:46, 31 May 2006 (UTC)

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

[edit] ???

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 Baas^talk 06:55, 2005 Apr 2 (UTC)

You might want to look up Turing_Test - tw

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

[edit] Attribution to Turing is required

We seriously doubt that Allen Turing refered to his own machines as "Turing machines". Until a reference (including document and page number) is applied here, "in Turing's own words" must go. wvbaileyWvbailey 16:21, 11 January 2006 (UTC)

In his 1936 paper Turing referred to his machine (i.e. the customary machine, the common, garden-variety Turing device) as an "automatic machine" -- an "a-machine." He defined but didn't use, a "choice-" or "c-machine" (page 118 in Undecidable) and in a later paper (1939) defined the "oracle-" or "o-machine" (p. 167 in Undecidable) wvbaileyWvbailey 19:18, 21 August 2006 (UTC)

[edit] Introduction: "It is generally assumed..."

"It is generally assumed that an algorithm must satisfy the following requirements". This statement should be sourced. It would be good if there was a reference either to the 4 requirements or the nearest thing to them. Pgr94 11:38, 29 May 2006 (UTC)

This is a very interesting question. I pulled out my cc of Donald E. Knuth: The Art of Computer Prograamming, Second Edition, Volume 1/Fundamental Algorithms, Addison-Wesley, 1973.

'Besides merely being a finite set of rules which gives a sequence of opertions for solving a specific type of problem, an algorithm has five important features:"(p. 4)

"1) Finiteness

2) Definiteness

3) Input

4) Output

5) Effectiveness "(p.4-6)

With respect to (1) Finiteness:

"An algorithm must always terminate after a finite number of steps" (p. 4).

" We should remark that the "finiteness" restriction is really not strong enough for practical use; a useful algorithm should require not only a finite number of steps, but a very finite number, a reasonable number" (p. 6, Knuth's italics)

With respect to (2) Definiteness:

"Each step of an algorithm must be precisely definied; the actions to be carried out must be rigorously and unambinguously specified for each case" (p. 5)

With respect to (3) Input:

"An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins. This inputs are taken from specified sets of objects" (p. 5)

With respect to (4) Output:

"An algorithm has one or more outputs, i.e., quantities which have a specified relation to the inputs" (p. 5)

With respect to (5) Effectiveness:

"'This means that all of the opertions to be performed in the algorithm must be sufficiently basic hat they can in principle be done exactly and in a finite length of time by a man using paper and pencil" (p. 6).

What I will do is munch this over and rewrite the lead-in para. to reflect Knuth, and look at Wiki's definition of 'algorithm' etc. I am a believer that the algorithm is actually the machine, not just a list of instructions, but the machine itself, programmed to do xyz. But that's just my definition; Knuth's will suffice.wvbaileyWvbailey 15:13, 29 May 2006 (UTC)

Well, in order to interpret the "list of instructions" correctly and precisely (for example, for use in a very formal mathematical proof), the underlying machine model the instructions operate on needs to be specified, so in that sense, you need both the instructions and the underlying machine model to fully specify an algorithm.

This is my belief as well, in part... but there is a more serious matter at stake. I broached this with the editors of Scientific American re an article by Chaitin and randomness/algorithmic complexity theory. Never heard another word. But there have been no letters to the editor re Chaitin's article, either. He was waxing about how the algorithm of pi is fairly trivial, but it creates a string of random numbers ad infinitum. The problem is: the results of the previous calculation in the pi sequence must be used for the next calculation, and so the state machine equivalent (i.e. Turing's "complete configuration" that includes both the result of the calculation and the next instruction) that does this grows and grows and grows...to infinity. So I don't know what the hell Chaitin is talking about. He just measures the "algorithm complexity" by counting the number of instructions. But if you calculate the "gate equivalence" (or bit equivalence, whatever) of the machine-as-algorithm as it operates, it grows to infinity as well. There is a grave disconnect here. While I agree with Chaitin that a person can just count the instructions in the description of the algorithm I am not sure that that description IS the algorithm. The upshot is: given a bad premise, an argument is junk. And I propose that Chatin's premise is bad, and his argument is junk. wvbaileyWvbailey 18:14, 31 May 2006 (UTC)

It gets worse: here's the result of a bit of research: Church in his paper of 1935 -- where he equates "recursive" and "effective calculability" clearly considers "an algorithm" to be an active process:

"For example, in the case of a function F of one positive integer, an algorithm consists in a method by which, given any positive integer n, a sequence of expresions (in some notation) En1, En2,..., Enrn, can be obtained... when n and all the expressions Eni up to and including Enrn are given, the fact that the algorithm has terminated becomes effectively known and the value of F(n) is effectively calculable."(p. 100, Undecidable)

A few lines further he goes on to describe a "Godelization" of the expressions Eni, and again mentions 'termination': "...if the algorithm has terminated with Enk"(ibid). So what is he saying? Is he defining the "algorithm" as (i) a list of instructions, or (ii) a sequential process that leads to a sequence of sub-results and then finally, termination? I read the later (Rosser and Kleene are more ambiguous and seem to lean the other way). but I read the same thing in Turing's 3rd proof, where he has to Godelize a huge expression as a "logical product" of a bunch of intermediate steps. In other words: Church/Turing-as-computer plus a list of instructions becomes "the algorithm." Is "he-or-it that calculates" a hidden assumption in the definition of "algorithm"? wvbaileyWvbailey 00:40, 1 June 2006 (UTC)

Of course, if the computation model being used is a Turing machine, then "list of instructions" and even "the machine programmed to do xyz" is not really meaningful. The Turing machine model is, mathematically, basically an FSM extended with a read/write head processing a one-end, infinitely long tape where the input resides. There is no concept of "programming" as we have in modern computers--each Turing machine by definition carries its own distinct "program" as defined by the control FSM (so the machine is the program).

Apparently you are not aware of the "universal machine". Apparently you've never programmed a Turing machine or a Post-Turing machine. I have, with my own little fingers, and can give you examples ("multiply" is the classic) chapter and verse. In fact I've written the universal program for the Post-Turing machine I built from scratch. You use all sorts of principles from programming. Its just harder (damned harder!). Subroutines in particular you have to use otherwise you go raving mad. Turing even used subroutines in his U-machine description.wvbaileyWvbailey

In computer programming however, because we have just one dominant computation model being used (the von Neumann architecture), because that model does have the concept of "programmability", and because in the programming context we rarely need to concern with all the precise details of the machine, "algorithm" can be thought of as just the program, ie. "list of instructions".

I trust that the algorithm article will probably discuss this better and in more details. 24.16.39.33 04:11, 31 May 2006 (UTC)

Your trust is misplaced. The algorithm article needs a hosing. But this stuff is very hard and some is quite controversial and folks-as-editors have a tendancy to cut when they shouldn't. If I get the courage up maybe I'll broach this on the algorithm page, where I believe we both admit it belongs.wvbaileyWvbailey 18:14, 31 May 2006 (UTC)

[edit] Introduction too long (revision as of May 30 2006) ?

My sense is that right now as of the revision on May 30 2006, the intro is a bit too long and goes into more details than it should. That is, I think a good deal of the intro should probably be moved into other sections, or simply cut.

I wrote this to answer a question posed by another writer. If I could trust the "editors" that fart with the algorithm page to leave some of this alone, then i would agree that all the "algorithm" stuff could be cut and moved to "algorithm". In fact I did that, and it got reverted (if you look at the discussion page for algorithm you'll see a copy of it). So I can't win. I frankly don't what to do. The algorithm page is a mess too. I have entered a bunch of historical stuff on the algorithm disucssion page that is really interesting -- you may even recognize some of the quotations. Maybe I can rework this at some point. But everything gets reverted.

I'm particularly not happy with that tacky part about algorithms that was copied from Knuth. The original statement of the Church-Turing thesis doesn't even use the word algorithm for Pete's sake, so why are we dragging it into the intro of all places?!?!?

Actually it does. Sorry, but you're wrong. I presume you've read Kleene's original paper (cf Undecidable page 273) and that you have forgotten his entire discussion where he defines his "Thesis I" is titled 12. Algorithmic theories. Here's an example. This is his Theorem VII verbatim (a page later):

Theorem VII. There exists no complete algorithm theory for either of the predicates (Ex)T[sub1](a,a,ax) and (x)T[bar][sub1)(a, a, x)" [m boldface, p. 275, Undecidable).

In other words, if you don't know what an algorithm is, this "thesis" is meaningless.

What I wrote isn't tacky at all. It is in answer to another writers question. Read the stuff on the algorithm discussion page. it turns out the quotes there from Church and Kleene in particular form the basis of the Knuth quote, to a degree. I also found something in Bell and Newell (1971) that has more than passing resemblance to the Knuth quote. So presumably, eventually the Knuth stuff will go away, but not until the algorithm page gets straightened out (I hope). At least you didn't revert it, and you opened a dialog.wvbaileyWvbailey 13:18, 31 May 2006 (UTC)

I would say that the whole intro section from "It is generally assumed..." to "...given unlimited time and memory.)" should be ruthless stripped out, and maybe given another home elsewhere later in the article (if at all). Intros should avoid being cluttered like the way it is now. 24.16.39.33 04:28, 31 May 2006 (UTC)

Changes to opening paragraphs:

1. Restructured opening paragraphs, removing forward references and formal content in informal description.
2. renamed section "Introduction" "Algorithms" as it isn't an introduction but a definition of an algorithm.
3. We now need a new introduction.

Pgr94 08:08, 15 June 2006 (UTC)

[edit] church??

wdf? what does the Church got to do with anything ?

A man's name: Alonzo Church. wvbaileyWvbailey 14:06, 11 June 2006 (UTC)

[edit] Thesis versus proof -- what would be required to disprove the Church-Turing Thesis

This is extracted from Talk: Turing machine

Your first paragraph is right; classical computability theory is about functions from the natural numbers to the natural numbers, and similar things like sequences of natural numbers. The idea behind computation is that it can be carried out by a person, given unlimited time. The fact that a computable function might also be computed by an analog device isn't a big deal. If you had a supposed counterexample to the Church-Turing thesis, and this example involved an analog device, you would need to show that the analog device could be simulated by a person with pencil and paper in order to convince me that you actually have a counterexample to the Church-Turing thesis (instead of a counterexample to some conjecture from physics). [CMummert 21 July 2006]

I just want to add this as a reference for future readers (or myself). CMummert's point is supported by the following quotation to be found in Boolos and Jeffrey (1974, reprinted 1980, 1989, 1999):

Although this thesis ('Church's thesis') is unprovable, it is refutable, if false. For if it is false, there will be some function which is computable in the intuitive sense, but not in our sense [of 'a computing machine, or by a human who is capable of carrying out only very elementary operations on symbols']. To show that such a function is computable in the intuitive sense, it would be sufficient to give instructions for computing its values for all (arbitrary) arguments, and see that these instructions are indeed effective...To show that such a function is not computable in our sense, one would have to survey all possible Turing machines and verify (by giving a suitable proof) that none of them compute that function. [The authors promise us some exampls in CH 4 and 5 that are not computable by either Turing machines or in any intuitive sense.] Then if Church's thesis is false, it is refutable by finding a counterexample; and the more experience of computation we have without finding a counterexample, the better confirmed the thesis becomes." (Boolos and Jeffrey (1974 etc), page 20).

Thus the thesis: "On Earth the sun rises in the east" is not provable but accepted as probably true by enumeration (probability); if only once it rises in the west then the thesis is proven false.

wvbaileyWvbailey 17:50, 21 August 2006 (UTC)

[edit] Quantum computers

The article says:

If quantum computers are physically possible, they could invalidate the Strong Church-Turing Thesis...

But quantum computers ARE physically possible, aren't they? In a class I took on Quantum Computing, it was mentioned that a 7-bit quantum computer had been built, and had been used to implement Shor's factorization algorithm, factoring the number 15. This is confirmed here: Integer factorization. So the number 15 was factored in polynomial time, so the Strong Church-Turing thesis has been disproven.

It makes little sense to talk about factoring one number in polynomial time; computational complexity measures the asymptotic growth of running time, not the running time for particular inputs. So it would have to be physically possible to build quantum computers with arbitrarily many qbits to invalidate the "Strong Church-Turing thesis".

Whether quantum computers constitute a "reasonable" model of computation is another question.

In any event, quantum computers can be simulated (albeit inefficiently) by Turing machines, so they do not enlarge the class of computable functions although they may increase the class of efficiently computable functions. In short, quantum computation has no effect on the genuine Church-Turing thesis. CMummert 22:02, 13 October 2006 (UTC)

The asymptotic growth of the running time of the algorithm has been proven to be O(n³), it just hasn't been physically realized for large n yet. Also, we are not just talking about factoring one number in polynomial time; I'm sure that 7-bit quantum computer could be used to run Shor's algorithm on the number 6, and the number 3. In the case of 3, we wouldn't want the algorithm wouldn't factor 3, we would just want it to output that 3 is prime. So we would have to include a primality test as part of the algorithm; using the AKS primality test would just make it O(n¹²) instead of O(n³). So, on the number 3, represented with 2 bits, the algorithm would take 2¹² steps in its physical realization. On the number 6, represented with 3 bits, the algorithm would take 3¹² steps. On the number 15, represented with 4 bits, the algorithm would take 4¹² steps. So the running time is growing as a polynomial in the size of the input.

Also, I don't think we have to be able to physically build quantum computers with arbitrarily many bits to invalidate the thesis. After all, it's physically impossible to build a classical computer with arbitrarily many bits. We can't build a classical computer one with 10⁵⁰⁰ bits.

Navigatr85 13 October 2006

I know that there are polynomial estimates for the running time; the original post, however, did not seem to understand the difference. Moreover, whether quantum computes are a "reasonable" model of computation doesn't depend on whether they can be physically constructed.

I encourage someone (not me) to edit the part of this article about the Strong Church Turing thesis, so if you think it needs changed plase feel free to improve it. It might be worth finding an actual print source for the strong claim, to see what that author thinks are the necessary assumptions on reasonable models of computation. CMummert 23:19, 13 October 2006 (UTC)

[edit] "Humans are Computers" argument

Hasnt it been argued, on the basis of this thesis, that human beings are turing complete computers because we can execute programs with pencil and paper? If the universe is a turing machine, and assume there is nothing super-physical about humans (such as a soul), then we must be computers, by definition. I know not everyone believes this, but some do. 129.210.199.37 06:31, 5 November 2006 (UTC)

There is some suspicion that humans can "compute" more than Turing machines -- for example, some would assert that an oracle machine would never have been "computed" (come about as a result of an "algorithm") by a computer (a machine following an algorithm). Daniel Dennett the philospher believes that this comes about because of randomness, and a (human-mind-based-) algorithm that uses randomness + pattern recognition to concoct original output. (This is not the same as a non-deterministic Turing machine because the patterns are stitched together from pieces of other patterns -- there may be an "effectively-infinite" aspect to this that defeats a non-deterministic TM.) Some folks make a distinction between computor and computer, and between machine-computation versus human-acting-as-machine computation (Soare). Others (Gandy) argue that by its intrinsic nature the universe, while perhaps not a computer itself, "is capable of" Turing-complete machinery but puts restrictions on computers because of the nature of space-time (most importantly the speed of light -- input cannot proceed to output without experiencing delay and therefore the notion of simultaneity). John Searle the philosopher of Chinese room fame believes that numbers are somehow 'in the mind' and are more than syntax because they have "meaning" for the mind; a computer on the other hand experiences no meaning from the numbers and is just a syntactical symbol-manipulating algorithm. These are the arguments that I have encountered aka computers (there are others for sure, probably as many arguments as there are mathematicians and philosophers). My own suspicions follow along the lines of the philosophers; I also suspect "analog computation" (using non-discrete symbols) may be at work in the mind, this may boil down to the Dennett argument.wvbaileyWvbailey 14:49, 5 November 2006 (UTC)

[edit] Grammars

Another form of the thesis (usually referred to as Church's thesis) is that any language given with some constructive definition can be generated by a grammar. --Tgr 11:30, 31 January 2007 (UTC)

[edit] On the origin of the Church thesis

I see that Kleene (1943) is receiving primary credit for this thesis. Why? I was always taught that it originated with Alonzo Church in connection with his investigations of effective calculability, culminating in 1936 with the idea that anything which is effectively calculable can be embodied in the lambda calculus. What's up? Sheerfirepower 17:44, 9 February 2007 (UTC)

The best reference is the 1996 paper Computability and Recursion by Robert Soare [2]. He did a lot of research into the various forms of Church's thesis (which he calls the Church/Turing thesis). CMummert · talk 17:59, 9 February 2007 (UTC)