非決定的な動作をするチューリングマシン

雑な理解をする場合

決定的チューリングマシンと同様、無限のメモリを持つコンピュータ

さらに無限の並列実行が可能

例えば自然数nの素因数分解は\sqrt{n}までの有限個の素数全ての組み合わせを試すことを同時に行う

あるいは、最も最適な解を運良く必ず最初に引き当てると言っても良い

例えば 1001 の素因数分解をするときに何故か 7\times11\times13から試し始めて、1 回で試行錯誤が終了する

イメージで理解する場合

ほぼ決定的チューリングマシンと同様だが、状態を非決定的に遷移させられる

実際は数学的に厳密な定義が存在する

が、ほぼ決定的チューリングマシンと同様なため、書くのがめんどくなって執筆者()が疾走しました

代わりに誰か書いてください