•  21-09-2019
  •  | 
  •  

题

如果我有一台机器，称之为机1台，即能解决一个问题：它只是一个机器，而不是本身图灵机。它可以解决一个具体的问题。 如果此相同的问题可以在通用图灵机来解决，然后是我的原机，1，通用图灵机吗？

这并不适用于所有的问题，这已经是ansered。是否有已在此描述的所有财产的任何问题？如果它是绝对不正确的，那么，为什么？

有人可以给一个需要解决的问题的一个例子。如果这个问题由我的原装机，1解决，肯定使这是一个万能车床？抑或这样的问题不存在？如果它不存在，为什么？

我很感兴趣，但不能看着办吧......谢谢你。

编辑：提出的问题更加清晰

有帮助吗？

解决方案

通用的车床（UTM）的一点是，对于任何图灵机（TM）你可以采取TM并为它创建的编码描述TM的操作，并具有另一个TM编码运行。

在UTM是它有一个定义足够强大，使得任何其它TM定义可以在它被重写的TM。

思UTM作为解释的。的TM是一个特定的任务。

除非TM也是在类口译然后它不是一个UTM为好。 （由于UTM也是一个专门负责TM）。

因此，要回答你的第二个问题：如果你能证明的是，UTM和TM是等价的，那么你已经表明，TM也是UTM。要做到这一点，你需要能够以示对UTM的编码的节目怎么可以变成为TM等效的程序。

其他提示

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

如果您的机器（1）能够解决1 + 1，这并不意味着它可以解决任何巨大的类。因此，它可能不是一个的通用的图灵机。

在逻辑学家“足够的”和“neccessary”的条件之间进行区分。举个例子来说，句子

  

天空是蓝色的。

（让我们姑且认为是总是如此）。现在你知道这是什么：

  

当你仰望天空，你看见蓝色的。

您的不的知道的是什么：

  

当你看见蓝色的，你看着天空。

- 你不如在看你的邻居的车

在逻辑术语中，蓝色是 neccessary 用于天空，但它是不充分的。

这同样适用于你的情况也是一样的：机（1）不解决您的问题，所以它确实是一个可以解决的问题。因此，能够解决的问题是一个 neccessary 条件为UTM，但不是充分之一，因为一个UTM必须能够解决的任何问题（即在是可解全部），而不仅仅是这一个。

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

所以你的通用图灵机（2），可以解决原来的图灵机（1）的目的是要解决这个问题。

您原始图灵机（1），然而可以解决仅确切的问题和解决不了任何其他问题（包括的是一个通用图灵机“问题”）。

所以，不，原来的图灵机是不能根据描述的通用图灵机。 （如果你定义它，但是这是一种欺骗它可能是）。

  

有人可以得到一个问题的一个例子来加以解决。

肯定的是：鉴于编码车床和数据，结果是什么:)如果你的机器就可以解决这个问题，那肯定是UTM

你知道的推理路线，为什么这些不同的问题是NP？像“我可以解决3-SAT问题时，我有一台机器解决问题哈密尔顿？”你肯定可以使用相同的回答你的问题。

证明特定系统的图灵完全是不平凡的，除非你可以很容易地表明，它的当量/同构到另一个系统是知道是图灵完成。所以，答案很简单：有没有简单的测试，你可以把你的机器通过检查它是否是图灵完整。你要分析和显示系统的性能作为一个整体。

如果您想了解更多关于这个话题，阅读这些文章图灵完全和可计算性理论。

想象一下，一个UTM，如果你将如何继续，如果你有写模拟图灵machine.You将需要以下代码（高级别）： 1.Array容纳输入符号和东西，耀会做就可以了。 2.An阵列（可能2-d）以保持过渡函数，你会提示用户。 3.An算法读取的转移函数的用户的输入，并模拟它阵列1。 4.Few变量，你的程序将需要跟踪自己的状态。

如果你这样想，如果你最终得到一个的完美的工作代码的你结束了一个完美的UTM。 然而，美中不足的是无论多么有效，你的代码，你不能进入过渡功能停止用户，可能会导致你的代码运行forever.So会有一定的问题，在UTM会失败，那么我们说，对于这些问题我们不能制定一个成员试验机（虽然通知一个成员资格验证机始终是可能的）

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top