Talk:Church–Turing thesis/Archive

comment by Jerzy

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)

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)

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

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

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)

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)

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)

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)

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)

???

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

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!!!

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)

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)

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)

church??

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

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

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)

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)

Actually, I realize that I was wrong. It has never been proven that a polynomial-time integer factorization algorithm could not exist for a classical computer. Even if one accepts quantum computers as a reasonable model of computation, and even if a quantum computer with a large number of bits is built, that wouldn't invalidate the Strong Church-Turing thesis yet. In addition to that, we would have to prove that factorization is outside of P for Turing machines, and then it could be invalidated. --Navigatr85 23:56, 15 August 2007 (UTC)

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

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)

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)

This terminology "Church-Turing thesis" is not in accord with what the other studies say, especially Kleene, Rosser, Feferman, Sieg, etc. I can give you the references if you wish. Pierre de Lyon 17:01, 21 April 2007 (UTC)

Unbounded nondeterminism

I feel this subject is not particularly relevant to the CTT, when CTT is interpreted to mean "any algorithm can be implemented on a Turing machine" because unbounded nondeterminism isn't an algorithm (it can't be carried out by a person with only pencil and paper).

The CTT does not say "every possible generalized sort of computation can be carried out by a Turing machine" because that is obviously false. CMummert · talk 22:46, 11 April 2007 (UTC)

Of course if you give a person an arbiter as well as pencil and paper, then they can perform calculations involving unbounded nondeterminism. And arbiters are very simple devices! So what are the grounds for including analog devices such as pencil and paper but excluding simple digital devices such as arbiters? In this day and age surely the relevant issue is "What can be computed by a person using a digital information technology? And how does that compare with what can be computed by nondeterministic Turing machines?"--71.198.216.63 21:48, 12 April 2007 (UTC)

I fear you are trying to redefine the CTT into something that it is not. CMummert · talk 22:20, 12 April 2007 (UTC)

The CTT is often misinterpreted to refer to "any computation". See SEP

It seems that the discussion in the SEP article is completely unaware of how concurrent computation subtly affects the formal results.

Also there is a great deal of confusion in the literature about "fairness". See unbounded nondeterminism.--71.198.216.63 21:48, 12 April 2007 (UTC)

1Z 13:09, 12 April 2007 (UTC)

Church-Turing thesis (moved from user discussion page)

You changed Church-Turing thesis to claim that it had been disproven. This is certainly not the case. Please feel free to discuss your changes on the talk page of the article. CMummert · talk 10:49, 12 April 2007 (UTC)

The Church-Turing thesis has not been disproved. However, it needs to be stately precisely which was not done in the previous version of the article. It is very important to distinguish between computable functions and computability (computations).--71.198.216.63 16:09, 12 April 2007 (UTC)

I have noticed that you have been adding this distinction to several articles. It isn't particularly standard in the literature, as far as I can tell. CMummert · talk 17:23, 12 April 2007 (UTC)

The distinction is a standard one in the published literature on concurrent computation and is also standard in the literature on arbiters. --71.198.216.63 21:57, 12 April 2007 (UTC)

But the CTT has nothing to do with arbiters or concurrent computation. The way that the CTT is ordinarily conceived in recursion theory, it states a relationship between what a human can theoretically do with pencil and paper vs. what a Turing machine can theoretically do. Concurrent computation is an important engineering problem but I can't see how it is related to theoretical computability. CMummert · talk 22:15, 12 April 2007 (UTC)

Turing, Church, Kleene, 'etc.' were concerned with what could be intuitively computed. Recursion theory came along as one attempt to formalize these intuitions. It just so happened that Turing, Church, and Kleene never conceived of concurrency because email, computer I/O with interrupts, etc. were not part of their world at the time. However, they were very concerned with the breadth of their notions and would no doubt embrace concurrent computation as belonging with the realm of the intuitively computable and consequently part of their concerns with theoretical computability. They were not as hung up on pencil and paper as you seem to imply. .--71.198.216.63 22:32, 12 April 2007 (UTC)

In Turing's original paper, where he invented the Turing machine, he motivated it by explicitly comparing it to the behavior of a person with pencil and paper. The CTT developed from that comparison. As I said higher on this talk page, you seem to be trying to redefine the CTT in some nonstandard way. Since I am confused, maybe you could provide me with some peer-reviewed references that explicitly deal with the relationship between the CTT and concurrent computation. The standard way of treating the CTT in recursion theory is to compare functions computable via (deterministic) algorithms with Turing computable functions. CMummert · talk 22:40, 12 April 2007 (UTC)

