|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 単 ： [ひとえ, たん] 【名詞】 1. one layer 2. single ・ 単純 ： [たんじゅん] 1. (adj-na,n) simplicity ・ 純 ： [じゅん] 1. (adj-na,n) pure 2. innocent 3. chaste ・ 集 ： [しゅう] 【名詞】 1. collection ・ 集合 ： [しゅうごう] 1. (n,vs) (1) gathering 2. assembly 3. meeting 4. (2) (gen) (math) set ・ 合 ： [ごう] 【名詞】 1. go (approx. 0.18l or 0.33m)
単純集合（たんじゅんしゅうごう、英：simple set）とは、数理論理学における再帰理論で扱われるある種の集合。帰納的可算だが帰納的ではない集合の例。 == ポストの問題との関係 == 単純集合はエミール・ポストによってチューリング完全でなく再帰的でもない帰納的可算集合の研究の中で考案された。そのような集合が存在するかどうかはポストの問題として知られる。ポストはこの問題の解答のために2つの事を証明する必要があった。ひとつは、単純集合は空集合にチューリング還元できないということである。いまひとつは、停止問題は単純集合にチューリング還元できないということである。彼が成功したのは前者であり（これは定義より明白）、後者は多対一還元についてのみ遂げられた。 このような集合が存在することはフリードバーグとムチニクにより1950年に独立に証明された。そこでは優先法と呼ばれる手法が用いられた。彼らは単純だが停止性問題を還元できない集合の構成を与えた。〔Nies (2009) p.35〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「単純集合」の詳細全文を読む スポンサード リンク
|