計算可能性の部分性：新しい視点

部分性は計算可能性のよくある問題であり、無視できない。主な質問は、部分性が発生する場所、具体的には非終端性が発生する場所をよりよく説明できるかどうかだ。この議論は、全関数と自然数の特定部分をドメインとする有限関数を含む特定の関数クラスに焦点を当てている。これらの関数は計算の中で自然に現れる。

これらの関数クラスのための強力な計算可能性理論を展開でき、その中にはすべての部分計算可能関数が考慮される伝統的な計算可能性理論からの重要な発見が含まれる。これを達成するために、ゲーデル数のアイデアを拡張し、より広範なナンバリングを許可する。この新しいアプローチにおける主なアルゴリズム的方法は、順序付けられたリストを調べることだ。つまり、計算を単なるリスト化の形として再定義するということ。

これらの関数クラスのための計算可能性理論を構築することに加えて、新しいナンバリング、いわゆる準ゲーデル数をナンバリングの視点から調査する。これらの新しいナンバリングは完全であり、あらゆる関数クラスを部分計算可能関数のゲーデルナンバー付き集合のセグメントとして特定できることを意味する。さらに、これらの関数クラスの計算可能ナンバリングの構造を研究し、部分計算可能関数と類似の結果を得る。

計算可能関数の一つの特徴は、しばしば部分的に定義されることだ。すべての全計算可能関数を構成的に定義することはできないが、特定の部分計算可能関数を含むより大きな集合を構成的に記述することはできる。関数クラスの明確な記述から、内部の関数にインデックスを付け、一般的な計算方法を確立できる。

歴史的に、計算可能性理論の初期の努力は全関数に対応する関数スキームに焦点を当てており、一般再帰関数の発展に至った。しかし、この研究はすぐにすべてのこうしたスキームを含むように拡大し、部分再帰関数の分類が行われた。このシフトにより、今日広く認識されている複雑で価値ある理論が発展した。

実際の応用において、私たちは通常全計算可能関数だけを気にする。誰も無限ループにはまるアルゴリズムを望んでいないからだ。この懸念は、初期の研究が一般再帰関数にのみ焦点を合わせた理由を説明しているだろう。さらに、再帰数学の一部では、全計算可能関数に関心が残っている、特に無限の対象を有限のもので効果的に近似することに関しては、再帰解析やドメイン理論のような分野で見られる。

私たちがしばしば部分関数よりも全関数に焦点を当てていることを考えると、満足のいく計算可能性理論を作成するためにすべての部分計算可能関数を考慮する必要があるのかどうか、真剣に問い直さなければならない。あるいは、全計算可能関数の集合を拡張して特定の部分関数、すなわちドメインが良好に構造化されているものだけを含む、というより簡略化したアプローチを取れるだろうか。この論文の目的は、特定の有限関数に専念することが可能であることを示すことであり、自然数の特定部分に沿った特定の有限関数と共に全計算可能関数を考慮するだけで十分だと提案する。

自然数の初期セグメント上で定義された関数はかなり関連性があるようだ。すべての全関数は、そのような初期セグメント関数の一連によって効果的に近似でき、これはさまざまな文脈で活用されている。たとえば、特定の引数に対して原始再帰によって定義された関数を評価するとき、その引数によって決定される初期セグメントの関数の制限を計算しなければならない。同様に、初期セグメント関数はプログラムテストのサンプルとして利用されている。

検証中の関数クラスは、プログラミングのサークルだけでなく、より広いコンピュータサイエンスの分野でも重要だ。無限の対象を有限の実体によって効果的に近似することに関連する文脈では、全計算可能関数が近似される対象の識別子として機能する。この使用は初期セグメント関数に意味を持って拡張できる。各関数は有限の有限オブジェクトの列に対応し、あるレベルの曖昧さを示している。近似された対象が完全には定義されていないからだ。

この観点から、初期セグメント関数は近似可能な対象の位相空間における近傍の識別子として機能する。私たちは、考えている関数から代数的ドメインの計算可能要素の集合への写像を特定できるので、初期セグメント関数はドメインの基底要素を指し、スコットの位相の基底を形成する。

