Talk:Computability theory (computer science)

I believe the Entscheidungsproblem was first proved unsolvable by Church, and months later by Turing. Goedel's theorems don't really talk about algorithms, so they don't directly apply. Of course, Goedel's trick of Goedel numbering and the Barber paradox is really the key to the Entscheidungsproblem and halting problem, everything else is details. --AxelBoldt

OK, I've added that. --LC

The context-free languages need a stack and a non-deterministic finite-state machine; deterministic won't do. --AxelBoldt

Yes, that's what it says. Perhaps you misread the 2nd sentence of the paragraph? --LC

Yup, you're right. --AxelBoldt

The languages that are accepted by a Turing machine are exactly those that are generated by formal grammars.

This is wrong. I doubt it is all formal grammars. I expect that it is context sensitive grammars the author was thinking of. Regular grammars are FSM equivalent, as I recall. -- BenBaker

No, the context sensitive grammars generate exactly the languages accepted by linear bounded nondeterministic Turing machines (Turing machines with only a linear amount of memory). The set of languages accepted by all possible Turing machines is exactly equal to the set of languages generated by all possible formal grammars. The sentence in the article is correct. See Chomsky hierarchy for more details. --LC

I moved the following question from the article. I don't know the answer. (¿Isn't it 3 parameters?)

Hi Cwitty, I'm not sure what form Turing's definition took. But your change seems unhelpful, because it puts too much weight on the word "arbitrarily".

Chaitin's constant, for example, can be approximated from below with unlimited accuracy, simply by simulating all machines and adding in a component for those which halt. It is not computable, because there is no way of telling how close the approximation is at any point.

I'm pretty sure the "incorrect" defition you changed is actually equivalent to the "correct" one. -- Pde 06:54, 8 Nov 2003 (UTC)

I can certainly change the definition to be precise; I didn't do so because I put a precise, correct definition in computable number a couple of months ago.

