優先度法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 05:44 UTC 版)
ポストの問題は優先度法という技法を用いて解決された。この技法を用いる証明は優先度論法と呼ばれる。これは第一義的には特別な性質を備えた帰納的可算集合を構成することを目的とする。やり方としては、まずその帰納的可算集合が備えるべき性質を無限個の「要件」に分解し、全ての要件を満足すれば目的の集合は自ずと所期の性質を獲得する、という形を作る。個々の要件には優先度を表す自然数を付与しておく。0 を付与された要件が最優先で、以下 1、2 …という具合である。以後、目的の集合を「段階」を踏んで構築して行く。個々の段階は、一つ以上の要件を満たすように、目的の集合に対して数を追加または削除することから成る。一つの要件を満たすと他の要件に反してしまう場合が有り得るが、その際は優先度を参照して処理方法を決定する。 これまで優先度論法を用いて再帰理論の様々な問題が解決されてきており、それらは複雑さの観点から階層状に分類されている(Soare 1987)。複雑な優先度論法はテクニカルかつ難解になりがちなので、伝統的に出来れば優先度論法は使わずに証明することが望ましいとされ、また優先度論法を用いた証明があればそれ抜きの別証明が模索されてきた。例えば Kummer は Friedberg ナンバリングの存在証明について優先度法を用いない証明を発表した（Kummer 1989, 1990）。
※この「優先度法」の解説は、「再帰理論」の解説の一部です。
「優先度法」を含む「再帰理論」の記事については、「再帰理論」の概要を参照ください。
ウィキペディア小見出し辞書の「優先度法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 優先度法のページへのリンク
