Super-recursive algorithm とは

計算能力理論では、超再帰アルゴリズムは、より強力な一般的なアルゴリズムの一般化です。つまり、チューリングマシン以上の計算を行います。この用語はMark Burginによって紹介された。彼の著書「超再帰アルゴリズム」は理論を発展させ、いくつかの数学的モデルを提示する。従来のアルゴリズムのチューリングマシンおよび他の数学モデルは、研究者が再帰アルゴリズムおよびその計算の特性を見つけることを可能にする。同様の方法で、帰納的チューリングマシンなどの超再帰アルゴリズムの数学的モデルによって、研究者は超再帰アルゴリズムの特性およびその計算を見つけることができます。
Burgin、ならびに他の研究者(Selim Akl、Eugene Eberbach、Peter Kugel、Jan van Leeuwen、Hava Siegelmann、Peter Wegner、およびJiříWiedermannを含む)は、異なる種類の超再帰アルゴリズムを研究し、超再帰アルゴリズムは、超再帰アルゴリズムを用いて教会 – チューリング論文を反証することができると主張してきたが、この観点は数学的コミュニティ内で批判され広く受け入れられていない。