It's true that Turing mentioned the use of pencil and paper in motivating Turing machines. But later in formulating CTT, Turing, Church, etc. became very concerned with generality trying to convince themselves and others that they had formally captured the intuitive notion of computability

The problem here is to write an encyclopedia article on CTT. So the various conceptions and criticisms are very much apropos. There is a vast literature on nondeterministic computation and concurrency. You might take a look at the following:

• Gordon Plotkin. A powerdomain construction SIAM Journal of Computing, 5:452-487, September 1976.
• Will Clinger, Foundations of Actor Semantics. MIT Mathematics Doctoral Dissertation, June 1981.
• Carl Hewitt, What is Commitment? Physical, Organizational, and Social COIN@AAMAS. April 27, 2006.--71.198.216.63 23:25, 12 April 2007 (UTC)

I looked through the first and third of those; neither one seems to discuss the Church-Turing thesis. Can you explain to me in a hundred words exactly how Plotkin's paper (on formal semantics) is supposed to reflect on the CTT? I have a digital copy of the paper, so you can use page numbers if you wish.

I am actually quite interested to find out what is going on here. CMummert · talk 23:52, 12 April 2007 (UTC)

Researchers had the goal to characterize computability in a way that was more general than by just demonstrating that a number of concrete computing models are equivalent, e.g., Turing machines and the lambda calculus. Dana Scott made a fundamental advance with the development of denotational domain models. Gordon Plotkin extended denotational models for nondeterminism. However, concurrency was more challenging. Will Clinger published the first denotational model for concurrent computation. Carl Hewitt developed a simpler way to construct concurrent denotational models.--70.231.229.132 00:57, 14 April 2007 (UTC)

I don't understand how this relates to the Church-Turing thesis. CMummert · talk 01:52, 14 April 2007 (UTC)

The Church-Turing thesis was an attempt to characterize computability. At the time the best that they could do was to point a few concrete models (e.g. nondeterministic Turing machines and the lambda calculus) and note that they were equivalent. Consequently they completely missed concurrent computation. The denotational approach is more general and powerful.--64.134.12.226 14:00, 16 April 2007 (UTC)

The Church-Turing thesis is ordinarily conceived as a characterization of the class of computable functions. In this context it states that the functions computable by a person with pencil and paper are exactly those computable by a Turing machine. What I don't understand is how concurrent computation relates to this characterization - a person can only do one thing at a time, and a Turing machine can only do one thing at a time. So concurrency seems like a red herring in this context. It's like saying the statement "I can ride a bike anywhere I can walk" is related to my ability to fly in an airplane. Concurrency is important for the theory of programming languages and is an important engineering problem, but I don't see that it has a close connection to the theory of computable functions. CMummert · talk 14:19, 16 April 2007 (UTC)

Church and Turing were not so narrow minded as you seem to imply. They were very concerned with the generality of their characterization of computability and no doubt would have embraced concurrent computation and denotational semantics. The unfortunate restriction to mathematical functions is just dogma.--64.134.12.226 14:33, 16 April 2007 (UTC)

I read the section re "unbounded determinism and non computablity". I am unconvinced -- the description there is missing an important something. In order to convince yourself that the testing-machine in question solves the halting problem for any machine you have to submit a copy of testing-machine itself to the (same) testing-machine and see what happens. This is what Turing did in his first proof. When the "outer machine" "becomes/emulates" the inner machine to test it, it gets trapped into making infinite copies of itself. (So you put a watchdog around this machine ... (what watchdog criterion would you use?) but this machine+watchdog becomes the new machine to act as both "tester" and "tested"... ad infinitum). This constructive form of proof is quite different from the more common "halting proof" of Martin Davis (Kleene discusses it and Minsky gave a version of it in his book), the "simpler" halting proof given here in wikipedia. In the original original Turing proof, the testing machine, although it seems to invoke the Cantor diagonal method, never gets to print its own diagonal "bit" representing "halt" or "not-halt" (as Turing noted). wvbaileyWvbailey 17:03, 13 April 2007 (UTC)

A good reference on the problem of going beyond Church thesis (worth reading) is

Peter Wegner, Dina Q. Goldin: Computation beyond Turing machines. Commun. ACM 46(4): 100-102 (2003)

