停止問題

無限ループの中には非常に便利なものもあります。例えば、イベントループは通常、無限ループとしてコーディングされます。^{[ 5 ]}しかし、ほとんどのサブルーチンは終了するように設計されています。^{[ 6 ]}

ハードリアルタイムコンピューティングでは、サブルーチンは終了するだけでなく、指定された期限前に終了する必要があります。^{[ 7 ]}これらの要件を満たすために、プログラマは最小電力のルールを適用し、完全なチューリング完全ではないものの、結果として得られるサブルーチンが指定された期限前に終了することを容易に証明できる制限付きスタイルを使用します。これには、MISRA C、SPARK、Rocqなどの言語が含まれます。

停止問題では、すべてのプログラムと入力に対して機能する判定手順が必要です。しかし、特定のプログラムと入力に対しては、答えは単に「停止する」か「停止しない」のどちらかです。常に「停止する」と答える単純な判定手順と、常に「停止しない」と答える単純な判定手順の2つを考えてみましょう。いずれの場合も、これらのアルゴリズムのうちどちらか一方が正しく答えますが、どちらのアルゴリズムも停止問題を解決しません。

インタプリタは、与えられたソースコードに関わらず、プログラムの実行をシミュレートするプログラムです。このようなプログラムは、プログラムを一定回数実行することで、プログラムが停止することを証明できます。しかし、入力プログラムが停止しない場合、インタプリタも停止しないため、このアプローチでは、前述の停止問題を解決することはできません。つまり、停止しないプログラムに対して「停止しない」という問いに適切に答えることも、プログラムが最終的に停止するか、あるいは永久に実行され続けるかを判断することもできません。

停止問題は、線形限定オートマトン（LBA）または有限メモリを持つ決定性マシンに対して決定可能です。このようなマシンは有限個の可能な構成を持つため、その上で実行される決定性プログラムは最終的に停止するか、以前の構成を繰り返す必要があります。^{[ 8 ]}

有限状態機械は、完全に放置しておくと、最終的には完全に周期的な繰り返しパターンに陥る。この繰り返しパターンの持続時間は、機械の内部状態の数を超えることはできない。

しかし、ミンスキーは次のように指摘している。^{[ 9 ]}

...関係する規模を考えると、状態図の単なる有限性に基づく定理や議論は、あまり意味を持たないのではないかと疑うべきである。

例えば、100万個の2状態コンポーネントを持つコンピュータには、少なくとも^21,000,000個の可能な状態があります。^{[ 9 ]}

これは1の後に約30万個のゼロが続く数字です...たとえそのような機械が宇宙線の周波数で動作したとしても、銀河進化の何億年もの歳月は、そのようなサイクルを旅する時間に比べれば何でもないでしょう。

非決定性有限メモリマシンにおいては、各決定後の状態を列挙することで、マシンが非決定性決定の可能なシーケンスのいずれにおいても停止しないか、一部において停止するか、あるいはすべてにおいて停止するかを判定することも可能です。

