Ank*_*rVj 2 turing-machines computation-theory
包含任意数量的带符号的图灵机M可以由仅包含三个带符号的一个M'模拟:{0,1,B}(B =空白).
M可以用只有两个磁带符号的M"模拟,比如{1,B}吗？
第一步 - 从任何TM到只用零和零的TM - 并不像你想象的那么难,但不像其他人所说的那么容易.我们的想法是为字母表中的每个符号开发一个固定长度的二进制编码.然后,您更新有限状态控制,以便在每个步骤中TM扫描适当的位数,确定要移动的方式和要写入的符号,写入新符号的二进制表示,然后重复.这可以通过拥有一个巨大的有限状态控制来完成,我将把细节留给读者,因为它是非常迂腐的,可以了解它是如何工作的.:-).需要注意的一个细节是,在这种结构中,您将空白符号表示为一系列空白,其长度与您发明的二进制符号相同.
要仅使用1和B实现TM,您可以使用类似的技巧.首先,将TM减少为仅使用1,0和B.我们将再次将符号集减少一个较小的符号集,但是我们必须更加聪明,因为磁带上有无限多个空白它.我们将使用以下编码:
当我们使用这种编码方案运行TM时,如果我们走过先前访问过的磁带的末尾,我们将遇到无数多个空白符号,幸运的是,这些符号与我们对空白符号的编码相对应.
唯一的挑战是如何将输入编码为这个新的TM,以便我们可以将其转换为上述格式.由于空白不能出现在TM输入中,因此输入必须以一元编码.然后我们规定对于旧机器的任何二进制字符串w,新机器的输入应该是数字1w的一元编码.然后我们将机器的第一步从一元编码转换为上面的二进制编码.这可以用两个符号来完成,但细节真的很难,而且我会再次对它们进行试探.如果需要,您可以计算出详细信息.
希望这可以帮助!