最 “复杂” 的图灵机

---

可以构造一台图灵机$U$，其接受任意一台图灵机 $A$ 的编码后模拟该图灵机。
从而，任意一台图灵机接受的语言 的变种（所谓变种，就是比如 A 接受 字符串 s， 那么$U$ 接受 $C(A)*s$ —— $C(A)$ 就是 A 的编码，$*$ 是连结 ），$U$ 都接受。
也就是，$U$ 可以 解决任意一台图灵机可以解决的问题 。

那么，$U$ 是不是 最”复杂“ 的图灵机

consider that, 这里的$U$ 不是$A_{TM}$ 那里提到的那个 universal turing machine

我觉得你可以把你这里的这个U描述一下（中层描述，它的输入是什么？它要做什么，返回什么？），另外就是，通用图灵机(记为$U$)其实是有定义的，粗略描述为：$U(\langle M,w\rangle):$ $U$模拟$M(x)$的计算过程。如果该计算停机，则$U$停机并在纸带上留下计算结果$M(w)$，否则不停机。

U在某种意义上是可以解决任意一台图灵机可以解决的问题，但它并不能解决问题本身，因为我们需要针对问题设计出对应的图灵机M，才能把M作为输入扔给U，然后U"解决"了该问题。

至于U是否复杂，这个无法衡量，因为没有衡量标准。就描述上的复杂性来看，U的描述本身是很简单的（就是模拟嘛），复杂的也许是它的输入$\langle M\rangle$。。。所以需要说明是什么方面的"复杂"。

@oded-zeng

• 上面说的那个U就是师兄描述的那个U
• 最 “复杂” 的这个 复杂 我只能大概的描述一下“复杂”，给不出形式化定义 。其来自于 第六章谈 打印出 <SELF> 的图灵机时说的 “某机器解决x问题，需要至少跟x问题一样复杂”
• 确实，需要先设计好 M 才可以 交给 U，从此处来看或许不可以称 U 解决了所有图灵机可以解决的问题——因为问题还是那些图灵机自己解决的