مجموعات إبداعية ومنتجة

في نظرية الحوسبة ، تُعدّ المجموعات المنتجة والمجموعات الإبداعية نوعين من مجموعات الأعداد الطبيعية التي لها تطبيقات مهمة في المنطق الرياضي . وهي موضوع أساسي في كتب المنطق الرياضي مثل كتابي سواري (1987) وروجر (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 . وبالمثل، لا يمكن لأي مجموعة إبداعية أن تكون قابلة للتقرير ، لأن هذا يعني أن مكملتها، وهي مجموعة منتجة، قابلة للتعداد التكراري.

أي مجموعة منتجة لها دالة منتجة أحادية وكاملة .

تُظهر النظريات التالية، التي وضعها مايهيل (1955)، أن جميع المجموعات الإبداعية متشابهة إلى حد ما.${\displaystyle K}$وجميع المجموعات الإنتاجية متشابهة${\displaystyle {\bar {K}}}$[ ^{1 ]​}

نظرية. ليكن P مجموعة من الأعداد الطبيعية. ما يلي متكافئ:

• P منتج.
• ${\displaystyle {\bar {K}}}$يمكن اختزالها إلى P.​
• ${\displaystyle {\bar {K}}}$يمكن اختزالها إلى P.​

نظرية. لتكن C مجموعة الأعداد الطبيعية. ما يلي متكافئ:

• ج مبدع.
• C كاملة من الدرجة 1
• C متماثلة بشكل متكرر مع K ، أي أن هناك تقابلًا حسابيًا كليًا f على الأعداد الطبيعية بحيث يكون f ( C ) = K .

مجموعة جميع الجمل القابلة للإثبات في نظام بديهي فعال هي دائمًا مجموعة قابلة للتعداد التكراري . إذا كان النظام معقدًا بدرجة مناسبة، كالحساب من الرتبة الأولى ، فإن مجموعة أعداد غودل للجمل الصحيحة في النظام (T) ستكون مجموعة منتجة، ما يعني أنه كلما كانت W مجموعة قابلة للتعداد التكراري من الجمل الصحيحة، توجد على الأقل جملة صحيحة واحدة غير موجودة في W. يمكن استخدام هذا لتقديم برهان دقيق لنظرية عدم الاكتمال الأولى لغودل ، لأنه لا توجد مجموعة قابلة للتعداد التكراري منتجة. مكمل المجموعة T لن يكون قابلًا للتعداد التكراري، وبالتالي فإن T مثال على مجموعة منتجة مكملها ليس إبداعيًا.

عرّفت الورقة البحثية الرائدة لبوست (1944) المفهوم الذي أطلق عليه اسم المجموعة الإبداعية. وبالتأكيد، فإن المجموعة${\displaystyle K}$المشار إليه أعلاه والمحدد على أنه مجال الدالة${\displaystyle d(x)=[[x]](x)+1}$إنّ جمع عناصر قطر جميع الدوال الجزئية القابلة للحساب ذات الموضع الواحد وإضافة 1 إليها يُعدّ مثالًا على مجموعة إبداعية. ^{[ 2 ]} قدّم بوست صيغةً لنظرية عدم الاكتمال لغودل باستخدام مجموعاته الإبداعية، حيث كان غودل قد صاغ في الأصل جملةً يُمكن ترجمتها بحرية على أنها "أنا غير قابل للإثبات في هذه النظرية البديهية". مع ذلك، لم يعتمد برهان غودل على مفهوم الجمل الصحيحة، بل استخدم مفهوم النظرية المتسقة، مما أدى إلى نظرية عدم الاكتمال الثانية . بعد أن أكمل بوست صيغته من نظرية عدم الاكتمال، أضاف ما يلي:

"الخلاصة لا مفر منها، وهي أنه حتى بالنسبة لمجموعة ثابتة ومحددة جيدًا من القضايا الرياضية، فإن التفكير الرياضي هو، ويجب أن يظل، إبداعيًا في جوهره." ^{[ 2 ]}

المجموعة الإبداعية المعتادة${\displaystyle K}$مُعرَّف باستخدام الدالة القطرية${\displaystyle 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 بواسطة دار نشر دوفر.
• إندرتون، هربرت ب. (2010)، نظرية الحوسبة: مقدمة في نظرية الاستدعاء الذاتي ، دار النشر الأكاديمية، رقم ISBN 978-0-12-384958-8.
• جوزيف، ديبورا ؛ يونغ، بول (1985)، "بعض الملاحظات حول دوال الشاهد للمجموعات غير متعددة الحدود وغير الكاملة في NP" ، علوم الحاسوب النظرية ، 39 ( 2-3 ): 225-237 ، doi : 10.1016/0304-3975(85)90140-9 ، MR 0821203 
• كلين، ستيفن كول (2002)، المنطق الرياضي ، مينولا، نيويورك: منشورات دوفر، رقم ISBN 0-486-42533-9MR 1950307​ إعادة طبع النسخة الأصلية لعام 1967، وايلي، MR 0216930 . 
• Myhill، John (1955)، “مجموعات إبداعية”، Zeitschrift für Mathematische Logik und Grundlagen der Mathematik ، 1 (2): 97–108 ، دوى : 10.1002/malq.19550010205 ، MR 0071379 .
• بوست، إميل ل. (1944)، "مجموعات الأعداد الصحيحة الموجبة القابلة للتعداد بشكل متكرر ومسائل القرار الخاصة بها"، نشرة الجمعية الرياضية الأمريكية ، 50 (5): 284-316 ، doi : 10.1090/S0002-9904-1944-08111-1 ، MR 0010514 
• روغرز، هارتلي الابن (1987)، نظرية الدوال التكرارية والحسابية الفعالة (الطبعة الثانية  )، كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا، رقم ISBN 0-262-68052-1، MR 0886890 .
• سواري، روبرت آي. (1987)، المجموعات والدرجات القابلة للتعداد بشكل متكرر: دراسة للدوال القابلة للحساب والمجموعات المولدة حسابيًا ، منظورات في المنطق الرياضي، برلين: سبرينغر-فيرلاغ، ISBN 3-540-15299-7، MR 0882921 .