可以仅用两个带符号构建图灵机吗？
包含任意数量磁带符号的图灵机 M 可以通过仅包含三个磁带符号的 M' 来模拟：{0, 1, B}（B = 空白）。
M 可以用只有两个磁带符号（例如 {1, B}）的 M" 来模拟吗？
A Turing machine M containing any number of tape symbols can be simulated by one M' containing just three tape symbols: {0, 1, B} (B = Blank).
Can M be be simulated by a M" that has just two tape symbols, say {1, B}?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
第一步 - 从任何 TM 到只有 1 和 0 的 TM - 并不像您想象的那么难，但也不像其他人所说的那么容易。这个想法是为字母表中的每个符号开发固定长度的二进制编码。然后，您更新有限状态控制，以便 TM 在每一步扫描适当的位数，决定移动方式和写入哪个符号，写入新符号的二进制表示，然后重复。这可以通过一个巨大的有限状态控制来完成，我将把细节留给读者，因为讨论它的工作原理确实很迂腐。 :-)。需要注意的一个细节是，在此构造中，您将空白符号表示为一系列空白，其长度与您发明的二进制符号相同。
要仅使用 1 和 B 来实现 TM，您可以使用类似的技巧。首先，将 TM 减少为仅使用 1、0 和 B。我们将再次将符号集减少一个更小的符号集，但我们的做法必须更加巧妙，因为磁带上有无限多个空白。它。我们将使用以下编码：
当我们使用这种编码方案运行 TM 时，如果我们走过之前访问过的磁带的末尾，我们将遇到无限多个空白符号，幸运的是，这些符号与我们对空白符号的编码相对应。
唯一的挑战是如何将输入编码到这个新的 TM 中，以便我们可以将其转换为上述格式。由于 TM 输入中不能出现空格，因此输入必须以一元编码。然后我们规定，对于旧机器的任何二进制字符串w，输入到新机器的应该是数字1w的一元编码。然后，机器的第一步是将一元编码转换为上述二进制编码。只需两个符号即可完成此操作，但细节确实很难，我将再次押注于它们。如果您愿意，您可以制定详细信息。
希望这有帮助！
The first step - getting from any TM to a TM with just ones and zeros - is not as hard as you might think but not as easy as what everyone else is saying. The idea is to develop a fixed-length binary encoding for each of the symbols in the alphabet. You then update the finite-state control so that at each step the TM scans the appropriate number of bits, decides which way to move and which symbol to write, writes the binary representation of the new symbol, and repeats. This can be done by having a HUGE finite-state control, and I'll leave the details to the reader since it's really pedantic to go over how it works. :-). The one detail to note is that in this construction you represent the blank symbol as a sequence of blanks with the same length as the binary symbols you invented.
To implement a TM using just 1 and B you use a similar trick. First, reduce the TM to use just 1, 0, and B. We'll again reduce the symbol set by a smaller one, but will have to be a bit more clever with how we do so because the tape has infinitely many blanks on it. We will use the following encoding:
As we run the TM using this encoding scheme, if we ever walk past the end of the previously-visited tape, we will encounter infinitely many blank symbols, which fortunately correspond to our encoding of the blank symbol.
The only challenge is how to encode the input to this new TM so that we can convert it to this above format. Since blanks can't appear in the TM input, the input must be encoded in unary. We then stipulate that for any binary string w of the old machine, the input to the new machine should be the unary encoding of the number 1w. We then have the first step of the machine be to convert from the unary encoding to the above binary encoding. This can be done with just two symbols, but the details are really hard and again I'm going to punt on them. You can work out the details if you want.
Hope this helps!
第一个很简单，想象一下计算机，二进制......
在第一个中，您可以将每个符号编码为 0,1 表示形式。
在第二个中，你可以做两件事：
将 B 视为 0 ...你怎么称呼它并不重要...然后你就有了一台 0,1 机器并且可以编码任何你想要的东西.
将符号编码为一系列 1，由 B 分隔。第 N 个符号将包含 N 个 1
The first one is easy, think of a computer, binary....
In the first one you can encode each symbol into a 0,1 representation.
In the second one, you can do 2 things:
Think of the B as 0 ... it doesn't matter what you call it... and then you have a 0,1 machine and can encode whatever you want.
Encode the symbols as a series of ones, separated by a B. The N'th symbol will hold N 1's