オラクルチューリングマシンとOTMプログラム

そういうわけで（何が？）NTMとクラスNPについて、もっと詳しく説明するまえにオラクルチューリングマシン（Oracle Turing Machine）を説明しとこうと思います。

オラクルチューリングマシンのオラクルとはご神託という意味です。どっかのデーターベース大手ではありません。オラクルチューリングマシン（以下OTMと呼ぶ）というのは、TMになにかご神託を付け加えて、問題を解けるようにしたTMのことです。といっても、ご神託もテープからの入力ですが。

ご神託テープでの入力文字列はTMテープと同様ですが、内容は様々です。たとえば、前の記事にあるようにある整数が素数であるかを判断するようなプログラムが入力にあるとして、オラクルテープの内容は既知の素数ということになれば、プログラムの処理時間は著しく減ることが予想されます。もちろん、ラリー・エリソン（オラクル社のCEO：この人もまた強烈な個性の持ち主として知られている。でも、とっても大金持ち（笑い））が出てきてあっという間に問題解決をしてもらっても良いですが。

OTMで解決するようなプログラムのうち多項式時間で解決できるものを、多項式OTMプログラムとこれからは呼ぶことにします。あと、オラクルはプログラム上で何度呼び出してもかまいませんが、間違ってもラリー・エリソンは呼び出さないように。