最初の研究では、他の学者と協力して、計算可能性理論を発展させるためにすべての部分計算可能関数を考慮する必要があるかどうかを調査した。私たちの仕事は、すべての全計算可能関数と限られたドメインを持つ初期セグメント関数を計算するように設計された修正チューリングマシンモデルから始まった。この関数クラスのためのナンバリングを提案したが、ゲーデルナンバリングに似たこのナンバリングの特徴づけが欠けていた。

このナンバリングに関連する計算可能な普遍関数は存在したが、対応する関数クラスには含まれていなかった。しかし、普遍関数のグラフは全計算可能関数によって列挙でき、これはゲーデルナンバリングの重要な列挙定理に結びつく。さらに、ゲーデルナンバリングは普遍関数が計算可能なすべてのナンバリングの中で還元可能性に関する最大構造を表している。

任意の計算可能な列挙に対して、そのクラス内の関数のグラフの計算可能な列挙が存在し、その列挙のインデックスを計算する全計算可能関数が存在することが分かる。この条件を満たすナンバリングを準ゲーデルナンバリングと呼ぶ。このような二つのナンバリングが再帰的に同型であることが示される。

さらに、伝統的な計算可能性理論から知られている重要な定理は、この新しいナンバリングに移転でき、古典的な計算可能性理論の結果を必要としない。すべてのゲーデルナンバリングもまた準ゲーデルナンバリングとして適格であるため、新しい概念がゲーデルナンバリングのアイデアの意義のある進展を表すことが確認できる。

伝統的な計算可能性理論では、計算可能な列挙のアイデアが重要であることが証明された。たとえば、部分再帰演算子の概念は、計算可能列挙集合を構成する何の概念に由来している。したがって、計算可能な列挙は、私たちがここで発展させようとしている計算可能性理論へのアプローチにおいて重要な意味を持つ。多くの証明には関数グラフの列挙を構築することが含まれている。

続くセクションでは、準ゲーデルナンバリングに基づいた計算可能性理論の発展を詳述する。最初に、全計算可能関数と与えられた長さで定義された特定の初期セグメント関数を含む関数クラスを紹介する。これらのクラスが、すべての部分計算可能関数のゲーデルナンバリングに関連する標準ナンバリングを持つことを示す。私たちが到達した標準ナンバリングは、具体的には準ゲーデルナンバリングである。これらの関数クラスのさまざまな応用についても掘り下げる。

次に、準ゲーデルナンバリングがゲーデルナンバリングに依存せずに達成できることを示す。我々のクラスの関数を正確に計算するマシンモデルを提示することで、対応するナンバリングを定義することができ、それが準ゲーデルナンバリングであることが明らかになる。これは、私たちが調べている関数クラスに基づいて計算可能性理論を構築できることを確立し、すべての部分計算可能関数に関する理論の事前知識を必要としない。

私たちは進んで、準ゲーデルナンバリングの性質に基づいて計算可能性理論から重要な結果を抽出する。SMN定理や置換の効果、正規形定理、再帰定理などのいくつかの著名な定理がここでも適用されることを示す。しかし、議論する部分関数は全計算可能関数に拡張できるが、その拡張は問われる部分関数のインデックスから効果的に導出できない。また、初期セグメント関数のインデックスからそのドメインの長さも抽出できないことに注意される。

SMN定理の重要性は古典的な理論とは異なることに気づく。特に、インデックス関数の構成に関しては、代替の方法が必要である。これらの関数は異なる方法で構成される必要がある。

計算可能列挙集合を通常のように定義し、空集合または全計算可能関数の範囲として述べる。これらは、必ずしも全体ではない関数の範囲によっても特徴づけることができる。私たちの関数クラスに対して準ゲーデルナンバリングを用いることで、これらの集合を同時に列挙できる。選ばれた定理から、ここでのアプローチでは古典的結果が適用されることが明らかになるが、計算可能列挙集合のドメインの特徴づけに基づく形式は除外される。我々の考慮しているドメインに対する制御があるため、その特徴づけは問題にならない。それでも、一般的な証明では、この特徴づけを用いた多くの議論された構成は他のもので置き換えられることができる。さらに、計算可能列挙集合のコンピュータ生成列挙がゲーデルナンバリングを介して生成されたナンバリングと一致することを示すことができる。これにより、我々が提示する計算可能性理論のアプローチは、従来の方法のように計算可能列挙集合を研究できることが強調される。

