可证明==可判定吗？
在计算理论中，术语“可证明”和“可判定”可以互换吗？它们的意思是一样的吗？
例如，您经常会看到某件事是否可证明的问题被称为决策问题（Das Entscheidungsproblem）。
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).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这些是不同的。事实上，它们指的是完全不同的领域。
可判定意味着图灵机可以针对所有可能的输入解决决策问题，并输出“接受”或“拒绝”。
可证明意味着数学陈述可以通过数学证明来证明。
事实上，你不能比较“可判定”和“可证明”，因为这些属性指的是完全不同的事物。
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.