無制限の非決定性

コンピュータサイエンスにおいて、無制限非決定性または無制限不確定性とは、同時実行性の特性であり、共有リソースの競合の調停の結果として、要求へのサービス提供の遅延が無制限になる可能性があるが、要求が最終的にサービスされることは保証される。無制限非決定性は、同時実行性の表示的意味論の開発において重要な問題となり、後にハイパーコンピューティングの理論的概念の研究の一部となった^[1]。

無制限の非決定性についての議論は、公平性の議論と絡んでくる傾向があります。基本的な概念は、すべての計算パスが「公平」でなければならないということです。つまり、マシンが無限に頻繁に状態に入る場合、その状態からのすべての可能な遷移をとらなければならないということです。これは、マシンが可能な場合は要求に確実に対応することを要求することを意味します。なぜなら、状態の無限シーケンスは、要求が処理される遷移がない場合にのみ許可されるからです。同様に、すべての可能な遷移は、無限の計算で最終的に発生する必要がありますが、遷移が発生するには無制限の時間がかかる可能性があります。この概念は、「公平な」コインを投げるという局所的な公平性とは区別されます。この概念では、有限数のステップでは常に表が出る可能性があるものの、ステップ数が増えると、これはほぼ確実に発生しなくなります。

文字列の併合における公平な非決定性または無制限の非決定性の役割の例は、ウィリアム・D・クリンガーの1981 年の論文で示されています。彼は、2 つの文字列の「公平な併合」を、各文字列の各文字が最終的に出現する 3 番目の文字列と定義しました。次に、2 つの文字列のすべての公平な併合の集合merge (S, T)を単調関数であると仮定して検討しました。次に、 merge (⊥,1 ω )⊆ merge (0,1 ω ) であると主張しました。ここ^で、⊥は^空のストリームです。ここで、 merge (⊥,1 ^ω ) = {1 ^ω } であるため、1 ^{ω は}merge (0,1 ^ω )の要素である必要があり、これは矛盾です。彼は次のように結論付けました。

公平なマージは、ストリーム上で動作する非決定性データフロープログラムとして記述することはできないようです。 ^[2]

エドガー・ダイクストラは、無制限の非決定性を持つシステムを実装することは不可能であると主張した^[3]。このため、トニー・ホーアは「効率的な実装は合理的に公平であるように努めるべきだ」と提案した^{[4] 。}

非決定性チューリングマシンは、有界な非決定性しか持たない。同様に、非決定性の唯一の源としてガードコマンドを含むシーケンシャルプログラムも、有界な非決定性しか持たない。^[3]簡単に言えば、選択非決定性は有界である。 ゴードン・プロトキンは、パワードメインに関する最初の論文で証明を与えた。

ここで、与えられた非決定性プログラムPの実行シーケンスの初期セグメントの集合は、与えられた状態から始まり、ツリーを形成します。分岐点は、プログラムの選択ポイントに対応します。各選択ポイントでは常に有限個の選択肢しかないため、ツリーの分岐係数は常に有限です。つまり、ツリーは有限です。ここで、ケーニッヒの補題は、有限ツリーのすべてのブランチが有限である場合、ツリー自体も有限であることを意味します。この場合、これは、Pのすべての実行シーケンスが終了する場合、実行シーケンスは有限個しかないことを意味します。したがって、 Pの出力セットが無限である場合、それは [終了しない計算] を含む必要があります。^[5]

ウィリアム・クリンガーは、プロトキンによる上記の証明について、次のような分析を行った。

この証明は、ある無限枝のあらゆるノードxに何らかの計算cで到達できる場合、その枝のあらゆるノードx を訪れる計算c が存在するという前提に依存しています。... 明らかに、この前提は論理からではなく、選択ポイントに与えられた解釈から生じます。この前提は、メッセージの到着における有限遅延のため、到着非決定性 [アクター モデルにおけるメッセージの到着] で失敗します。無限枝の各ノードは制限のある枝上にある必要がありますが、無限枝自体に制限がある必要はありません。したがって、無限枝の存在は、必ずしも終了しない計算を意味するわけではありません。[ ^2]

Spaanらは、無制限に非決定的なプログラムが停止問題を解決することが可能であると主張しており、彼らのアルゴリズムは次のように定義される2つの部分から構成されている。^[6]

プログラムの最初の部分は、2 番目の部分から自然数を要求します。それを受け取った後、目的のチューリング マシンをそのステップ数だけ繰り返し、マシンがまだ停止しているかどうかに応じて受け入れるか拒否するかを決定します。

プログラムの 2 番目の部分では、要求に応じて自然数を非決定的に選択します。数値は 0 に初期化された変数に格納され、その後、プログラムは変数を増分するか、要求に応えるかを繰り返し選択します。公平性の制約により、要求は最終的に対応される必要があります。そうでない場合、"変数を増分する" ブランチのみが実行される無限ループが発生します。

明らかに、マシンが停止した場合、このアルゴリズムには受け入れるパスがあります。マシンが停止しない場合、プログラムの 2 番目の部分が返す数値に関係なく、このアルゴリズムは常に拒否します。

