- 317 名前：１３２人目の素数さん mailto:sage [2022/09/18(日) 15:03:49.24 ID:ldv25uGN.net]
- 具体的に書こう。計算機科学には「信託機械」という概念がある。信託機械とは、
チューリングマシンに神託(オラクル)と呼ばれるブラックボックスを付与した機械のこと指す。
このオラクルは、特定の問題を1ステップで決定可能である。よくあるオラクルとしては、
チューリングマシンの停止問題といった、決定不能な問題に対するオラクルが挙げられる。
そのようなオラクルを付与したチューリングマシンでは、チューリングマシンの停止問題が1ステップで解けてしまう。
もちろん、具体的にどうやって解いているのかは我々には分からない。なんたって、
チューリングマシンの停止問題は決定不能問題なのだから、具体的に分かるわけがない。
それでも、そのようなオラクルを付加したチューリングマシンでは、チューリングマシンの停止問題が
1ステップで解けてしまう。これはちょうど、選択公理を公理として採用するのと同じノリである。
