可以构造一台图灵机
从而,任意一台图灵机接受的语言 的变种(所谓变种,就是比如 A 接受 字符串 s, 那么
也就是,
那么,
consider that, 这里的
最 “复杂” 的图灵机
可以构造一台图灵机
从而,任意一台图灵机接受的语言 的变种(所谓变种,就是比如 A 接受 字符串 s, 那么
也就是,
那么,
consider that, 这里的
我觉得你可以把你这里的这个U描述一下(中层描述,它的输入是什么?它要做什么,返回什么?),另外就是,通用图灵机(记为
U在某种意义上是可以解决任意一台图灵机可以解决的问题,但它并不能解决问题本身,因为我们需要针对问题设计出对应的图灵机M,才能把M作为输入扔给U,然后U"解决"了该问题。
至于U是否复杂,这个无法衡量,因为没有衡量标准。就描述上的复杂性来看,U的描述本身是很简单的(就是模拟嘛),复杂的也许是它的输入