創造的で生産的なセット

計算可能性理論において、生産的集合と創造的集合は、数理論理学において重要な応用を持つ自然数の集合の一種である。これらは、Soare (1987)やRogers (1987)などの数理論理学の教科書における標準的なトピックである。

この記事の残りの部分では、以下のことを前提とします。$\displaystyle \varphi _{i}}$は計算可能な関数の許容可能な番号付けであり、W _{i は}再帰的に列挙可能な集合の対応する番号付けである。

自然数の集合Aは、全再帰的（計算可能な）関数が存在する場合に生産的であると呼ばれる。${\displaystyle f}$すべてに対して${\displaystyle i\in \mathbb {N} }$、 もし${\displaystyle W_{i}\subseteq A}$それから${\displaystyle f(i)\in A\setminus W_{i}.}$機能${\displaystyle f}$これは生産関数と呼ばれます${\displaystyle A.}$

自然数の集合Aは、 Aが再帰的に列挙可能で、その補集合が${\displaystyle \mathbb {N} \setminus A}$は生産的です。ただし、以下に示すように、すべての生産的な集合が再帰的に列挙可能な補集合を持つわけではありません。

典型的なクリエイティブ集団は${\displaystyle K=\{i\mid i\in W_{i}\}}$停止問題を表す集合。その補集合${\displaystyle {\bar {K}}=\{i\mid i\not \in W_{i}\}}$生産関数f ( i ) = i (恒等関数) で生産的です。

これを確認するには、生産関数の定義を適用し、別々に以下を示します。${\displaystyle i\in {\bar {K}}}$そして${\displaystyle i\not \in W_{i}}$:

• ${\displaystyle i\in {\bar {K}}}$： 仮定する${\displaystyle i\in K}$、 それから${\displaystyle i\in W_{i}}$では、${\displaystyle W_{i}\subseteq {\bar {K}}}$我々は持っています${\displaystyle i\in {\bar {K}}}$これは矛盾を生む。${\displaystyle i\in {\bar {K}}}$。
• ${\displaystyle i\not \in W_{i}}$: 実際もし${\displaystyle i\in W_{i}}$そうすれば、${\displaystyle i\in K}$しかし、前の項目でその逆を実証しました。${\displaystyle i\not \in W_{i}}$。

生産的集合Aは再帰的に列挙可能ではありません。なぜなら、A が再帰的集合W _iに含まれるすべての数を含む場合、A は他の数も含むことになり、さらに、インデックスiからそのような数の例を生成する有効な手順が存在するからです。同様に、創造的集合は決定可能ではありません。なぜなら、決定可能であれば、その補集合である生産的集合が再帰的に列挙可能になることを意味するからです。

任意の生産的集合は、単射かつ全射な生産関数を持つ。

Myhill (1955) による以下の定理は、ある意味で全ての創造的集合が${\displaystyle K}$そしてすべての生産セットは次のようになります${\displaystyle {\bar {K}}}$[ ^{1 ]​}

定理。Pを自然数の集合とする。以下の式は同値である。

• Pは生産的である。
• ${\displaystyle {\bar {K}}}$Pに1 還元可能である。
• ${\displaystyle {\bar {K}}}$はPにm 還元可能である。

定理。Cを自然数の集合とする。以下の式は同値である 。

• Cは創造力がある。
• Cは1完全である
• CはKと再帰的に同型である。つまり、自然数上の全計算可能な全単射fが存在し、 f ( C ) = Kとなる。

有効な公理系における証明可能な文の集合は、常に再帰的に列挙可能な集合である。システムが一階算術のように十分に複雑であれば、システム内の真の文のゲーデル数の集合Tは生産的な集合となる。これは、 Wが真の文の再帰的に列挙可能な集合であるときはいつでも、 Wに含まれない真の文が少なくとも 1 つ存在することを意味する。再帰的に列挙可能な集合は生産的ではないため、これを利用してゲーデルの第一不完全性定理を厳密に証明することができる。集合Tの補集合は再帰的に列挙可能ではないため、T は補集合が創造的ではない生産的な集合の例となる。