• 1900年 （1900）：ダフィット・ヒルベルトは、パリで開催された第2回国際数学者会議で「23の質問」（現在ではヒルベルトの問題として知られている）を提起した。「これらのうち、2番目は、彼が示したように数学の厳密性が依存する「ペアノ公理」の無矛盾性を証明することであった。」^{[ 10 ]}
• 1920年 （1920年） ～1921年 （1921年）：エミール・ポストはタグシステムの停止問題を研究し、それを解決不可能な問題の候補とみなした。^{[ 11 ]}その解決不可能性は、ずっと後になってマービン・ミンスキーによって確立された。^{[ 12 ]}
• 1928年 ( 1928 ) :ヒルベルトはボローニャ国際会議で「第二問題」を再考した。^{[ 13 ]}彼は次の3つの質問を提起した。すなわち、#1: 数学は完全か？ #2: 数学は無矛盾か？ #3: 数学は決定可能か？^{[ 14 ]} 3番目の質問は決定問題(Entscheidungsproblem)として知られている。^{[ 15 ]}
• 1930年 （1930年）：クルト・ゲーデルは、ヒルベルトが1928年に提起した最初の2つの質問に対する答えとして証明を発表した。^{[ 16 ]}「最初は彼（ヒルベルト）はただ怒りと苛立ちを感じていたが、その後、建設的に問題に取り組もうとし始めた…ゲーデル自身も、自分の研究はヒルベルトの形式主義的な観点と矛盾しないと感じ、その考えを論文で表明した。」^{[ 17 ]}
• 1931年 （1931）：ゲーデルは「プリンキピア・マテマティカの形式的に決定不可能な命題と関連システムについて I」を出版した。^{[ 18 ]}
• 1935年 4月19日（1935-04-19）：アロンゾ・チャーチは「初等整数論の解決不可能な問題」を発表し、効果的に計算可能な関数の直感的な概念は、一般的な再帰関数、あるいは同等にラムダ定義可能な関数によって形式化できると提案した。彼は、ラムダ計算の停止問題（つまり、与えられたラムダ式が正規形を持つかどうか）は効果的に計算できないことを証明した。  ^{[ 19 ]}
• 1936年 （1936）：チャーチは再帰関数による計算の概念を用いて、決定問題が解けないことの最初の証明を発表した。^{[ 20 ]}
• 1936年 10月7日（1936-10-07）：エミール・ポストの論文「有限組み合わせプロセス。定式化I」が受理される。ポストは自身の「プロセス」に「（C）停止」という指示を追加した。彼は、決定するプロセスが各特定の問題に対して終了する場合、そのようなプロセスを「タイプ1」と呼んだ。  ^{[ 21 ]}
•  1936 年5 月 ( 1936-05 )  – 1937 年1 月( 1937-01 ) :アラン・チューリングの論文「計算可能な数とその決定問題への応用」が1936 年 5 月に印刷にかけられ、1937 年 1 月に印刷されました。^{[ 22 ]}チューリングは、3 つの問題が決定不可能であることを証明しました。「充足問題」、「印刷問題」、そして決定問題です。^{[ 23 ]}チューリングの証明は、機械による計算の概念を導入することで、チャーチの証明とは異なります。これは、「解決不可能であることが証明された決定問題の最初の例」の 1 つです。^{[ 24 ]}  
• 1939年 （1939年）：J.バークレー・ロッサーは、ゲーデル、チャーチ、チューリングによって定義された「効果的な方法」の本質的な等価性を指摘した。^{[ 25 ]}
• 1943年 （1943年）：スティーブン・クリーネは論文の中で、「完全なアルゴリズム理論を構築するにあたって、我々が行うのは、ある手続きを記述することである。その手続きは必ず終了し、その結果から『述語の値は真か？』という問いに対して、『はい』または『いいえ』という明確な答えを読み取ることができるような方法で終了する。」と述べている。
• 1952年 （1952年）：クリーネはチューリングマシンの停止問題の解決不可能性についての議論を含め、「最終的に停止する」マシン、つまり停止するマシンの観点からそれを再定式化しました。「...任意のマシンが任意の状況から開始された場合、最終的に停止するかどうかを決定するアルゴリズムはありません。」^{[ 24 ]}
• 1952年 （1952年）：マーティン・デイビスは、1952年にイリノイ大学の制御システム研究所で行われた一連の講義の中で「停止問題」という用語を使用している。これがこの用語の最初の使用例である可能性が高い。^{[ 26 ]}

