3
$\begingroup$

In the https://en.wikipedia.org/wiki/Computational_problem, the first line states: "A computational problem is a problem that may be solved by an algorithm." However, I have doubts about the accuracy of this definition.

As I understand it, there are computational problems that cannot be solved by algorithms, such as undecidable problems (e.g., the Halting Problem). These problems cannot be solved by any algorithm, so what happens with all the problems that are undecidable? Are they not considered computational problems, or are they just problems? If they are just problems, what kind of problems would they be classified as? Would they be any kind of problem?

My questions are:

  1. Is the Wikipedia definition correct?
  2. If not, what is the most widely accepted definition of a "computational problem" that includes both problems that can be solved by algorithms and those that cannot be solved?

I appreciate any clarification or references to more precise sources on this topic.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ You are correct that there is a problem, thank you for pointing to it. I fixed Wikipedia, so this question is not needed anymore. Let me also point out that it might be more helpful to complain about Wikipedia on Wikipedia (each page has a "Talk" sub-page), rather than ask here what's wrong over there. And keep in mind that Wkipedia is full of errors when it comes to science, at least in my corner of science. $\endgroup$
    – Andrej Bauer
    Commented Jul 14 at 7:43
  • 1
    $\begingroup$ Wikipedia still has some way to go for Computer Science. I actually tend to appreciate the "simplified" wikipedia pages more than the actual "main" wikipedia articles for particular Computer Science topics. $\endgroup$
    – Minko_Minkov
    Commented Jul 16 at 4:49
  • $\begingroup$ And even then, ocassionally a page can just get obliterated for a not-so logical reason at all. simple.wikipedia.org/wiki/RSA_algorithm The RSA page for example, had a very nice straightforward implementation of RSA which was so easy, you could code it yourself. Then they went ahead and deleted it (Check history on the page). Meanwhile the implementation on the real page is not so good, and includes a lot of details which are not very relevant for the aspiring programmer. en.wikipedia.org/wiki/RSA_(cryptosystem) They could've at least moved it to the main page... $\endgroup$
    – Minko_Minkov
    Commented Jul 16 at 4:57

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.