死亡率（計算可能性理論）

計算可能性理論では、死亡問題は停止問題に関連する決定問題です。チューリング マシンの場合、停止問題は次のように記述できます。 チューリングマシンと単語が与えられた場合、指定された単語でマシンを実行したときに停止するかどうかを決定します。

対照的に、チューリング マシンの死亡率問題は、任意の構成から始まるマシンのすべての実行が停止するかどうかを尋ねます。

上記のステートメントでは、構成はマシンの状態 (必ずしも初期状態ではない)、テープ位置、およびテープの内容の両方を指定します。通常、開始構成ではテープ上の有限個以外のすべてのセルが空白であると想定されますが、死亡率問題では、テープには任意の内容 (無限個の空白でないシンボルが書き込まれるなど) が含まれる可能性があります。

フィリップ・K・フーパーは1966年に死亡率問題が決定不可能であることを証明した^[1]。これは両方向に無限のテープを持つマシンと半無限のテープを持つマシンの両方に当てはまります。この結果は、よく知られている全関数問題（与えられたマシンはすべての入力に対して停止するか？）から直接導かれるものではないことに注意してください。後者の問題は有効な計算（初期設定から始まる）にのみ関係するからです。

有限構成のみを考慮した変種も決定不能であり、ハーマン^{[2]によって証明され、彼はこれを「一様停止問題」と呼んでいる。彼は、問題が決定不能であるだけでなく、}完全であることを示している。 ${\displaystyle \Pi _{2}^{0}}$

この問題は、「構成」と「遷移」の概念があるあらゆる計算モデルに自然に言い換えることができます。モデルのメンバーは、遷移の無限の連鎖につながる構成がない場合、死亡することになります。死亡問題は、次の場合に決定不可能であることが証明されています。

• セミThueシステムとマルコフアルゴリズム[ ^1]
• カウンターマシン^[3]
• またはまたは上の力学系（に対して）であり、遷移関数は区分的に線形である^{[4] [5]}（ここで、任意の点、例えば原点が停止状態として選択される）。${\displaystyle {\mathbb {R} }^{n}}$${\displaystyle {\mathbb {Q} }^{n}}$${\displaystyle {\mathbb {Z} }^{n}}$${\displaystyle n\geq 2}$