多くの論文や教科書は、停止問題の不確定性の定義と証明をチューリングの1936年の論文に帰している。しかし、これは正しくない。^{[ 23 ] [ 27 ]}チューリングは、1936年の論文を含め、彼の発表した著作のいずれにも「停止」や「停止」という用語を使用していない。^{[ 28 ]} 1936年から1958年までの学術文献を調べたところ、「停止問題」という用語を使用した最初の出版物はロジャース（1957）であることがわかった。しかし、ロジャースはデイビス（1958）の草稿を入手できたと述べており、^{[ 23 ]}マーティン・デイビスは序文で「専門家はトピックの構成と扱いに何らかの目新しさを見出すかもしれない」と述べているため、^{[ 29 ]}この用語はデイビスに帰属するはずである。^{[ 23 ] [ 27 ]}デイビスは手紙の中で、1952年から停止問題について言及してきたと述べている。^{[ 26 ]}デイビスの著書での使用例は以下のとおりである。^{[ 30 ]}

"[...] 我々は、チューリングマシン Z が与えられた初期状態に置かれた場合に、最終的に停止するかどうかを判定したい。この問題を Z の停止問題と呼ぶ。[...]

定理2.2再帰的に解けない停止問題を持つチューリングマシンが存在する。

関連する問題として、単純なチューリングマシン Z の記号 S _i "に関する印刷問題があります。

デイビスの定式化の先駆けとなりうるのは、クリーネの1952年の声明で、表現が異なるだけである。^{[ 23 ] [ 24 ]}

特定の状況から起動された機械が最終的に停止するかどうかを判定するアルゴリズムは存在しない。

停止問題は、デイビスの印刷問題（「チューリングマシンは、与えられた状態から始めて、与えられた記号を印刷するか？」）とチューリングの 1936 年の論文で検討された印刷問題（「チューリングマシンは、空白のテープから始めて、与えられた記号を印刷するか？」）の両方とチューリング等価である。しかし、チューリング等価性はかなり緩く、2 つの問題が同じであることを意味するものではない。印刷するが停止しないマシンと、停止するが印刷しないマシンが存在する。印刷問題と停止問題は異なる問題を扱っており、重要な概念的および技術的な違いを示している。したがって、デイビスが次のように言ったのは単に謙遜していただけである。^{[ 23 ]}

また、これらの問題の本質的な解決不可能性を最初に明らかにしたのはチューリングであったことも付け加えておくべきだろう。

決定問題は、常に正しい答えで停止するアルゴリズムが存在する場合に決定可能であり、そのようなアルゴリズムが存在しない場合は決定不能であると言われます。チューリングは、オリジナルの証明において、チューリングマシンを導入することでアルゴリズムの概念を形式化しました。しかし、この結果はチューリングマシンに特有のものではなく、マルコフアルゴリズム、ラムダ計算、ポストシステム、レジスタマシン、タグシステムなど、チューリングマシンと同等の計算能力を持つ他のあらゆる計算モデルにも同様に適用されます。

重要なのは、形式化によって、アルゴリズムが操作可能なデータ型へのアルゴリズムの直接的なマッピングが可能になることです。例えば、形式化によってアルゴリズムが文字列に対する関数を定義できる場合（チューリングマシンなど）、これらのアルゴリズムを文字列にマッピングする必要があります。また、形式化によってアルゴリズムが自然数に対する関数を定義できる場合（計算可能な関数など）、アルゴリズムを自然数にマッピングする必要があります。文字列へのマッピングは通常最も簡単ですが、n文字のアルファベット上の文字列は、 n進数体系の数値として解釈することで数値にマッピングすることもできます。

決定不能な問題は数多く存在する。停止問題のチューリング次数に等しいチューリング次数を持つ集合はすべて、そのような定式化である。停止問題の他に、そのような集合の例としては以下のようなものがある。

• { i | プログラムi は入力 0 で実行すると最終的に停止する}
• { i | プログラムiを入力xで実行すると最終的に停止するような入力xが存在する}。

クリストファー・ストラッチーは、停止問題が解けないことを背理法で証明した。 ^{[ 32 ] [ 33 ]}証明は次のように進む。サブルーチンf が（入力なしで実行されたときに）停止する場合は true を返し、そうでない場合は false を返す、全計算可能な関数halts(f)が存在すると仮定する。ここで、次のサブルーチンを考える。

def g () -> None : if halts ( g ): loop_forever ()

