Computable problem

Question

A mathematical problem is computable if there is an algorithm that decides/solves this problem, right?

Can you give an example of such a problem?

Answer 1

These are all computable problems:

• Computing the greatest common divisor of a pair of integers.
• Computing the least common multiple of a pair of integers.
• Finding the shortest path between a pair of nodes in a finite graph.
• Determining whether a propositional formula is a tautology.
• Determining whether a propositional formula is satisfiable.

An example of an uncomputable problem is: determining whether a computer program loops forever on some input. You can replace "computer program" by "Turing machine" and the statement is equivalent.

Answer 2

A problem is computable if there is a decision procedure. This means that given any statement allowed in the system, you can decide it's true or false in finite time. (For a more formal definition see https://en.wikipedia.org/wiki/Formal_system)

Examples would be, deciding if a number is prime, or if a propositional statement is true or false.

A problem is undecidable if no such decision procedure can exist. Examples would be deciding if a first order logic statement is true or false, or as mentioned by BrianO, deciding if a computer program would terminate (Turing's stopping problem). Note that this does not mean that we can't decide the truth hood or falsehood of certain problem instances, it just means that no general strategy can exist to make decisions for arbitrary problem instances. For both of the above mentioned problems, if a statement is true, we can find out it's true in finite time. However, for any decision algorithm there are false statements that can make it run forever.