Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

like image 254
Robben_Ford_Fan_boy Avatar asked Oct 12 '10 08:10

Robben_Ford_Fan_boy


Video Answer


1 Answers

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.

like image 116
shuhalo Avatar answered Oct 05 '22 01:10

shuhalo