开发者

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

上一篇:

下一篇:

精彩评论

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

最新问答

问答排行榜