I'm reading Sipser's "introduction to the theory of computation" book. Even though in many places the phrase "computational problem" appears there is no definition of it. How is it defined?

Some other questions I thought about when trying the understand the nature of a "computational problem":

Are there mathematical problems which are not computational problems? (I do not mean undecidable problems since undecidable problems are still computational problems that cannot be solved by computers). Or every mathematical problem is also a computational problem? In general, is there a difference between a mathematical problem and a computational problem.

  • 2
    $\begingroup$ Not every concept has a formal definition. Sipser's textbook is not a philosophical tract, and I suggest not reading too much into these terms. $\endgroup$ Mar 8, 2022 at 21:47
  • $\begingroup$ A computational problem is a problem in which we want to compute something. $\endgroup$ Mar 9, 2022 at 8:33
  • $\begingroup$ In a way you are right, every mathematical statement should be provable by formal computation from axioms (but for Gödel's limitations). When they say computational, they mean that you want an explicit algorithm. $\endgroup$
    – user16034
    Mar 9, 2022 at 10:43


Your Answer

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

Browse other questions tagged or ask your own question.