See other articles by Peter Wegner on the same subject in DBLP. Pierre de Lyon 08:57, 14 April 2007 (UTC)

Unfortunately the above references do not seem to be aware of the work on denotational semantics and concurrent computation.--64.134.12.226 14:39, 16 April 2007 (UTC)

Peter Wegner is not aware of denotational semantics and concurrent computation. Good joke! Just look at DBLP and you will see that he has cosigned papers with Luca Cardelli et Robin Milner among others and be reassured he knows them. Pierre de Lyon 16:43, 21 April 2007 (UTC)

Talking about Church. Church was not interested by machines and computers, he was interested by logic and especially Principia Mathematica for which he invented lambda calculus. Pierre de Lyon 08:57, 14 April 2007 (UTC)

Concurrency

The CTT is a definition of computability. This argument, that real-time or interactive computation is a different definition of computability, is also made here by Selim Akl. I would not say that this warrants a rewrite of the article, but surely a paragraph on "other meanings of computability". Septentrionalis PMAnderson 17:43, 20 June 2007 (UTC)

Non computable functions

I added a section on non computable functions, with the example of the busy beaver, which I forget to sign. Pierre de Lyon 08:57, 14 April 2007 (UTC)

Skeptical Scientist's edit of History section

-- a work in progress (added by Wvbailey) -- --- Expanded history is now moved to Church-Turing thesis: History -- wvbaileyWvbailey 01:59, 2 September 2007 (UTC)

Soare makes his appearance again. . . others have tread this ground including Gandy. What I will do here is write down as best as I can a time line using as references the papers compiled by Martin Davis in The Undecidable (U), Jean van Heijenoort (vH), Stephen Kleene (1952) (K) and Godel's biography by John Dawson (D), Robin Gandy 1980 (Ga), Soare 1995 (S), Sieg 2002 (Sieg) and + Merriam-Webster's New Collegiate Dictionary (MW). The intent here is to be as brutally-true to the published facts as published as is possible. wvbaileyWvbailey 14:45, 20 June 2007 (UTC)

Where do the phrases Church's Thesis and Turing's Thesis come from?

Kleene's paper of 1943 repeats his statement of "Thesis I" (p. 300) first proposes Church's Thesis as "Thesis I" U p. 274). He uses the phrase Church's Thesis formally in his 1952 text (K p. 317) and later in the same text the phrase Turing's Thesis (Kleene 1952:376).

