Search code examples
computation-theorydecidable

Does Provable == Decidable?

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).

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.