Jump to content

Talk:Computation problem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Nortexoid (talk | contribs) at 00:15, 29 November 2004 (→Notes). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Notes

  1. Provide various equivalent notions of computability ranging from Turing computability to Abacus computability to general recursive computability.
  1. Outline computability of total, partial, and uncomputable functions, giving examples for each.
  1. 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.
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)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Computation_problem&oldid=7955545"