Zeno machine とは

数学とコンピュータサイエンスでは、Zenoマシン(ZMと略し、加速チューリングマシン、ATMとも呼ばれます)は、有限の時間内に無数のアルゴリズムステップを実行することを可能にするチューリングマシンに関連する仮想的な計算モデルです。これらのマシンは、ほとんどの計算モデルでは除外されています。
より正式には、Zenoマシンはn番目のステップを実行するために2 n時間の時間を要するチューリングマシンです。したがって、第1のステップは0.5単位時間を要し、第2の値は0.25単位、第3の0.125単位などをとり、1単位時間後に無制限(すなわち、≧0)のステップ数が実行される。
Zenoマシンのアイデアは、1927年にHermann Weylによって最初に議論されました。名前はエレノの古代ギリシャ哲学者ゼノに起因するゼノのパラドックスを指します。 Zenoマシンはいくつかの理論で重要な役割を果たしています。たとえば物理学者Frank J. Tiplerが考案したオメガポイントの理論は、ゼノマシンが可能な場合にのみ有効です。