Summary: In 1900 David Hilbert posed 23 problems (cf Hilbert's problems) to mathematicians of the new century. The impetus -- the propelling push -- behind the Church Thesis and Turing Thesis was Hilbert's second problem (the completenes of mathematics) and Hilbert's tenth problem (are all Diophantine equations calculable?). By 1928 Hilbert had refined his second problem into three distinct questions: (1) Is mathematics complete? (2) Is mathematics consistent? (3) Is mathematics decidable? The third question also impacted his Diopantine problem #10. Hilbert believed that the answers to all three would be YES. (For what this means, see more below at Hilbert 1928).

In 1930, as luck would have it, at the meeting being held to honor Hilbert's retirement, a young mathematician named Kurt Gödel tentatively presented a devastating (at least for Hilbert) paper: the answers to the first two questions were a resounding NO. This discovery, however, left the last question -- is mathematics decidable? -- dangling.

The problem was: the answer to this question requires a precise defintion of "calculable" or "computable", and in 1930 a precise definition was wanting.

Effective method, Effectively calculable: The notion of, what J. B. Rosser called an effective method, leading to a function effectively calculable (cf Minsky at Algorithm characterizations) was first defined by Church (1934) in the context of (1) his version of a human-based symbol-manipulation formalism called "the λ-calculus and (2) the Gödel-Herbrand-Kleene version of human-based symbol-manipulation formalism called general recursion.

There was one little, niggling problem, however: Both are "intuitively" defined and presented. Why would should someone believe that either is sufficient to calculate anything and everything that is "calculable"?

Recursion:

The idea behind "recursion" is straightforward: "recursion" comes from "to recur", "to happen again". For a mathematician it means to: "Plug back into an equation the result from a previous calculation." One must start with an initializing number (often 0) or numbers, but thereafter the process of plugging-in (as propelled along by a human or a machine-computer) continues until something (counting up or down, usually) terminates the recursion ("primitive recursion"); otherwise the recursion may continue ad infinitum ("general recursion") as shown in the following example:

Example to create an approximation to 1 - e^-kt (the diffusion equation):

• 1 Start with Y = 0.

  2 Evaluate Y_new <= Y + 0.5*(1 - Y)

  3 Let Y <= Y_new

  4 Repeat steps 2 and 3 until boredom sets in: { 0, 0.5, 0.75, 0.875, 0.9375, 0.96875, 0.984375, 0.9921875, 0.99609375, 0.9980469, 0.998046875, etc. etc. )

As presented nothing except boredom will "terminate" this recursion; efforts will get the numbers closer and closer to 1 will never (ever) succeed.

Primitive Recursion: "an intuitive theory":

Why would anyone believe that the notion of: "Plug back into an equation the previous result" would result in any calculation that is possible? Kleene called this "an intuitive theory" (Kleene 1952:217). But one reason is that: Our familiar arithmetic ( +, -, x, /, exponents, etc.) stripped to their bare essentials is just Primitive recursion. (Kleene also called it "Definition by induction" (Kleene 1952:217)). Primitive recursion is just the "zero", "successor" and "induction" of the Peano axioms working together with two "formation rules" to become, in Kleene's version, just 5 rules of how to get new numbers from "functions". In particular, the fifth Peano axiom is the "axiom of induction", and induction is the repeated reuse of a previous calculation. " . . . functions definable by induction in an elementary manner . . . will be called 'primitive recursive'." (K p. 219). So there were good reasons (i.e. Dedekind's and Peano's work of the late 1800s) to believe that "recursion" was sufficient.

General recursion: a patch on the intuitive theory:

In 1931 Kurt Gödel framed his Hilbert-shattering paper in terms of what is now known as "primitive recursion". But a few years previous (1927-1928) Hilbert's students and associates had found "a hole" in primitive recursion. Perhaps here is why Gödel was so suspicious of recursion being able to calculate everything that is calculable. The hole being what happens when a function is defined by recursion with respect to two variables (cf Godel in U. p. 69 footnote 33)). In 1934 Gödel, in his lectures at Princeton as transcribed by Alonzo Church's students Stephen Kleene and J. B. Rosser attempted to plug the hole. At the behest of their professor the two picked up this torch; Kleene refined the matter further by adding a sixth rule (the mu-operator) that allowed recursion to go on and on until a terminating condition is satisfied. Thus a function defined by general recursion can be a total function, or if not then possibly a partial function or undecided (i.e. a work in progress)).

Church's answer to The Entscheidungsproblem (the decision problem) is "undecidable":

After 1930, but simultaneously and independently, Church with Kleene and Rosser, Emil Post and Alan Turing were all hard at work trying to solve "the Entscheidungsproblem" -- the third of Hilbert's three questions of 1928.

At Princeton, Church, Kleene and Rosser were busily developing Church's proposed lambda calculus. But students Kleene and Rosser found a flaw in a general form of "lambda definability"; Kleene had to rewrite part of his PhD thesis because of it, and only a restricted lambda calculus survived. Worse, Gödel considered it suspect as an adequate definition of "calculability", as he did his own brand of Gödel-Herbrand "general recursion" -- he wasn't convinced; he recognized that both were "intuitive" definitions rather than being formed from primitive axioms.

So Church, in his paper of 1936 that shows the Entscheidungsproblem to be "undecidable", made use of both the lambda calculus and Gödel's general recursion, and together with results of Kleene's Church showed that the two were "equivalent". Church defines

"the notion, already discussed of an effectively calculable function of positive integers by identifying with the notion of a recursive function of positive integers (or of a λ-definable function of positive integers). This definition [these italics added] is thought to be justified by the considerations which follow, so far as positive justification can ever be obtained for the selection of a formal definition to correspond to an intuitive notion." (Church, U p. 100)

Nevertheless, the results were weakened by Gödel's doubts about the ability of his or any other recursion to define "calculability" -- and Gödel was the "inventor" of the very thing he himself doubted!

(Godel wasn't the only doubter: see Post 1936 below.)

Turing's proof that the Entscheidungsproblem was "undecidable":

Church's 1936 paper (presented 19 April 1935) pre-empted Turing by about a year (cf Hodges:112) and Post by a half-year. Turing was working in relative isolation in Cambridge UK, Church and his students were in Princeton NJ and Emil Post was in at New York University. The appearance of Church's paper [and a correspondence of some debate between Church and Post ?] encouraged Post to publish his definition of what Church was calling "effective calculability". But because this was received by Church's Journal of Symbolic Logic in October 1936, Turing's submission (received 28 May 1936) pre-empted Post's and "Church had to certify that [Post's] work had been completely independent." (Hodges p. 125)