halts(g)は、haltsが全計算関数であると想定されていたため、必ずtrueまたはfalseを返します。halts ( g)がtrueを返すと、gはloop_foreverを呼び出し、決して停止しないため、矛盾が生じます。halts (g)がfalseを返すと、gはloop_foreverを呼び出さないため停止します。これもまた矛盾です。全体として、gはhaltsがgに期待する動作とは正反対の動作をするため、halts(g)はgが停止するかどうかと矛盾しない真偽値を返すことができません。したがって、 haltsが全計算関数であるという当初の想定は誤りであるに違いありません。

上記の概念は証明の一般的な方法を示していますが、計算可能な関数halts はサブルーチンを直接引数として受け取るのではなく、プログラムのソースコードを受け取ります。さらに、gの定義は自己参照的です。厳密な証明ではこれらの問題に対処します。全体的な目標は、任意のプログラムi が任意の入力xに対して停止するかどうかを決定する完全な計算可能な関数が存在しないことを示すことです。つまり、次の関数h (「halts」用) は計算可能ではありません。^{[ 34 ]}

${\displaystyle h(i,x)={\begin{cases}1&{\text{プログラム }}i{\text{が入力 }}x で停止する場合},\\0&{\text{それ以外の場合}}}\end{cases}}}$

ここでプログラム i は、固定されたチューリング完全な計算モデルのすべてのプログラムを列挙したリストにおけるi番目のプログラムを指します。

証明は、2 つの引数を持つ全計算可能関数が要求される関数hにはなり得ないことを直接的に証明することによって進められる。概念の概略と同様に、任意の全計算可能二項関数fが与えられた場合、次の部分関数gも何らかのプログラムeによって計算可能である。

${\displaystyle g(i)={\begin{cases}0&{\text{if }}f(i,i)=0,\\{\text{undefined}}&{\text{otherwise.}}\end{cases}}}$

gが計算可能であることの検証は、以下の構成要素（またはそれらに相当するもの）に基づいています。

• 計算可能なサブプログラム（ fを計算するプログラムはプログラムeのサブプログラムである）、
• 値の重複（プログラムeは、 gの入力iからfの入力i、iを計算する）、
• 条件分岐（プログラムeは、 f ( i , i )の値に応じて2つの結果から選択する）、
• 定義された結果を生成しない（例えば、無限ループするなど）、
• 0の値を返します。

eの以下の擬似コードは、 gを計算する簡単な方法を示しています。

手順e ( i ) : f ( i , i ) == 0の場合、0を返す。それ以外の場合は、無限ループする。

gは部分的に計算可能であるため、計算モデルがチューリング完全であるという仮定により、gを計算するプログラムeが存在するはずです。このプログラムは、停止関数hが定義されているすべてのプログラムのうちの 1 つです。証明の次のステップでは、h ( e , e ) がf ( e , e )と同じ値にならないことを示します。

gの定義から、以下の2つのケースのうち、いずれか1つが必ず成り立つことがわかる。

• f ( e , e ) = 0 なのでg ( e ) = 0 となります。この場合、プログラムeは入力eで停止するので、h ( e , e ) = 1 となります。
• f ( e , e ) ≠ 0 なので、g ( e ) は未定義です。この場合、プログラムe は入力eで停止しないので、h ( e , e ) = 0 となります。

いずれの場合も、f はhと同じ関数にはなり得ません。fは2 つの引数を持つ任意の全計算可能関数であったため、そのような関数はすべてhと異なる必要があります。