There is a link to Turing's original paper at the end of computable number. Note that the link includes both the original paper and a correction to it. Turing's original definition is indeed similar to the one I removed; but in the correction, he acknowledged that this definition was flawed, and provided an alternate definition (which I can't read, due to font problems).

Here's an example which shows the problem of relying on "digits" in a definition of this form. Start with 1/2. Add 2^-k for every k which is an odd perfect number. Subtract 2^-k for every k which is an even number >2 that is not the sum of two primes. This number is greater than 0.5 if the first odd perfect number is smaller than the first counterexample to Goldbach's conjecture; if Goldbach's conjecture is true, and there are no odd perfect numbers, then this number is exactly 1/2.

My definition (at computable number) says that this number is computable; another way to put it is that given an epsilon, we can give a number which is within epsilon of this number. However, we cannot give a single (binary or decimal) digit of this number; we do not know whether it begins 0.4 or 0.5. (I think you might be able to produce arbitrary ternary digits of this number, though.) -- Cwitty 23:45, 8 Nov 2003 (UTC)

Gotcha. One could argue (at least momentarily) that it is acceptable to consider your number to be incomputable unless the Goldbach conjecture is resolvable. The fact that the definition is not consistent across all bases makes such an argument a little untennable, though. -- Pde 01:52, 9 Nov 2003 (UTC)

I didn't edit the page, but I believe it should read "given ANY statement in [FOL]...", not "given A statement in [FOL]"...

also, it might be helpful to add that godel's general recursive functions are also equivalent to the notion of Turing-computable functions and lambda-definable functions.

Refocus article on Computable functions

I think the article should be rewritten to focus more on computable functions instead of Turing machines. This should be done in most articles in the computability category. Of course Turing machines are easier to grasp then the abstract concept of computable function, but by focussing on the abstract concept we can eliminate the redundant discussion of lamda calculus, recursive function and Church-Turing thesis in each computability article. I guess in many cases the proofs and theorems will get shorter too. We can always add a concrete example using Turing machines if the article gets to abstract MathMartin 23:59, 9 Nov 2004 (UTC)

I have the opposite opinion. TM gives very intuitive and simple representation for computability. See the proofs for uncomputability of Busy Beaver functions. More of the results may be demonstarted on TM (or other programming language) examples. If you get the Quine program, it is easy to expand it to self-explorer program, and then using self-opposite behavior to proof easy non-stoping problem, Godel incompleteness theorem and other results. Such proofs are simple and don't use complex and hard for understanding mathematical notation. Skelet 19:16, 7 Dec 2004 (UTC)

I do not object to using Turing machines as examples, but as with any model, Turing machines only serve to illustrate certain points. Other points can be illustrated better using other models. My point is the main (technical) definition should be based on computable functions. But at the moment I am not able to devote any amount of time on this topic. So I guess for now things will stay as they are. MathMartin 19:30, 9 Dec 2004 (UTC)

What happened to this article?!

As far as I remember (and correct me if I am wrong), this article used to have a lot of content. Now it is just 8 lines. Computability theory deserves more than just a short definition and two links. This is an ENCYCLOPEDIA, not a DICTIONARY. Who destroyed the old content?! ---- David November 13, 2005

Yes, this is indeed very strange! I do not know the previous article, but this topic cannot possibly be that short after 4 years of Wikipedia! Hints on what might have happened here are found at the deleted changes page. There it says that "00:11, 26 October 2005 Timwi deleted "Computability theory" (Deleted to make way for move)" Yet, I do not understand it. What moved? Where did it move to? I will go and ask Timwi. --Markus Krötzsch 21:05, 15 November 2005 (UTC)[reply]

Problematic name

It's become trendy in recent years, due to the influence of Soare, to use the term "computability theory" to refer to what's traditionally called "recursion theory", and in fact recursion theory is a redirect here. However this article is not much about recursion theory (Turing degrees, effective descriptive set theory, that sort of thing), but more about models of in-principle-physically-realizable computation. Recursion theory is a branch of math logic, not of theory of computation.

So what do we do about this? I see there's a merge template to merge to computation. For most of the content in the current article that's probably fine. But there should also be an article about what math-logicians call computability theory or recursion theory. Perhaps we need a dab page under the name computability theory. --Trovatore 04:26, 26 November 2005 (UTC)[reply]

This article should be moved to theory of computation (which I can't do because I'm not an admin). This should be made in to a disambig to theory of computation and a to be written recursion theory. —R. Koot 04:40, 26 November 2005 (UTC)[reply]

So I've taken an awkward first step, moving the article to Computability theory (computation), which I don't propose as the permanent name, but just a good place to put this content while we sort things out. Some of the content does need to be reproduced in the (new stub) recursion theory article. Roughly speaking, recursion theory starts with what is here called "Unreasonable models of computation". Definitely the halting problem needs to be mentioned in the "recursion theory" article. --Trovatore 05:22, 26 November 2005 (UTC)[reply]

To tell the truth I'm not sure the articles should be split at all. What's clear is that, whatever article is called recursion theory (or where recursion theory redirects) has to have a very different focus from the current article here; this current article seems to be mainly about things of Turing degree 0. In the end perhaps we should have just one article, but it shouldn't spend so much time talking about Turing degree 0 in fifteen different ways, but should move quickly into the real meat of the topic, which starts with oracles. --Trovatore 06:05, 26 November 2005 (UTC)[reply]

Theory of Computation

The current article isn't really suited as the main article for all of Theory of Computation, as when I wrote it I was considered only computability theory and not the other major branch, complexity theory. So do we want separate articles on computability and complexity, or do we want to expand this article greatly to include some discussion of complexity theory as well? Clearly any article called "Theory of Computation" should at least mention P =? NP. — Preceding unsigned comment added by Readams (talk • contribs) 17:34, 26 November 2005 (UTC)[reply]

That's another aspect, alright. It seems we have a multidimensional mess on our hands. Interested parties should also look at the categorization question. Yesterday I created Category:Recursion theory and have been going through the articles in Category:Theory of computation to try to figure out what belongs where. Roughly speaking, the test I used was this: Would this question be considered in a math department by people who call themselves mathematical logicians, or would it be considered in a computer science department? Of course there was a very considerable overlap. Also people may disagree with my judgment as to which articles are categorized which way by this test, and may disagree with the test itself. I'd like to see some more thoughts on this. --Trovatore 18:35, 26 November 2005 (UTC)[reply]

There is indeed a much larger overlap than you suggested at first (I suspected this, but I know nearly nothing about recusion theory, so didn't mention it). Maybe some other people want to say something aboiut this? — Preceding unsigned comment added by R.Koot (talk • contribs)

Well, I was conservative about removing the "Theory of computation" category from articles, so there may be more overlap in the current categorization than there really should be. --Trovatore 19:03, 26 November 2005 (UTC)[reply]

I think keeping it would be best if the article would be kept seperate. Maybe we should move this page to Computability theory (computer science)? The Theory of computation could be an introductory article wich refers to automata theory, formal language theory, computability theory (computer science) and computational complexity theory. —R. Koot 18:53, 26 November 2005 (UTC)[reply]

Chaitin

For the moment, I've removed the following:

(the fact that one can follow from the other was first shown by Gregory Chaitin in his development of Chaitin's Constant, a number which can be defined but not computed)

First, it's not clear just what connection between the incompleteness theorems and the halting problem is being claimed, but whatever it is, I'd want to see a ref that Chaitin was the first one to find it. Chaitin, like Wolfram, is a bit of a self-promoter, and is good enough at self-promotion that a lot of people give him credit for things that might not have been quite as original as they think. In particular Chaitin's Omega was by no means the first non-computable number to be defined. --Trovatore 04:06, 2 December 2005 (UTC)[reply]

It's not clear to you, because you might not know the subject. Chaitin proved the connection to the halting problem, and anybody who knew something about Kolmogorov complexity would acknowledge that. Fact: Chaitin was one of the co-inventors of Kolmogorov complexity. The halting probability Omega contains all information required to solve the halting problem. So it acts as an oracle for the halting problem. How is that for a connection? --Exa 15:26, 22 January 2006 (UTC)[reply]

Omega was of course not the first oracle for the halting problem to be defined, though. The first one was, presumably, simply the set of all Gödel numbers of Turing machines that halt. You still haven't explained (or indeed even mentioned) the connection to Gödel's incompleteness theorem (which is quite distinct from the halting problem), or given a ref that Chaitin was the first one to find said connection. --Trovatore 17:13, 22 January 2006 (UTC)[reply]

On reflection I probably should have removed entirely the following two sentences from the version way back then:

Computability theory has its roots in First-order logic, and the halting problem and other non-recursive problems are closely related to Gödel's incompleteness theorem (the fact that one can follow from the other was first shown by Gregory Chaitin in his development of Chaitin's Constant, a number which can be defined but not computed). David Hilbert and Kurt Gödel laid many of the foundations for first-order logic.

It was a red flag to me that someone was dragging Chaitin in to a discussion of the incompleteness theorems, but really the entire first sentence is unsupported–what roots in first-order logic are being claimed, exactly? And if the first sentence goes, then the second, while certainly true, is out of context.

Unless someone can explain and support this passage, I'll be snipping these two sentences. --Trovatore 17:32, 22 January 2006 (UTC)[reply]

Desktop PCs are not considered to be FSMs

The author probably didn't read the enlightening discussion in the new edition of the Cinderella book.

It would take too much effort from me to explain it completely, but I am going to remove those uninformed assumptions that the tape of a turing machine is an infinitely long resource. In fact, at any moment, the turing machine has a finite ID, and thus the infinity talked of is potential infinity (much like the infinity of Z) Furthermore, the TM is a mathematical model. Every TM denotes a particular computation. The author probably doesn't recognize that. The potential infinity there is an idealization. It does not mean that physical machines cannot be TMs!

If you followed that naive logic, just because you can define finite state machines that would not fit into this universe, desktop pcs would not even be finite state machines.

Think about that for a while. What do I mean by "Every TM denotes a particular computation"?

I am hoping it is clear now, and now this bit about desktop pcs not being TMs is goodbye kansas. Why on earth do you think we are studying turing machines then?

The standard reason for the potentially infinite tape of the TM is to model the fact that an ongoing computation may extend the tape (allocate more memory). This is usually thought to be a property of desktop PCs as well. With some effort, it is possible to extend the PC with as much memory as you want. There are no hard limits (except physical limits which apply to EVERYTHING including FSMs). Did you ever connect two PCs with a network? Fine. Then you know what this means.

For the record, all of this can be shown rigorously.

--Exa 15:41, 22 January 2006 (UTC)[reply]

Except inasmuch as they behave nondeterministically, desktop machines are finite state machines. You might argue that it's more useful to treat them using the theory of Turing machines, and I'd tend to agree, but in the strictest mathematical sense they aren't Turing machines.

What you call "potential infinity" is what mathematicians call "countable infinity". Every particular integer is finite, but the set of integers is infinite. Each particular state of a Turing machine is finitely describable, but there are infinitely many such states. A finite state machine can only be in finitely many different states (each of which is, again, finitely describable). As the article (currently) says, a desktop computer cannot recognize the language S ::= e | a S b, because it is a finite state machine, while a Turing machine can recognize this language. You can extend a desktop computer with more memory, but the amount of memory, hence the count of states, is always finite.

Please don't edit the article, at least not without more discussion.

-- BenRG 22:05, 22 January 2006 (UTC)[reply]

BenRG is correct. —Ruud 22:32, 22 January 2006 (UTC)[reply]

Yes, I'm a computer scientist I know what countable infinity is but the discussion is philosophical. Please read what I say carefully, the potentially infinite tape in the TM models the fact that storage is extensible. This

is true also for ordinary desktop PCs not only in the sense that it is "useful to treat them as such", but it can be rigorously proven that you can extend a PCs memory indefinitely. Only the very physical limits apply but that applies to everything, and no, I don't think you have really read my argument. I don't know if I can make it clearer. Let's try. You need to contend first that a desktop computer is physically extensible, it is not a static device with a hard-limit on the number of its states. It has no difference from a TM. The view in the article seems to me a Platonist, inadequate and unwarranted reading into Turing's original paper in which his genius makes it clear that he is modelling human computers. This article comes around and says that he failed to do what he tried to do. I don't think so. In my opinion, it is necessary to read Turing's paper in a philosophically consistent and fully scientific way and everything will be resolved. I am perhaps guilty for trying to make a non-trivial philosophical analysis here but it was just bad philosophy and bad science in this page that has no place. The argument I am giving is a stronger version of the argument in the Cinderella book. It is not simply "useful" to treat the PC as the realization of an r.e. function, it is essential. This is because, I am saying this very carefully, each TM represents a particular computation, and NOT a class of computations. Since you are a mathematician, I believe you will appreciate the difference between a function, and a set of functions. So, each ongoing physical computation in a desktop PC corresponds to a particular TM. That a desktop PC can not "instantiate" every possible TM is a no-brainer. It is due to physical limits. But the same physical limits also apply to FSMs. There are also infinitely many particular FSMs that a given desktop PC cannot "instantiate". We do not say that a desktop PC is not a particular FSM because it cannot "instantiate" all possible FSMs! Likewise, we cannot say that a desktop PC is not a particular TM because it cannot "instantiate" all possible TMs. That is to say, you might want to revise the claim here to be precise. In the simplest language, it would read "A desktop PC that is not extensible can be seen as either a FSM or a TM. It is interesting to note that such a machine cannot implement a universal Turing machine which could simulate any possible Turing Machine". etc. But note, such statements would really make the article descend a slippery slope, that is why I suggest to remove all references to this, in my humble opinion redundant, "PCs are finite state machines, TMs don't physically exist" argument that is best kept for redundant discussions on comp.theory . As far as authority goes, I would like to refer to the Cinderella book. However, my refutation is self-contained. I am hoping this somewhat complicated but correct argument is appreciated. It usually isn't understood how much thought has gone into my analysis. I would be glad if you could spend the effort to read it. Best. --Exa 23:06, 22 January 2006 (UTC)[reply]

Could you clarify on the following points in your first post, I might be misunderstanding you.

Every TM denotes a particular computation. What about universal Turing machines?
... can define finite state machines that would not fit into this universe, desktop pcs would not even be finite state machines. Not every finite automaton would be a desktop pc, but every desktop pc is a finite automaton?

Desktop PC's are not TMs in the sense that they cannot recognize any turing recognizable language, because as the input string becomes large, the amount of memory needed to reconize becomes larger as well. Every language which has a finite length wouls be regular. —Ruud 23:48, 22 January 2006 (UTC)[reply]

Ok, I had better read you second, and much clearer, second reply before making the comments above. I essence I do indeed agree with you, although there remains the point that physics will limit you to a "finite tape". This should be much more carefully explained in the article. —Ruud 23:58, 22 January 2006 (UTC)[reply]

You may wish to read the stuff (about half of which I wrote) at Turing_machine#Comparison_with_real_machines. Deco 01:46, 23 January 2006 (UTC)[reply]