This flurry of work must have been awful for Turing. Turing's teacher and mentor Newman sent a letter to Church stating that "your paper . . . had a rather painful interest for a young man, A. M. Turing . . ." (Hodges p. 111), and he asked Church if he would referee Turing's paper. He did and eventually invited Turing to study with him at Princeton; Turing would write his PhD thesis there.

After reading Church's and Kleene's papers of 1933 and 1935, Turing added in an appendix the sketch of a proof that the lambda-calculus and Turing computability were equivalent (Hodges p. 114).

Turing's work is deemed more satisfactory:

"But it was not obvious that 'a formula of the lambda-calculus' correcsponded to the notion of a 'definite method. Church gave several arguments for the assertion that any 'effective' method of calculation could be represented by a formula of the lambda-calculus. But the Turing construction was more direct, and provided an argument from first principles, closing the gap in Church's demonstration.

"So Alan was able to submit his paper on 28 May 1936 . . ." (Hodges p. 112)

Later developments:

Late 1960's: Turing's thesis is deemed more satisfactory by Gödel

Gandy 1980 disagrees with the belief that Turing defined (axiomatized) all forms of machine computation

The debate continues.

--- Expanded history is now moved to Church-Turing thesis: History--

I'm glad someone has time to do a much more complete history than I do. I just saw "first proposed in 1943" in the previous version, and wanted to have it reflect more of the history than that. I assume this is going to replace the history section in the article after you have it to your liking? skeptical scientist (talk) 18:03, 15 June 2007 (UTC)

P.S. I went back and fixed your typos. I fixed some typos in the quotes, as well, so you should do a diff to make sure I didn't fix anything that was a mistake in the original quote and should be left, but I'm guessing you retyped those quotes, and so most of the typos were unintentional. skeptical scientist (talk) 18:22, 15 June 2007 (UTC)

Thanks for fixing the typos. I added quite a bit more to the above-- I'll go over this all again and check. In my opinion it's much too long and too complicated to be used as it is; it needs to be "digested". But I just wanted to get it all in one place. Also, I need to reread and explore (and add) Gandy 1980 and 1988 (I have 1980 but not 1988), maybe some of Gurevich, maybe Soare, and I don't have Wilfried Sieg so I won't be "done" until I get a cc of him. This stuff is just so . . . what? confused? Bewildering? I think a lot of the confusion comes from "archaic" terminology, a confusion of terms in particular all the different "kinds" of recursion (primitve recursion, "general" recursion using the unbounded mu-operator rather than the bounded mu-operator, and the extension of both kinds of "recursion" to "partial recursion"). Kleene 1952 (and Minsky 1967 and Boolos-Burgess-Jeffrey 2002) prove that "general recursion" and "mechanical procedure" are "equivalent", whatever that means. I wasn't aware that some folks still take the lambda-calculus seriously until someone here at wikipedia insisted that the lambda-calculus was the only true way. wvbaileyWvbailey 20:03, 15 June 2007 (UTC)

• Apparently the first non primitive recursive function is due to Sudan in 1927. Pierre de Lyon

Yuri Gurevich

User:hmoraldo added:

These days, this paper has been in the news: [[3]]. I think something about this should be added to the page, as it's important news for the Church-Turing thesis, and Yuri Gurevich is well known in this field. Hmoraldo 18:48, 18 July 2007 (UTC)

This is interesting -- do you know if this article has been peer-reviewed and submitted to a journal? (That is the criterion I use for adding to an article, and not that it just appears on the web.) I've downloaded and will read. I've referenced Gurevich on the algorithm characterizations page but another contributor is having a fit (about Gurevich's point-of-view and my contention, consequent to Gurevich's "divergent" P.O.V. and dialog with other wiki contributors and readings etc, that "algorithm" is a word yet-to-be formally defined). About six months or a year ago I corresponded with Gurevich directly to try and figure out what his "thesis" is; I was left confused, and I cannot claim I understand it. wvbaileyWvbailey 16:49, 20 July 2007 (UTC)

