如何判断机器是否与图灵机等效

Question

我找到了维基百科的图灵机等效列表文章.但是,它没有说明如何确定给定机器是否与图灵机等效的方法.

我是否需要使用图灵机的定义来证明它？你举个例子吗？

谢谢.

Answer 1

证明某个事物完整的标准方法是在您的机器中实现 TM 等效项之一。如果这是可能的，那么你的机器就是图灵完备的。如果不是，那就不是。因此，如果我试图证明一种新的编程语言是图灵完备的，我会选择最容易实现的 TM 等效语言，然后证明我的编程语言可以模拟它。