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).
Asked
Active
Viewed 567 times
8
-
1Maybe a suitable question for mathoverflow.net? – Prof. Falken Oct 12 '10 at 08:45
-
2I thought about that but as Comp. Theory (and complexity) course can be found on almost all CS\SE courses I thought here would be more suitable. – Robben_Ford_Fan_boy Oct 12 '10 at 08:47
1 Answers
1
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.
shuhalo
- 5,732
- 12
- 43
- 60
-
-
The answer seems to be yes: https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence – polcott May 24 '21 at 19:52