Notes

Provide various equivalent notions of computability ranging from Turing computability to Abacus computability to general recursive computability.
Outline computability of total, partial, and uncomputable functions, giving examples for each.
Parse and conjoin function problem with and revert to, what I take to be the more correct, computation problem - viz., this article (unless someone objects?). Nortexoid 04:58, 23 Nov 2004 (UTC)

I think (1) should be discussed on computability theory. (2) is already partially discussed on computable function. Regarding (3), I do not know if computation problem is widely used in this sense. I have only heard and read the terms decision problem and function problem. The complexity classes for function problems are also prefixed with an F (like FP) so I think it makes more sense to stick with this term. MathMartin 18:51, 28 Nov 2004 (UTC)

In mathematical logic, 'computation problem' is more often used than 'function problem'. See G. Boolos' widely used "Computability and Logic" and Kleene's "Mathematical logic" and "Introduction to Metamathematics" for starters. It might be used more often in mathematics (non-logic), but I haven't a clue.

I cannot quote any books on this topic and google did not provide an answer, so perhaps we should use your term. In any case I do not really care, but perhaps other people have a stronger opinion.MathMartin 13:28, 29 Nov 2004 (UTC)

As for (1) - ok; and the overlap for (2) is still necessary, if you ask me. It makes the article more informative and self-contained without linking/referrign all over the place. Nortexoid 00:15, 29 Nov 2004 (UTC)

I think it is ok to duplicate some material in order to provide context for an article. But in the long run we want to have a set of core definition (articles) which are referenced from other articles. And in my opinion the computability and computational complexity articles lack those core articles and duplicate a lot of material, which makes it hard to keep the articles consistent. But anyway if you are interested in writing the computation problem article give it a try. MathMartin 13:28, 29 Nov 2004 (UTC)