この証明はカントールの対角線論法に類似しています。上の表に示すように、各自然数に対応する 1 列と 1 行を持つ 2 次元配列を視覚化できます。f ( i , j )の値は、列i、行jに配置されます。fは全計算可能関数であると仮定されているため、配列の任意の要素はfを使用して計算できます。関数gの構成は、この配列の主対角線を使用して視覚化できます。配列の位置 ( i , i ) に 0 がある場合、g ( i ) は 0 です。そうでない場合、g ( i ) は未定義です。矛盾は、配列の列eがg自体に対応するという事実から生じます。ここで、f が停止関数hであったと仮定します。g ( e )が定義されている場合（この場合はg ( e )=0）、プログラムeは入力eで停止するため、f ( e,e )=1となります。しかし、g ( e )=0となるのはf ( e,e )=0の場合のみであり、 f ( e,e )=1と矛盾します。同様に、 g ( e )が定義されていない場合、プログラムeは入力eで停止しないため、f ( e,e )=0となり、gの構成の下ではg ( e )=0となります。これはg ( e )が定義されていないという仮定と矛盾します。どちらの場合も矛盾が生じます。したがって、任意の計算可能な関数fは停止関数hにはなり得ません。

チューリングの証明は、アルゴリズムが停止するかどうかを判定する機械的で一般的な方法（つまり、チューリングマシンや、それと同等の計算モデルにおけるプログラム）は存在しないことを示している。しかし、停止問題の個々の事例には明確な答えがあり、それは実際に計算可能かどうかは別問題である。特定のアルゴリズムと入力が与えられれば、停止するかしないかを示すことができる場合が多く、実際、コンピュータ科学者は正当性証明の一部としてまさにそれを行っている。証明を構築するために自動的に使用できるヒューリスティックがいくつかあり、それらは典型的なプログラムに対してしばしば成功する。この研究分野は、自動停止解析として知られている。

停止問題ヒューリスティックの理論的性能、特に再帰アルゴリズムによって正しく分類できる特定のサイズのプログラムの割合については、いくつかの結果が確立されている。これらの結果は、割合が計算不可能であり、「サイズ」を決定するために使用されるプログラムエンコーディングの選択に大きく依存するため、正確な数値を与えるものではない。たとえば、状態数によってプログラムを分類し、プログラムがテープの左端を超えた場合に（停止せずに）エラーとなる特定の「チューリング半無限テープ」計算モデルを使用することを考える。${\displaystyle \lim _{n\to \infty }P(x\,{\text{停止は決定可能}}\mid x\,{\text{は}}\,n\,{\text{状態を持つ}})=1}$プログラムについて${\displaystyle x}$状態の数によって均等に選択される。しかし、この結果は、これらの決定可能なプログラムは単にテープから外れたものにすぎず、ヒューリスティックは単にエラーによる停止がないと予測することであるため、ある意味で「自明」である。したがって、一見無関係な詳細、すなわちエラーのあるプログラムの扱いが、プログラムの割合を決定する決定的な要因となる可能性がある。^{[ 36 ]}

