非決定的チューリングマシン
雑な理解をする場合
さらに無限の並列実行が可能
例えば自然数$ nの素因数分解は$ \sqrt{n}までの有限個の素数全ての組み合わせを試すことを同時に行う
あるいは、最も最適な解を運良く必ず最初に引き当てると言っても良い
例えば 1001 の素因数分解をするときに何故か $ 7\times11\times13から試し始めて、1 回で試行錯誤が終了する
イメージで理解する場合
実際は数学的に厳密な定義が存在する
が、ほぼ決定的チューリングマシンと同様なため、書くのがめんどくなって執筆者(Summer498.icon)が疾走しました 代わりに誰か書いてください