也就是说，图灵机能否将形式系统 S 作为其输入并确定 S 是否是图灵完备的？
我认为这是一个无法确定的问题，对吗？
如果它是不可判定的，为什么我们（作为人类）可以决定图灵完备性？
问问题
194 次
1 回答
0
嗯 :-) 决定图灵完整性并不是确定人脑是否是 TM 完整的核心；可以通过机械步骤来确定图灵完整性；这不是问题。
关键问题是，人脑是超计算[1]还是超图灵。
一项测试是对以下问题之一回答“是”：人类能否预测图灵机何时停止？（即解决停机问题）或者是人脑不受赖斯定理的约束。
在一般情况下，这两个问题的答案似乎都是“否”，因为人们可以想象一个带有无限长磁带的 TM 并且只是四处跳动，我们永远无法判断它何时会碰到一个告诉它停止的单元格。
表面上的超计算能力来自于我们将普通计算机/软件/机械过程等误认为 TM 的事实。
赖斯定理可以在具有马尔可夫性质并且具有有限数量的位置转移网络表示的系统的“特殊情况”中被回避。我们的一般环境有大量的这些“特殊情况”，所以看起来人脑似乎能够进行超计算，因为它倾向于从特殊情况下得出一般结论，但可能不是，因为我们人类还没有体验与图灵机的交互。
于 2013-05-15T10:01:00.860 回答