これらの問題を回避するために、プログラムの「サイズ」に関するいくつかの制限された概念が開発されてきた。密なゲーデル番号付けは、各計算可能な関数が 1 から n までのインデックスの各シーケンスで正の分数で出現するようにプログラムに番号を割り当てる。つまり、ゲーデル化 φ は、すべての に対して が成り立つ場合に限り密である。${\displaystyle i}$存在する${\displaystyle c>0}$そのため${\displaystyle \liminf _{n\to \infty }\#\{j\in \mathbb {N} :0\leq j<n,\phi _{i}=\phi _{j}\}/n\geq c}$例えば、インデックスを割り当てる番号付け$2n$非自明なプログラムおよび他のすべてのインデックスに対して、エラー状態は密ではありませんが、構文的に正しいBrainfuckプログラムの密なゲーデル番号付けが存在します。^{[ 37 ]}密なゲーデル番号付けは、他の任意のゲーデル番号付けに対して、最適であると言われます。${\displaystyle \alpha }$1対1の全再帰関数が存在する${\displaystyle f}$そして一定の${\displaystyle c}$すべての${\displaystyle i}$、$\displaystyle \alpha _{i}=\phi _{f(i)}}$そして${\displaystyle f(i)\leq ci}$この条件により、すべてのプログラムのインデックスが他のどのゲーデル番号付けにおけるインデックスよりも大幅に大きくならないことが保証されます。最適なゲーデル番号付けは、ユニバーサルチューリングマシンの入力に番号を付けることによって構築されます。^{[ 38 ]}サイズの3つ目の概念は、バイナリ文字列上で動作するユニバーサルマシンを使用し、入力プログラムを記述するために必要な文字列の長さを測定します。ユニバーサルマシンUは、他のすべてのマシンVに対して、以下の条件を満たす全計算可能関数hが存在するマシンです。${\displaystyle V(x)=U(h(x))}$最適マシンとは、コルモゴロフ複雑性不変性限界を達成するユニバーサルマシンである。すなわち、任意のマシンVに対して、あるcが存在し、すべての出力xに対して、長さnのVプログラムが出力xである場合、最大で長さ n のUプログラムが存在する。${\displaystyle n+c}$xを出力します。^{[ 39 ]}

我々は部分計算可能な関数（アルゴリズム）を考察する${\displaystyle A}$.各${\displaystyle n}$分数を考慮する${\displaystyle \epsilon _{n}(A)}$サイズメトリックのすべてのプログラムにおけるエラーの最大${\displaystyle n}$各プログラムを数える${\displaystyle x}$そのために${\displaystyle A}$終了に失敗し、「わからない」という回答を生成するか、間違った回答を生成する、つまり${\displaystyle x}$停止して${\displaystyle A(x)}$出力DOES_NOT_HALT、または${\displaystyle x}$停止せず、${\displaystyle A(x)}$出力HALTS。密なゲーデル化と最適マシンについては、その動作は次のように記述できます。^{[ 37 ] [ 39 ]}

• すべてのアルゴリズムについて${\displaystyle A}$、${\displaystyle \liminf _{n\to \infty }\epsilon _{n}(A)>0}$つまり、どんなアルゴリズムでも、問題の規模が極めて大きくなっても、最小のエラー率は必ずプラスの値をとるということである。
• 存在する${\displaystyle \epsilon >0}$すべてのアルゴリズムに対して${\displaystyle A}$、${\displaystyle \limsup _{n\to \infty }\epsilon _{n}(A)\geq \epsilon }$つまり、問題の規模が際限なく大きくなっても、どんなアルゴリズムも、ある一定のエラー率よりも頻繁に悪い結果を出すような、正のエラー率が存在するということである。
• $\displaystyle \inf _{A}\liminf _{n\to \infty }\epsilon _{n}(A)=0}$つまり、ある特定の数列のサイズが増加するにつれて、エラー率が任意にゼロに近づくようなアルゴリズムのシーケンスが存在する。しかし、この結果では、誤った答えを生成するアルゴリズムのシーケンスも許容される。
• 定義されていない可能性はあるが、決して間違った答えを生成しない「正直な」アルゴリズムのみを考慮すると、指標によっては、$\displaystyle \inf _{A\,{\textrm {honest}}}\liminf _{n\to \infty }\epsilon _{n}(A)}$0 の場合もあれば、そうでない場合もある。特に、左全汎用機械の場合は 0 だが、実質的に最適な機械の場合は 0 より大きい。^{[ 39 ]}

これらの境界の複雑な性質は、振動的な挙動によるものです。${\displaystyle \epsilon _{n}(A)}$まれに発生する新しい種類のプログラムが任意に大きな「ブロック」で出現し、繰り返しの割合が絶えず増加している。新しい種類のブロックを完全に含めると、エラー率は少なくとも${\displaystyle \epsilon }$しかし、ブロック間では、正しく分類された繰り返しの割合は任意に高くなる可能性があります。特に、最初の N 個の入力を単純に記憶し、それらの同等物を認識する「集計」ヒューリスティックを使用すると、任意に低いエラー率を無限に達成できます。^{[ 37 ]}

