最近看了科普:计算的极限, 脑洞被打开了。
oracle machine具体定义忘了, 只记得它是可以立刻得到一类问题Q的解答的图灵机。。
下面阐述我的脑洞, 上个图:
如上图, inner world是基于outer world的虚拟机。
这个想法最初来自于一个游戏作业:在一个tick内完成游戏状态的更新。
inner world中有一台oracle machine, 它是沟通inner 和 outer的接口。
小人向oracle machine提交问题Q, outer接收到Q, 随后暂停inner world的运转, 计算出Q的答案后返回给inner world。 在小人看来, 计算没有消耗时间, 时钟A不变。 在outter的观察者看来, clock B走过的时间比clock B更长。
如此, 我们得到了一个能在inner world工作的oracle machine!