开发者

Does Provable == Decidable?

开发者 https://www.devze.com 2023-01-19 10:33 出处:网络
In computation theory are the terms Provable and Decidable interchangable?Do they mean the same thing?

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 Entscheidu开发者_开发技巧ngsproblem).


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.

0

精彩评论

暂无评论...
验证码 换一张
取 消