Gurevich is essentially doing the same thing Turing did when Turing argued that any "effective procedure" could be simulated by a Turing machine. But Gurevich is using a different model of computation, which he calls an "Abstract State Machine", and a different set of postulates about a general "effective procedure". Time will tell whether Gurevich's work is influential in the computation community. For the moment all that can be said is that Gurevich has proposed a alternative complete model of computation and an argument for a version of Church's thesis for this model of computation. — Carl (CBM · talk) 17:58, 28 August 2007 (UTC)

Turing Machines and Computers Not Equivalent

I take issue with a statement in this article:

"Furthermore, a computer can theoretically run any algorithm; in other words, all ordinary computers are equivalent to each other in terms of theoretical computational power, and it is not possible to build a calculation device that is more powerful than the simplest computer (a Turing machine)."

because the inference is that a calculation device could be constructed that was as powerful as a Turing Machine.

Such a machine can never be constructed because an unconstrained Turing Machine has an infinite tape and to be equivalent a computer would likely have to have an infinite memory. A computer with infinite memory cannot be constructed.

The assumption that they are equivalent has led to grievous errors in computation.

I have not finished researching this issue, but at first glance it appears that the question "is a finite length tape Turing Machine equivalent to an infinite tape Turing Machine" may be undecidable.

I would prefer that this statement in this article be worded:

"Furthermore, a computer can theoretically run any algorithm; in other words, all ordinary computers are equivalent to each other in terms of theoretical computational power, but it is not possible to build a calculation device that is as powerful as the simplest computer (a Turing machine)."

I'm going to change it if there are no serious objections.

Alan A. Jorgensen

Softtest123 17:51, 28 August 2007 (UTC)

The Church-Turing thesis is not about real computers at all, but about (abstract) computers with potentially infinite memory, or equivalently, about algorithms. The first paragraph tries to explain that with the phrase "provided that sufficient time and storage space are available." The second paragraph emphasizes that [these considerations assume] unlimited time and memory.

An important point is that the storage space has to be only potentially infinite, because when we talk about computing power we talk about terminating algorithms.

Actual real-life computers with finite memory are not equivalent to each other in computing power. Computer A may be able to solve problem P, whereas any algorithm to solve problem P might need more space than computer B provides.

--Aleph4 14:10, 29 August 2007 (UTC)

Good point. It is not my contention that different computers have the same computational power; that statement is in the original article. My contention is that no real computer is equivalent to an unconstrained Turing Machine.

Perhaps you could recommend a change such that "Any computer is equivalent to a Turing Machine with a finite tape."

Softtest123 15:00, 29 August 2007 (UTC)

Am not convinced about "Any" in your recommendation. Even changing this to "Most" worries me: The machine must have the capability of "infinite indexing" along a tape, i.e. capability to "move tape left one square", "move tape right one square", "read square under tape head", "mark square under head", and "erase square under head", without any reference to any "register" (because any real register will be finite). The machine must have this built-in capability (i.e. not built as a random access machine with regards to locations on the tape, i.e. it had not be built with explicit (i.e. absolute) addressing: "Move to tape-location 1156893224987632153 and then do xyz". Or if it is built this way (as an indexed RAM) the index register must have infinite capacity.)

With regards to the "Most": Many years ago I fiddled with "Turtle Logo" I believe it was called. I could not do certain things with it, no matter how hard I tried (it's been a long time, so I can't remember exactly what, but I remember being very frustrated that there was no "unconditional jump" or any combination of instructions that would result in the same outcome). Even a "Turtle Logo" computer had been built with an infinite tape I swear it would not "compute everything that is computable".

I suggest: "When in doubt, cut it out." The statement is wrong as it stands. wvbaileyWvbailey 17:27, 29 August 2007 (UTC)

I've been doing some research on Church-Turing Thesis and the whole 2nd paragraph of this article seems to be wrong. The 1st paragraph seems to be okay, but the Church-Turing Thesis does not say that any computer can run any algorithm. Instead it addresses what computers do and states that an algorithm (i.e. a program that terminates) that runs on a computer can be expressed with an equivalent Turing Machine (or, per Church, a lamda-expression). But does not state the converse, that any algorithm can be run on a finite computer.

There are tons of citations on this and should be included in this article.

I guess I better get to work on that. <sigh>

Softtest123 21:45, 29 August 2007 (UTC)

