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).
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With