Clinger とCarl Hewitt ^[要出典]は、無制限の非決定性の特性を組み込んだ並行計算のモデル (アクター モデルとして知られている) を開発しました [Clinger 1981; ^[7] ; ^[8] ; ^[9] ]。これにより、上記のようにチューリング マシンでは実装できない計算が可能になります。ただし、これらの研究者は、並行計算のモデルでは、Church、Kleene、Turingなどによって定義された再帰関数^{のクラス[要出典]}外の関数を実装できないことを強調しています (並行計算における不確定性 を参照)。

ヒューイットは、アービターと呼ばれる計算回路が安定するまでにかかる時間に制限はないと主張して、無制限の非決定性の使用を正当化しました(電子工学における準安定性を参照)。アービターは、コンピューターのクロックがキーボード入力、ディスク アクセス、ネットワーク入力などの外部からの入力と非同期に動作する状況に対処するためにコンピューターで使用されます 。そのため、コンピューターに送信されたメッセージが受信されるまでに無制限の時間がかかり、その間にコンピューターは無制限の数の状態を移動する可能性があります。

さらに彼は、電子メールは配送前にサーバー上に無期限に保存できるため、無制限の非決定性が可能であり、インターネット上のサーバーへのデータリンクも同様に無期限にサービス停止になる可能性があると主張した。これが無制限の非決定性論争を引き起こした。^[10]

ヒューイットは、公平性の問題は部分的にはグローバル状態の観点から生じると主張した。最も古い計算モデル（チューリングマシン、ポストプロダクション、ラムダ計算など）は、計算ステップを表すためにグローバル状態を使用する数学に基づいている。各計算ステップは、計算の1つのグローバル状態から次のグローバル状態へである。グローバル状態アプローチは、有限状態マシンやプッシュダウンスタックマシン（それらの非決定性バージョンを含む）のオートマトン理論に引き継がれた。これらのモデルはすべて、有界非決定性という特性を持つ。つまり、マシンが初期状態で起動したときに常に停止する場合、停止できる状態の数には限界がある。

Hewitt は、グローバル状態非決定性における選択と、彼のアクター モデルの到着順序不確定性 (非決定性)の間には根本的な違いがあると主張しました。グローバル状態非決定性では、「次の」グローバル状態に対して「選択」が行われます。到着順序不確定性では、無制限の時間内に各到着順序がローカルで調停によって決定されます。ローカル調停が進行中に、他の場所で無制限のアクティビティが発生する可能性があります。グローバル状態は存在せず、したがって、「次の」グローバル状態に関して「選択」を行う必要もありません。

