可证明==可决定吗？

Question

在计算理论中，术语是否可以证明且可决定性互换？他们的意思是同一件事吗？

例如，您经常看到一个问题是否可以证明是决策问题（das ientscheidungsproblem）。

Answer 1

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

可确定的意味着，可以通过图灵计算机为所有可能的输入来解决决策问题，从而将“接受”或“拒绝”解决。

可证明的是，可以通过数学证明来证明数学陈述。

实际上，您无法比较“可决定”和“可证明”，因为这些属性是指完全不同的事物。