如果我有一台机器，称之为机器 1，它能够解决一个问题：它只是一台机器，而不是图灵机。它可以解决一个特定的问题。如果这个完全相同的问题可以在通用图灵机上解决，那么我原来的机器 1 也是通用图灵机吗？
这并不适用于所有问题，这已经被解决了。是否有任何具有此描述属性的问题？如果这绝对不是真的，那为什么呢？
有人可以举一个要解决的问题的例子。如果我原来的机器解决了这个问题，1，确定这是一台万能车床吗？还是不存在这样的问题？如果不存在，为什么？
我很感兴趣，但无法弄清楚...谢谢。
编辑：使问题更清楚。
问问题
2239 次
7 回答
5
通用图灵机可以解决任何一大类问题。
如果您的机器（1）可以解决 1+1，这并不意味着它可以解决任何一个巨大的类。所以它可能不是通用图灵机。
于 2010-01-20T12:15:50.250 回答
2
逻辑学家区分“充分”和“必要”条件。以句子为例
天是蓝的。
（让我们假设这总是正确的）。你现在知道的是：
当你仰望天空时，你会看到蓝色。
你不知道的是：
当你看到蓝色时，你在看天空。
——你不妨看看你邻居的车。
从逻辑上讲，蓝色是天空所必需的，但这还不够。
你的情况也是如此：机器（1）确实解决了你的问题，所以它确实是一个可以解决的问题。因此，能够解决问题是UTM 的必要条件，但不是充分条件，因为 UTM 必须能够解决任何问题（完全可以解决），而不仅仅是单个问题。
于 2010-01-20T12:26:34.723 回答
1
通用图灵机可以解决任何特定图灵机可以解决的任何代码。
因此，您的通用图灵机 (2) 可以解决您原来的图灵机 (1) 旨在解决的问题。
但是，您原来的图灵机 (1) 只能解决那个确切的问题，而不能解决任何其他问题（包括作为通用图灵机的“问题”）。
所以不，根据您的描述，您原来的图灵机不是通用图灵机。（如果您将其定义为，可能是这样，但这是一种作弊）。
于 2010-01-20T12:14:05.390 回答
1
Imagine a UTM as if how would you proceed if you have to write a code(High level) for simulating the turing machine.You will require the following: 1.Array to hold the input symbols and the stuff that yiu would do on it. 2.An array(possible 2-d) to hold the transition function that you will prompt the user. 3.An algorithm that read user's inputs of transition functions and simulates it on array 1. 4.Few variables that your program will need to track its own state.
If you think in this way,if you end up getting a perfectly working code you end up with a perfect UTM. However the catch is no matter how efficiently you code you can't stop the user from entering transition functions that can cause your code to run forever.So there will be certain problems for which UTM will fail,and then we say that for those problems we can't develop a membership testing machine.(though notice a membership verification machine is always possible)
于 2011-12-06T02:46:24.787 回答
1
有人可以举一个要解决的问题的例子。
当然：给定编码的车床和数据，结果是什么:) 如果您的机器可以解决这个问题，那肯定是 UTM。
你知道为什么这些不同的问题出现在 NP 中的推理路线吗？就像“当我有一台可以解决哈密顿问题的机器时，我可以解决 3-sat 问题吗？” 你当然可以用它来回答你的问题。
于 2010-01-20T12:33:41.550 回答
1
通用车床 (UTM) 的重点在于，对于任何图灵机 (TM)，您都可以使用该 TM 并为其创建一个编码来描述 TM 的操作，并让该编码在另一个 TM 上运行。
UTM 是一种 TM，它的定义足够强大，以至于任何其他 TM 定义都可以在其中重写。
将 UTM 视为解释器。TM 是一项特定的任务。
除非 TM 也属于解释器类，否则它也不是 UTM。（因为 UTM 也是一个专门负责的 TM）。
所以回答你的第二个问题：如果你能证明 UTM 和 TM 是等价的，那么你已经证明 TM 也是一个 UTM。为此，您需要能够展示如何将 UTM 的编码程序更改为 TM 的等效程序。
于 2010-01-20T12:20:18.757 回答