Talk:Computability theory

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)