打印自身的图灵机的构造

  • 以下是Introduction to The Theory of Computation 英文第三版的Lemma6.1、Theory6.3的个人理解

  • 下文中,<p> 代表图灵机p的编码

  • 首先,根据Lemma6.1,可以有一台通用机器q,其对于任意w,打印出“输出该w的图灵机”的编码——不过并不保证这台被打印出的图灵机就是那一台生成该w的图灵机——生成w的图灵机可以有很多台,q只打印出其中一台
  • 然后,利用上面这个东西,就可以特殊构造某机器p,其输出w,并且该机器的编码就是q输出的图灵机的编码。从而使得q从p的输出w可以反推出p本身
  • 然后,再特殊一点,这台p输出的w刚好就是q的编码——这是可以做到的,因为q是一台已经确定的,独立于p的图灵机。那么,q的输出+p的输出就刚好是<p><q> ——从而,q与p组合起来的图灵机就是一台打印出自身的图灵机
  • 继续扩展,p可以有多部分构成,使得p和q组合起来的机器不仅仅打印出自身,还可以做其他事情。比如说,p=ab,其中a是打印出<q><b> 的图灵机,b是做其他事情的图灵机。然后,图灵机q就可以打印出图灵机p。如果把他们的输出组合起来就成了<p><q><b> 。当图灵机a、图灵机q运行完之后,纸带上就有了<p><q><b> 。consider that,必然是p先运行,在纸带上留下自己的输出,然后才能q运行,从纸带上获得p的输出,来产生出<p> 。可以修改q,使得其运行后,把控制权交给图灵机b,然后图灵机b从纸带上获得<p><q><b> ,继续执行计算。
  • 上文说的转交控制权的可以这样实现——根据图灵机b定制图灵机q,使得q的accept状态后读入空串到达图灵机b的其实状态。这时候,图灵机q的编码将依赖于图灵机b。
  • 更进一步,再修改图灵机q,其不是使用图灵机p的所有输出,而是使用图灵机p的一部分输出来构造出<p> ,那么,图灵机p就不仅仅可以输出图灵机q的描述,还可以在纸带上留下w(w与<p><q> 无关)。
  • 那么,我们就可以有一台图灵机M,其由图灵机p、q组成,其中,p=ab,那么,这台图灵机会在q运行完后,在纸带上留下w<p><q><b> 。然后,将控制权转给图灵机b,其执行其他计算。从而,我们的这台图灵机M其不仅仅打印出自身,还实现了图灵机b的功能。