ゲーデルの不完全性定理によって提起される概念は、停止問題によって提起される概念と非常によく似ており、証明もかなり似ています。実際、第一不完全性定理の弱い形式は、停止問題の決定不能性から容易に導かれる帰結です。この弱い形式は、完全かつ健全な自然数の有効な公理化は不可能であると主張する点で、不完全性定理の標準的な記述とは異なります。「健全」の部分が弱化の理由です。つまり、問題となっている公理系は、自然数に関する真の命題のみを証明する必要があるということです。健全性は一貫性を意味するため、この弱い形式は強い形式の系と見なすことができます。ゲーデルの第一不完全性定理の標準的な記述は、命題の真偽値には全く関心がなく、数学的証明によってそれを見つけることが可能かどうかという問題のみに関心があることに注意することが重要です。

定理の弱い形式は、停止問題の決定不能性から次のように証明できます。^{[ 40 ]}自然数に関するすべての真の1階論理ステートメントの健全（したがって一貫性のある）かつ完全な有効な公理化があると仮定します。すると、これらのステートメントをすべて列挙するアルゴリズムを構築できます。これは、自然数nが与えられたときに、自然数に関する真の1階論理ステートメントを計算するアルゴリズムN ( n ) が存在し、すべての真のステートメントに対して、 N ( n ) がそのステートメントを生成するようなnが少なくとも 1 つ存在することを意味します。ここで、表現aを持つアルゴリズムが入力iで停止するかどうかを決定したいとします。このステートメントは、 H ( a , i )のような1階論理ステートメントで表現できることがわかっています。公理化が完全であることから、 N ( n ) = H ( a , i )となるnが存在するか、 N ( n ′ ) = ¬H ( a , i )となるn ′が存在するかのいずれかであることがわかります。したがって、H ( a , i )またはその否定が見つかるまですべてのnについて反復すると、必ず停止し、さらに、その結​​果得られる答えは（健全性により）真となります。これは、停止問題を判定するアルゴリズムが得られることを意味します。このようなアルゴリズムは存在しないことがわかっているので、自然数に関するすべての真の一階述語論理の命題について、健全かつ完全な有効な公理化が存在するという仮定は偽でなければなりません。

普遍停止問題（再帰理論では全体性とも呼ばれる）は、与えられたコンピュータプログラムがすべての入力に対して停止するかどうかを判定する問題である（全体性という名前は、計算された関数が全体であるかどうかという同等の質問に由来する）。この問題は、停止問題と同様に決定不能であるだけでなく、非常に決定不能である。算術階層の観点から言えば、$\displaystyle \Pi _{2}^{0}}$-完了。^{[ 42 ]}

これは特に、停止問題に対するオラクルを用いても決定できないことを意味する。

入力によっては停止問題に正しい答えを返すプログラムが多数存在するが、他の入力では答えを全く返さないものもある。しかし、「プログラムpが与えられたとき、それは部分停止ソルバーであるか」（ここで説明した意味で）という問題は、停止問題と少なくとも同程度に難しい。これを確認するには、PHSR（「部分停止ソルバー認識器」）というアルゴリズムが存在すると仮定する。すると、次のように停止問題を解決するために使用できる。入力プログラムx がyで停止するかどうかをテストするには、入力 ( x , y )でtrueを報告し、他のすべての入力で発散するプログラムpを構築する。次に、PHSR を使用してp をテストする。

上記の議論は停止問題をPHS認識に還元したものであり、同様に、すべての入力で停止するなどのより困難な問題も還元できるため、PHS認識は決定不能であるだけでなく、算術階層の上位に位置することを示唆している。具体的には$\displaystyle \Pi _{2}^{0}}$-完了。

損失のあるチューリングマシンとは、テープの一部が非決定的に消失する可能性があるチューリングマシンのことである。損失のあるチューリングマシンでは停止問題は決定可能であるが、非原始的な再帰性を持つ。^{[ 43 ]}

停止問題に関するオラクルを備えた機械は、特定のチューリングマシンが特定の入力に対して停止するかどうかを判定できるが、一般に、自分と同等の機械が停止するかどうかを判定することはできない。