ポストの問題との関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/23 09:57 UTC 版)
単純集合はエミール・ポストによってチューリング完全でなく再帰的でもない帰納的可算集合の研究の中で考案された。そのような集合が存在するかどうかはポストの問題として知られる。ポストはこの問題の解答のために2つの事を証明する必要があった。ひとつは、単純集合は空集合にチューリング還元できないということである。いまひとつは、停止問題は単純集合にチューリング還元できないということである。彼が成功したのは前者であり（これは定義より明白）、後者は多対一還元についてのみ遂げられた。 このような集合が存在することはフリードバーグとムチニクにより1950年に独立に証明された。そこでは優先法と呼ばれる手法が用いられた。彼らは単純だが停止性問題を還元できない集合の構成を与えた。
※この「ポストの問題との関係」の解説は、「単純集合」の解説の一部です。
「ポストの問題との関係」を含む「単純集合」の記事については、「単純集合」の概要を参照ください。
ウィキペディア小見出し辞書の「ポストの問題との関係」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ポストの問題との関係のページへのリンク