Also see the "Skeptical Scientist edits" just above, on this talk page; I've been picking away slowly at this, accumulating "evidence" for a "history" section. There are indeed papers galore. I haven't put any of it into the article yet, am working on other stuff and letting this stew and ferment for a while. wvbaileyWvbailey 03:13, 30 August 2007 (UTC)

That is great stuff and a lot of work. It belongs somewhere in Wikipedia but I would not know where to start wedging it in. Do you think this article should contain some of that work? This article really needs fixing and you've done most of the work necessary. I'd like to see something put in place of what is here. Softtest123 07:21, 30 August 2007 (UTC)

Yes I think the article needs work. "Skeptical Scientist" also wanted more info, and that's what set me going. My "plan" is/was to assemble some of this stuff on the article page (a bit like the stuff at the beginning of the "Skeptical Scientist edits") and then put the rest in a new "expanded history" adjunct page. But I keep encountering new stuff along the way, in particular in context of the Entscheidungsproblem (I've got messy stuff all over that talk page too, it's really a mess). In the Entscheidungsproblem researh I ran across a precursor/mathematican to Godel named Finsler and all that has diverted me (right now I'm trying to really really understand Godel's proofs, it's a hard slog). But as it turns out some of this will have a bearing on this article. All this stuff seems very entwined: Godel's undedicability proof VI, the Church-Turing thesis, the Entscheidungsproblem ... I'll eventually get to this page if I don't chicken out along the way... I just want to see the whole picture better... plus a bit of "distance" between me and this topic helps me see it with fresh eyes. wvbaileyWvbailey 03:09, 31 August 2007 (UTC)

I'm going edit something in the offending paragraph but it will need references. I am away from my library for another month and you have done the research. When you get to it, I would appreciate fixing the stuff I am going to put in.

Sure, go for it. I'll do what I can do to help. wvbaileyWvbailey 14:04, 31 August 2007 (UTC)

Softtest123 13:22, 31 August 2007 (UTC)

Nice job Mr. Bailey.Softtest123 17:44, 31 August 2007 (UTC)

Archaic terminology

There's no reason this article should focus excessively on archaic terminology such as "general recursive. The Church/Turing thesis says simply that every effectively calculable function is a computable function. While it is certainly worthwhile to include a thorough account of the history, the article should use contemporary terminology except when actually discussing the history. — Carl (CBM · talk) 18:18, 6 September 2007 (UTC)

Without qualification/explanation I can't agree with your definition. I agree that the words "general recursion" is archaic (that's about the only one). That has been part of the problem with this page. So many interpretations/definitions, so little time. What to do: just state the facts as they are known.

Note I (temporarily) hid the "formal definition". I really don't like the "formal definition" as it stands. I'm not happy with the long lead-in, and agree that something more concise could be done. Maybe move down into the "formal definition" or into the history. However, whatever we do lets not cheat the reader with over-simplifications or vagueness.

Perhaps this can be cleared up. My problem is with your expression of "the Thesis" is the use of words such as "computable" and "calculable". They don't have a pinned-down meaning. They might to you, but they don't to me. Their meanings need to be precise. If you mean "computable" as in "calculated by Turing-machine or equivalent" and "calculable" as in "produced by any intuitively "effective means" whatever", then I don't object. In fact Turing's 1939 definition is exactly that:

"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." (cf the footnote † in Turing 1939 (his Ordinals paper) in Davis 1965:160).

Lemme know your thoughts here. I want to bring back "the formal definition", but I want it to be a good one. wvbaileyWvbailey 18:50, 6 September 2007 (UTC)

Yes, I mean exactly what you said by "computable" and "effectively calculable". — Carl (CBM · talk) 18:56, 6 September 2007 (UTC)

Busy Beaver Example - Assuming the Thesis is right

Since these functions cannot be computed by Turing machines, the Church-Turing thesis guarantees that these functions cannot be effectively computed at all, by any means.

Shouldn't this say, "Since these functions cannot be computed by Turing machines, if the Church-Turing thesis is right, then these functions cannot be effectively computed at all, by any means"? —Preceding unsigned comment added by 72.74.115.73 (talk) 06:10, 10 September 2007 (UTC)

There is no significant opposition to the Church-Turing thesis; it is a thesis because in some sense it cannot be proved, but the justifications for it are compelling enough that all but a tiny number of people in the field accept it. — Carl (CBM · talk) 11:40, 10 September 2007 (UTC)