Provable ==可判定？

Question

在计算理论中,可证明和可判断的术语是可互换的吗？他们的意思是一样的吗？

例如,您经常会看到一个问题是否可证明是一个决策问题(Das Entscheidungsproblem).

Answer 1

这些是不同的。事实上，它们指的是完全不同的领域。

可判定意味着图灵机可以针对所有可能的输入解决决策问题，并输出“接受”或“拒绝”。

可证明意味着数学陈述可以通过数学证明来证明。

事实上，你不能比较“可判定”和“可证明”，因为这些属性指的是完全不同的事物。