• Hewitt, Carl ; Bishop, Peter; Steiger, Richard (1973 年 8 月)。「人工知能のためのユニバーサル モジュラー ACTOR 形式」。人工知能に関する第 3 回国際合同会議議事録。IJCAI'73。スタンフォード: Morgan Kaufmann。pp. 235–245。
• ミルナー、ロビン(1973)。「プロセス: コンピューティング エージェントの数学的モデル」。論理コロキウム議事録。論理コロキウム '73。ブリストル: ノース ホランド。pp. 157–173。
• Hewitt, Carl ; Bishop, Peter; Greif, Irene ; Smith, Brian; Matson, Todd; Steiger, Richard (1973 年 10 月)。「アクター誘導とメタ評価」。プログラミング言語の原理に関する第 1 回 ACM SIGACT-SIGPLAN シンポジウムの議事録。POPL'73。マサチューセッツ州ボストン: Association for Computing Machinery。pp. 153–168。doi :10.1145/512927.512942。
• Hewitt, Carl ; Bishop, Peter; Steiger, Richard; Greif, Irene ; Smith, Brian; Matson, Todd; Hale, Roger (1974 年 4 月)。「非再帰的制御構造の動作意味論」。Robinet, B. (編)。Colloque sur la programming の議事録。プログラミング シンポジウム。パリ: Springer Berlin Heidelberg。pp. 385–407。doi : 10.1007 / 3-540-06859-7_147。ISBN 9783540378198。
• Greif, Irene (1975 年 8 月)。並列プロセスの通信のセマンティクス(博士論文)。マサチューセッツ工科大学、電気工学およびコンピュータ サイエンス学部。hdl : 1721.1/57710。
• Hewitt, Carl ; Baker, Henry (1977 年 8 月)。「アクターと連続関数」。Neuhold, Erich J. (編)。プログラミング概念の形式的記述に関する IFIP ワーキング カンファレンスの議事録。IFIP'78。セント アンドリュース、ニューブランズウィック州、カナダ: North-Holland。ISBN 9780444851079。
• カーン、ジル、マッククイーン、デイヴィッド (1976)。並列プロセスのコルーチンとネットワーク (研究レポート) 。2022年3 月 9 日閲覧。
• Baker, Henry (1978 年 1 月)。リアルタイム コンピューティングのためのアクター システム(博士論文)。マサチューセッツ工科大学、電気工学およびコンピューター サイエンス学部。
• スミス、マイケル (1978)。 「電力ドメイン」。コンピュータとシステム科学ジャーナル。16 :23–36。doi : 10.1016/0022-0000(78)90048-X。
• Milne , George; Milner, Robin (1979 年 4 月)  。「並行プロセスとその構文」。Journal of the ACM。6 ( 2): 302–321。doi : 10.1145/322123.322134。S2CID 16565064。
• Francez, Nissim ; Hoare, CAR ; Lehmann, Daniel J .; de Roever, Willem P. (1979 年 12 月)。「非決定性、並行性、および通信のセマンティクス」。Journal of Computer and System Sciences。19 ( 3​​): 290–308。doi : 10.1016 /0022-0000(79)90006-0。
• Lynch, Nancy A. ; Fischer, Michael J. (1979 年 7 月)。「分散システムの動作と実装の記述について」。Kahn , Gilles (編)。同時計算の意味論に関する国際シンポジウムの議事録。同時計算の意味論。エビアン、フランス: Springer-Verlag。pp. 147–171。doi :10.1007/BFb0022468。ISBN 9783540351634。
• Schwartz, Jerald S. (1979 年 7 月)。「並列処理の表示的意味論」。Kahn , Gilles (編)。同時計算の意味論に関する国際シンポジウム議事録。同時計算の意味論。エビアン、フランス: Springer -Verlag。pp. 191–202。doi :10.1007/ BFb0022470。ISBN 9783540351634。
• Wadge, William W. (1979 年 7 月)。「データフロー デッドロックの拡張的処理」。Kahn , Gilles (編)。同時計算の意味論に関する国際シンポジウムの議事録。同時計算の意味論。エビアン、フランス: Springer-Verlag。pp. 285–299。doi : 10.1007/ BFb0022475。ISBN 9783540351634。
• Back, Ralph-Johan (1980 年 7 月)。「無制限の非決定性の意味論」。de Bakker, Jaco ; van Leeuwen, Jan (編)。第 7 回オートマトン、言語、プログラミングに関するコロキウム。国際オートマトン、言語、プログラミングに関するコロキウム。オランダ、ノールトウェイカーハウト: Springer-Verlag Berlin Heidelberg。pp. 51–63。doi : 10.1007 /3-540-10003-2_59。
• Park, David (1979)。 「公平な並列処理の意味論について」。Bjørner , Dines (編)。抽象ソフトウェア仕様。1979 コペンハーゲン冬季学校。コペンハーゲン: Springer-Verlag Berlin Heidelberg。pp. 504–526。doi :10.1007/3-540-10007-5_47。

• Dana Scott . 「表示的意味論とは何か?」 MIT コンピュータサイエンス研究所特別講演シリーズ。1980 年 4 月 17 日。

• Clinger, William (1982 年 8 月)。「非決定的な必要による呼び出しは、遅延呼び出しでも名前による呼び出しでもない」。Park, David MR、Friedman, Daniel P. (編)。LISPおよび関数型プログラミングに関する 1982 ACM シンポジウムの議事録。LFP'82。ペンシルベニア州ピッツバーグ: Association for Computing Machinery。pp. 226–234。doi : 10.1145 /800068.802154。
• Brookes, SD; Hoare , CAR ; Roscoe, AW (1984年7 月) 。「通信シーケンシャル プロセスの理論」。Journal of the ACM。31 ( 3): 560–599。doi : 10.1145/828.833。S2CID  488666 。
• Roscoe, AW (1988 年 1 月)。「CSP における無制限の非決定性」。CSP に関する 2 つの論文(PDF) (技術モノグラフ)。オックスフォード大学コンピューティング研究所。PRG67。2022年3 月 10 日に閲覧。
• Roscoe, AW ( 1997年 11 月 10 日)。並行性の理論と実践。Prentice-Hall。ISBN 9780136744092。
• シュミット、デイビッド A. (1994 年 3 月)。型付きプログラミング言語の構造。MIT 出版。ISBN 9780262193498。
• バトラー、マイケル、モーガン、キャロル(1995 年 1 月)。 「アクション システム、無制限の非決定性、および無限トレース」。コンピューティングの形式的側面。7 (1): 37–53。doi : 10.1007/ BF01214622。S2CID  2135743 。
• Sudkamp, Thomas A. (1997 年 1 月 3 日)。言語とマシン: コンピュータ サイエンスの理論入門(第 2 版)。Addison- Wesley。ISBN 9780201821369。
• Aceto, Luca; Gordon, Andrew D.編 (2005 年 8 月)。代数的プロセス計算: 最初の 25 年間とそれ以降。PA'05。ボローニャ大学レジデンシャル センター ベルティノーロ (フォルリ)、イタリア: BRICS。
• Brookes, Stephen (2005 年 8 月)。「Retracing CSP」(PDF)。Aceto, Luca、Gordon, Andrew D. (編)。代数的プロセス計算: 最初の 25 年間とそれ以降。PA'05。ボローニャ大学レジデンシャル センター ベルティノーロ (フォルリ)、イタリア: BRICS。pp. 75–80。2022年3 月 10 日に取得。