関数クラスについての計算可能性理論の探求を進める中で、ライスの定理やマイヒルの定理に関連する結果を導出する。準ゲーデルナンバリングのナンバリング理論的分析も行い、準ゲーデルナンバリングが存在する全計算可能関数の最小スーパーセットの存在を調査する。さらに、関数クラスの全準ゲーデルナンバリングが計算可能に同型であることを示す。

次に、ドメイン理論との関連を調査する。この分野は、より高いタイプの計算可能関数の計算を数学的に満足のいく方法で研究するために設立された。私たちが話している関数が効果的に与えられた代数的ドメインの計算可能要素であり、全ての全数理関数と関心のある初期セグメント関数を含むことを示す。

さらに、我々のドメインから他の効果的に与えられたドメインへの計算可能な写像を確立できることを示す。これにより、効果的に与えられたドメインにおける計算可能要素のすべての許容できる列挙が準ゲーデルナンバリングから生成できると結論できる。

結論として、私たちが探求した関数クラスは、豊かな計算可能性理論の発展を可能にすることを要約する。部分関数によって引き起こされる複雑さにもかかわらず、我々は従来の計算可能性理論に類似した満足のいく結果を生み出す一貫したフレームワークを作り出すことができることを示した。

#関数クラス

続く内容を示すために、特別な一対一で全ての計算可能なマッチングスキームを示そう。このペアリング関数は、通常どおりn-タプルエンコーディングに拡張される。関数デコーディングも同様に、マッチするように定義される。すべてのn-元部分、全体、部分計算可能、全計算可能関数の集合について、それぞれ言及する。これらの関数のアリティと直交積の次元は少なくとも1であると仮定するが、特別なケースについて詳しくは論じない。

次に、我々のクラスのゲーデルナンバリングを考える。関数のアリティが文脈から明らかな場合や重要でない場合は、特に指定せずに表記する。与えられた引数のナンバリングから得られる値は、簡単な形で表記される。

初期セグメントは、その部分集合内のすべての要素が特定の順序に従う場合と定義される。このような部分集合の基数がその長さおよびエッジの長さを定義する。

前述の通り、主な焦点はドメインが空であるか初期セグメントである関数にある。この焦点は、これらのパラメータ内で定義された関数の明確なセットを形成することにつながる。

無限の計算可能列挙集合の中には、注目すべき列挙可能部分集合がある。私たちの初期セグメントを管理するのに役立つ構造を定義することで、議論を容易にする。

これらの関数がどのように機能するかを探求し、それらの列挙特性に特に焦点を当て続ける。指定した関数が標準ナンバリングと特別標準ナンバリングの定義を満たすように条件を設定していく。

条件を満たす関数は、準ゲーデルナンバリングの要求を満たすことを見せることができる。したがって、これらの関数に対して計算可能な普遍関数が効果的に計算できることを示し、彼らの計算可能性の理解を明確にする。

伝統的な計算可能性理論の重要な結果を認識しつつ、これらの準構造が計算可能関数の継続的な検討において固有の方法で機能することを強調する。列挙と制御された構造を通じた強制の展開がこの研究の核心を形成している。

次に、特定の構造の計算可能性の側面を探求し、定義の再確認を通じて準ゲーデルナンバリングの重要な特性を再確認する。これは、我々の前提や発見に明確な接続路を確立し、効果的な写像の原則に基づいていることを保証することである。

この努力を通じて、古典的な計算可能性が我々の新たに定義された構造の精査を耐えられるのか、その影響が計算可能性理論の未来に何をもたらすのかに対する疑問に答えることができることを期待している。我々が述べた結果や方法論が、計算可能性と関数理論の領域でさらなる探求の道を開くことを願っている。