ポストの画期的な論文（1944年）は、彼が創造的集合と呼ぶ概念を定義した。繰り返しますが、集合は${\displaystyle K}$上記で参照され、関数の定義域として定義されている。${\displaystyle d(x)=[[x]](x)+1}$列挙されたすべての 1 位の計算可能な部分関数の対角線を取り、それに 1 を加えることは、創造的集合の一例である。^{[ 2 ]}ポストは、創造的集合を用いてゲーデルの不完全性定理のバージョンを与えた。元々ゲーデルはある意味で「私はこの公理的理論では証明不可能である」と自由に翻訳できる文を構成していた。しかし、ゲーデルの証明は真の文の概念からではなく、むしろ一貫性のある理論の概念を使用しており、それが第2 不完全性定理につながった。ポストは不完全性のバージョンを完成させた後、次のことを付け加えた。

「このような固定された、明確に定義された数学的命題の体系であっても、数学的思考は本質的に創造的であり、今後もそうあり続けなければならないという結論は避けられない。」^{[ 2 ]}

いつものクリエイティブな人々${\displaystyle K}$対角関数を用いて定義される$d(x)$独自の歴史的発展を遂げてきた。アラン・チューリングは1936年のチューリングマシンに関する論文で、計算を行う汎用コンピュータの存在を示した。${\displaystyle \Phi }$関数。関数${\displaystyle \Phi }$は次のように定義される。 ${\displaystyle \Phi (w,x)=}$（​${\displaystyle w}$入力に対して${\displaystyle x}$）であり、任意の計算可能な部分関数が${\displaystyle f}$は${\displaystyle f(x)=\Phi (e,x)}$すべての人々のために${\displaystyle x}$どこ${\displaystyle e}$指示コード${\displaystyle f}$上記の表記法を用いて ${\displaystyle \Phi (e,x)=[[e]](x)}$、そして対角関数はごく自然に次のように現れる。${\displaystyle d(x)=[[x]](x)+1}$結局のところ、これらの考え方は、計算可能な部分関数という数学的概念は、証明も反証もできない、実質的に計算可能な部分関数の正しい形式化であるというチャーチのテーゼにつながっている。チャーチはラムダ計算、チューリングは理想化されたコンピュータ、そして後にエミール・ポストをそのアプローチに用いたが、これらはすべて同等である。

デボラ・ジョセフとポール・ヤング（1985 ）は、計算複雑性理論において多項式創造性という類似の概念を定式化し、NP完全集合の同型性に関するバーマン・ハートマニス予想に対する潜在的な反例を提供するためにそれを使用した。 

• デイビス、マーティン（1958）、『計算可能性と解不可能性』、情報処理とコンピュータシリーズ、ニューヨーク：マグロウヒル、MR 0124208 1982年にドーバー出版より復刻版が刊行された。
• エンダートン、ハーバート・B. (2010)、計算可能性理論：再帰理論入門、アカデミック・プレス、ISBN 978-0-12-384958-8。
• Joseph, Deborah ; Young, Paul (1985)、「NPにおける非多項式集合および非完全集合の証拠関数に関するいくつかの考察」、Theoretical Computer Science、39 ( 2–3 ): 225–237、doi : 10.1016/0304-3975(85)90140-9、MR 0821203 
• クリーネ、スティーブン・コール（2002）、『数理論理学』、ミネオラ、ニューヨーク：ドーバー出版、ISBN 0-486-42533-9MR 1950307​ 1967年のオリジナル版の復刻版、Wiley、MR 0216930。 
• Myhill、John (1955)、「クリエイティブ セット」、Zeitschrift für Mathematische Logik und Grundlagen der Mathematik、1 (2): 97–108、doi : 10.1002/malq.19550010205、MR 0071379 。
• ポスト、エミル・L. (1944)、「正の整数の再帰的に列挙可能な集合とその決定問題」、アメリカ数学会報、50 (5): 284–316、doi : 10.1090/S0002-9904-1944-08111-1、MR 0010514 
• ロジャース、ハートリー・ジュニア（1987）、『再帰関数と有効計算可能性の理論（第2 版）』、マサチューセッツ州ケンブリッジ：MIT Press、ISBN 0-262-68052-1MR 0886890​ 。
• Soare, Robert I. (1987), Recursively enumerable sets and degrees: A study of computable functions and computably generated sets , Perspectives in Mathematical Logic, Berlin: Springer-Verlag, ISBN 3-540-15299-7MR 0882921​ 。