通用图灵机问题
如果我有一台机器，称之为机器1，它能够解决一个问题：它只是一台机器，本身并不是图灵机。它可以解决一个特定问题。 如果这个完全相同的问题可以在通用图灵机上解决，那么我原来的机器 1 也是通用图灵机吗？
这并不适用于所有问题，这已经被回答了。是否有任何问题具有所描述的属性？如果这绝对不是真的，那为什么呢？
有人可以举一个要解决的问题的例子吗？如果我原来的机器解决了这个问题，1，这肯定是万能车床吗？或者说不存在这样的问题？如果它不存在，为什么？
我很感兴趣，但不明白...谢谢。
编辑：使问题更清楚。
If I have a machine, call it machine 1, that is able to solve a problem: it's just a machine, not per se a Turing machine. It can solve one specific problem.
If this exact same problem can be solved on a Universal Turing Machine, then is my original machine, 1, a Universal Turing Machine too?
This does not hold for all problems, which is already ansered. Are there any problems which have this described property at all? If it is absolutely not true, then why?
Can someone give an example of a problem to be solved. If this problem is solved by my original machine, 1, definately makes this a Universal Turning Machine? Or does such a problem not exists? If it doesn't exists, why?
I'm very interested, but can't figure it out... Thanks.
Edit: made the question more clear.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
通用图灵机可以解决任何一大类问题。
如果你的机器（1）可以解决 1+1，这并不意味着它可以解决任何大类问题。所以它可能不是通用图灵机。
A Universal Turing Machine can solve any of a huge class of problems.
If your machine(1) can solve 1+1, that doesn't mean it can solve any of the huge class. So it may not be a Universal Turing Machine.
逻辑学家区分“充分”条件和“必要”条件。举个例子，这个句子
（我们假设这总是正确的）。你现在知道的是：
你不知道的是：
——你不妨看看你邻居的车。
从逻辑上讲，蓝色对于天空来说是必要，但还不够。
对于您的情况也是如此：机器（1）确实解决了您的问题，因此这确实是一个可解决的问题。因此，能够解决问题是 UTM 的一个必要条件，但不是充分条件，因为 UTM 必须能够解决任何问题（可以在所有），而不仅仅是这一个。
The logicians differentiate between "sufficient" and "neccessary" conditions. Take, for example, the sentence
(let's just assume that's always true). What you know now is this:
What you don't know is this:
-- you might as well be looking at your neighbour's car.
In logical terms, the color blue is neccessary for the sky, but it's not sufficient.
The same is true for your case: Machine (1) does solve your problem, so it's indeed a solvable problem. Hence, being able to solve the problem is a neccessary condition for a UTM, but not a sufficient one, because a UTM must be able to solve any problem (that's solvable at all), not just this single one.
通用车床 (UTM) 的要点在于，对于任何图灵机 (TM)，您都可以使用该 TM 并为其创建一个编码来描述 TM 的操作，并让该编码在另一个 TM 上运行。
UTM 是一种具有足够强大定义的 TM，任何其他 TM 定义都可以在其中重写。
将 UTM 视为口译员。 TM 是一项特定任务。
除非 TM 也属于口译员类别，否则它也不是 UTM。 （因为 UTM 也是一个专门负责任务的 TM）。
因此，回答你的第二个问题：如果你能证明 UTM 和 TM 是等价的，那么你就证明了 TM 也是一个 UTM。为此，您需要能够展示如何将 UTM 的编码程序更改为 TM 的等效程序。
The point of the Universal Turning Machine (UTM) is that for any Turing Machine (TM) you could take that TM and create an encoding for it that describes the operation of the TM and have that encoding run on another TM.
The UTM is a TM which has an definition sufficiently powerful such that any other TM definition could be rewritten in it.
Think of the UTM as an interpreter. The TM is a specific task.
Unless the TM is also in the class of interpreters then it is not a UTM as well. (Because a UTM is also a specifically tasked TM).
So to answer your second question: if you can show that the UTM and TM are equivalent then you have shown that TM is also a UTM. To do this you need to be able to show how an encoded program for the UTM can be changed into an equivalent program for the TM.
通用图灵机可以解决任何特定图灵机可以解决的任何代码。
因此，您的通用图灵机 (2) 可以解决您的原始图灵机 (1) 旨在解决的问题。
然而，您原来的图灵机 (1) 只能解决该问题，而无法解决任何其他问题（包括作为通用图灵机的“问题”）。
所以不，根据你的描述，你原来的图灵机不是通用图灵机。 （如果您将其定义为，则可能是这样，但这是一种作弊）。
A universal turing machine can solve any code that any specific turing machine can solve.
So your universal turing machine (2) can solve the problem that your original turing machine (1) was designed to solve.
Your original turing machine (1) however can solve only that exact problem and can't solve any other problem (including the "problem" of being a universal turing machine).
So no, your original turing machine is not a universal turing machine according to your description. (It might be if the you define it to, but that's kind of cheating).
当然：给定编码的车床和数据，结果是什么:)如果你的机器能解决这个问题，那肯定是UTM。
你知道这些不同问题属于 NP 的推理思路吗？就像“当我有一台可以解决哈密顿问题的机器时，我可以解决 3-sat 问题吗？”您当然可以用同样的方法来回答您的问题。
Sure: Given encoded turning machine and data, what is the result :) If your machine can solve this problem, it is surely UTM.
Do you know the line of reasoning why those different problems are in NP? Like 'can i solve the 3-sat problem when I have a machine that solves the Hamiltonian problem?' You can surely use the same to answer your question.
证明特定系统的图灵完备性并非易事，除非您可以轻松证明它与已知的图灵完备性系统等效/同构。简短的回答：没有简单的测试可以让你的机器通过来检查它是否是图灵完整的。您必须分析并显示整个系统的属性。
如果您想了解有关此主题的更多信息，请阅读这些有关 图灵完整性 和 可计算性理论。
Proving the Turing completeness of a particular system is not trivial, unless you can easily show that it's equivalent/isomorphic to another system that is know to be Turing complete. So short answer: there is no simple test that you can put your machine through to check whether it is Turing complete. You have to analyze and show properties of the system as a whole.
If you want to learn more about this topic, read these articles about Turing completeness and computability theory.
想象一下 UTM，如果您必须编写代码（高级）来模拟图灵机，您将如何进行。您将需要以下内容：
1. 保存输入符号和 yiu 将对其执行的操作的数组。
2.一个数组（可能是二维）来保存您将提示用户的转换函数。
3.一种读取用户输入的转换函数并在数组 1 上进行模拟的算法。
4.您的程序需要很少的变量来跟踪其自身状态。
如果您以这种方式思考，如果您最终得到完美工作的代码，那么您最终就会得到一个完美的 UTM。
然而，问题是无论你的代码有多高效，你都无法阻止用户输入可能导致你的代码永远运行的转换函数。因此，在某些问题上，UTM 会失败，然后我们说，对于这些问题我们无法开发会员资格测试机。（尽管请注意，会员资格验证机始终是可能的）
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)