通用图灵机问题

通用转向机(UTM)的要点是,对于任何图灵机(TM),您可以使用该TM并为其创建一个描述TM操作的编码,并使该编码在另一个TM上运行。

UTM是一个具有足够强大的定义的TM,任何其他TM定义都可以在其中重写。

把UTM想象成一个翻译。TM是一项特定的任务。

除非TM也属于口译员类别,否则它也不是UTM。(因为UTM也是一种特殊任务的TM)。

所以要回答你的第二个问题:如果你能证明utm和tm是等效的,那么你已经证明tm也是一个utm。要做到这一点,您需要能够展示一个为UTM编码的程序是如何被改变为一个为TM等价的程序的。

通用图灵机可以解决任何一类大问题。

如果你的机器(1)能解1+1,这并不意味着它能解任何一个大类。所以它可能不是 通用 图灵机。

逻辑学家区分“充分”和“必要”条件。例如,以句子为例

天空是蓝色的。

(假设总是这样)。你现在知道的是:

当你看到天空时,你会看到蓝色。

你什么 不要 知道这一点:

当你看到蓝色时,你看到的是天空。

--你不妨看看邻居的车。

从逻辑上讲,蓝色是 必需的 对于天空来说,这是不够的。

对于您的情况也是如此:机器(1)确实解决了您的问题,因此它确实是一个可解决的问题。因此,能够解决问题是 必需的 一个utm的条件,但不是充分的条件,因为utm必须能够解决 任何 问题(完全可以解决),而不仅仅是这个问题。

通用图灵机可以解决任何特定图灵机可以解决的任何代码。

因此,通用图灵机(2)可以解决原始图灵机(1)设计要解决的问题。

但是,您的原始图灵机(1)只能解决这个精确的问题,不能解决任何其他问题(包括作为通用图灵机的“问题”)。

所以不,根据你的描述,你原来的图灵机不是一个通用图灵机。(可能是你定义的,但那是一种欺骗)。

有人能举出一个要解决的问题的例子吗?

当然:如果你的机器能解决这个问题,那么它肯定是UTM。

你知道为什么这些不同的问题是NP的推理路线吗?比如“当我有一台机器可以解决哈密顿问题时,我能解决3-SAT问题吗?”你当然可以用同样的方法来回答你的问题。

证明一个特定系统的图灵完备性并不容易,除非您可以很容易地证明它与另一个已知为图灵完备性的系统是等价的/同构的。所以简短的回答是:没有简单的测试可以让您的机器通过来检查它是否是图灵完成的。您必须分析并显示整个系统的属性。

如果您想了解更多有关此主题的信息,请阅读以下文章 Turing completeness 和 computability theory .

想象一个UTM,如果你必须写一个代码(高级)来模拟图灵机器,你会怎么做。你需要如下: 1.数组,用于保存输入符号和Yiu将对其执行的操作。 2.一个数组(可能是二维的),用于保存您将提示用户的转换函数。 3.读取用户输入的转换函数并在数组1上进行模拟的算法。 4.程序跟踪自身状态所需的变量很少。

如果你这样想,如果你最终得到 完美工作的代码 你最终会得到一个完美的UTM。 然而,关键是无论你编码的效率如何,你都不能阻止用户输入转换函数,这会导致你的代码永久运行。因此,对于某些问题,UTM将失败,然后我们说,对于这些问题,我们不能开发一个成员身份测试机。(尽管注意到一个成员身份验证机总是可能的)