我找到了一个图灵机等效列表的维基百科文章。但是，它没有说明如何确定给定机器是否与图灵机等效的方法。
需要用图灵机的定义来证明吗？你能举个例子吗？
谢谢。
问问题
1835 次
3 回答
4
证明图灵完备的标准方法是在您的机器中实现 TM 等效项之一。如果可以做到这一点，那么您的机器就是图灵完备的。如果不是，那就不是。因此，如果我试图证明一种新的编程语言正在完善，我会选择最容易实现的 TM 等效语言，然后证明我的编程语言可以模拟它。
于 2011-01-10T10:08:34.517 回答
1
事实上，它并不能真正得到证明。至少，将这些常见的等式证明完全形式化可能需要比理论计算机科学中预期的更多的形式逻辑。（如果您不同意，请告诉我！我很想讨论这个问题。）
但是，从上下文中可以很清楚地看到。您尝试在另一个此类计算模型 B 中构建计算方案 A 的“机器”的模拟。这意味着 B 可以模拟 A，因此具有 A 的全部功能。反之亦然，这两个模型称为相等的。
于 2011-06-04T22:37:43.493 回答
0
我的头脑：如果您的机器可以模拟已知的图灵机等效机器之一，那么您的机器也是图灵机等效机器。
可能是最简单的方法来做这样的事情。
编辑：我并不是说这要求一台机器与图灵机相当，尽管它可能是。也许在理论信息学方面更熟练的人可以让我明白这一点？
于 2011-01-10T09:29:27.167 回答