Question

In computation theory are the terms Provable and Decidable interchangable? Do they mean the same thing?

For example you often see the question whether something is provable referred to as a decision problem (Das Entscheidungsproblem).

Was it helpful?

Solution

These are different. In fact, they refer to completely different areas.

Decidable means, that a decision problem can be solved for all possible inputs by a Turing machine, which puts out 'accept' or 'reject'.

Provable means, that a mathematical statement can be proven by, well, a mathematical proof.

In fact, you cannot compare 'decidable' and 'provable', as these attributes refer to completely different things.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top