ゼノマシン

数学とコンピュータサイエンスにおいて、ゼノマシン（ZMと略され、加速チューリングマシン、ATMとも呼ばれる）は、可算無限個のアルゴリズムステップを含む計算を実行できるチューリングマシンに関連する仮想的な計算モデルである。 ^[1] これらのマシンは、ほとんどの計算モデルでは除外されている。

ゼノマシンのアイデアは、1927 年にヘルマン ワイルによって初めて議論されました。この名前は、古代ギリシャの哲学者エレアのゼノンに帰せられるゼノンのパラドックスに由来しています。ゼノマシンは、いくつかの理論で重要な役割を果たします。たとえば、物理学者フランク J. ティプラーによって考案されたオメガ ポイントの理論は、ゼノマシンが可能である場合にのみ有効です。

ゼノ マシンは、無限の数のステップを実行し、さらにステップを実行し続けることができるチューリング マシンです。これは、ステップを実行するために単位時間かかるスーパータスクと考えることができます。つまり、最初のステップには 0.5 単位の時間、2 番目のステップには 0.25 単位の時間、3 番目のステップには 0.125 単位の時間などかかり、1 単位の時間後には、可算無限の数のステップが実行されることになります。 ${\displaystyle {\frac {1}{2^{n}}}}$${\displaystyle n}$

ゼノマシンのより正式なモデルは、無限時間チューリングマシンである。これは、ジェフリー・キダーの未発表の研究で初めて定義され、ジョエル・ハムキンスとアンディ・ルイスによって無限時間チューリングマシンで拡張された^[2]。無限時間チューリングマシンは、古典的なチューリングマシンモデルを拡張して、超限時間、つまりすべての有限時間を超えた時間を含めたものである。[ 2 ^] 古典的なチューリングマシンは、ステップ（開始状態、空のテープ、読み取りヘッドがセル 0 にある）での状態と、ある状態から次の状態に移行するための手順を持つ。このようにして、チューリングマシンの状態は、自然数に対応するすべてのステップに対して定義される。ITTM はこれらの特性を維持するが、極限順序数、つまりどの順序数でもどの順序数の後続でもない順序数でのマシンの状態も定義する。チューリングマシンの状態は、次の 3 つの部分で構成される。 ${\displaystyle 0}$${\displaystyle 0}$

1. 州
2. 読み書きヘッドの位置
3. テープの内容

古典的なチューリングマシンがラベル付けされた開始状態、つまりプログラムの開始時の状態を持つのと同様に、ITTMはラベル付けされた限界状態を持ち、これはマシンの任意の極限順序における状態である。 [ ^1]これは、マシンがこの状態にアクセスする他の方法がない場合、たとえばノードがこの状態に遷移しない場合でも当てはまる。読み取り書き込みヘッドの位置は、任意の極限ステップで に対してゼロに設定される。^{[1] [2]} 最後に、テープの状態は、以前のテープ状態の極限上限によって決定される。あるマシン、セル、および極限順序の 場合、${\displaystyle T}$${\displaystyle k}$ ${\displaystyle \lambda }$

${\displaystyle T(\lambda )_{k}=\limsup _{n\rightarrow \lambda }T(n)_{k}}$

つまり、時刻 における 番目のセルは、マシンが に近づくにつれて、その同じセルの極限の上限になります。^[1]これは、収束するかどうかにかかわらず、極限と考えることができます。^[1]${\displaystyle k}$${\displaystyle \lambda }$${\displaystyle \lambda }$${\displaystyle 1}$

ゼノマシンは、古典的なチューリングマシンの停止問題を解決できることから、古典的なチューリングマシンよりも強力な計算モデルとして提案されている。 ^[3]クリスティアン・カルデとルートヴィヒ・シュタイガーは、ゼノマシンで実行した場合の停止問題の解決策として、次の疑似コードアルゴリズムを提示している。 ^[4]

プログラムを開始する
    出力テープの最初の位置に 0 を書き込みます。
    ループ開始
        与えられた入力に対して、与えられたチューリングマシンの 1 つの連続ステップをシミュレートします。
        チューリングマシンが停止した場合
            出力テープの最初の位置に 1 を書き込み、ループを終了します。
    ループ終了
プログラム終了

単位時間が経過した後の出力テープの最初の位置を調べることで、与えられたチューリングマシンが停止するかどうかを判断できます。 ^[4] 対照的に、Oron Shagrir は、Zeno マシンの状態は区間 でのみ定義されるため、時刻 でテープを検査することは不可能であると主張しています。さらに、古典的なチューリングマシンにはタイミング情報がないため、加速するかどうかに関係なくタイミング情報を追加しても、計算能力は追加されません。^[3]${\displaystyle 1}$${\displaystyle [0,1)}$${\displaystyle 1}$

しかし、無限時間チューリングマシンは与えられたアルゴリズムを実装することができ、正しい解で時間で停止することができる。 ^[2]なぜなら、無限時間チューリングマシンは超限ステップの状態を定義しているからである。^[3] すべての集合は無限時間チューリングマシンによって決定可能であり、集合は半決定可能である。^{[2] [説明が必要]}${\displaystyle \omega }$${\displaystyle \Pi _{1}^{1}}$${\displaystyle \Delta _{2}^{1}}$

ゼノマシンは自身の停止問題を解決することができない。^[4]

• 極限の計算
• スペッカーシーケンス
• ロス・リトルウッドのパラドックス