مجموعة بسيطة

في نظرية الحوسبة ، تُسمى مجموعة جزئية من الأعداد الطبيعية بسيطة إذا كانت قابلة للعد الحسابي (ce) ومكملة لها (أي أن مكملتها لانهائية)، ولكن كل مجموعة جزئية لانهائية من مكملتها ليست قابلة للعد الحسابي. المجموعات البسيطة هي أمثلة على مجموعات قابلة للعد الحسابي ولكنها غير قابلة للحساب .

ابتكر إميل ليون بوست مفهوم المجموعات البسيطة في بحثه عن مجموعة غير كاملة تورينج. تُعرف مسألة وجود مثل هذه المجموعات بمسألة بوست . كان على بوست إثبات أمرين للوصول إلى نتيجته: أن المجموعة البسيطة A غير قابلة للحساب، وأن مسألة التوقف K لا تُختزل تورينجياً إلى A. نجح في الجزء الأول (وهو أمر بديهي بحكم التعريف)، أما بالنسبة للجزء الثاني، فقد تمكن فقط من إثبات عدم وجود اختزال متعدد-واحد .

تم التحقق من صحة فكرة بوست بواسطة فريدبيرغ وموشنيك في خمسينيات القرن الماضي باستخدام تقنية جديدة تسمى طريقة الأولوية . وقد قدما بناءً لمجموعة بسيطة (وبالتالي غير قابلة للحساب)، لكنها فشلت في حساب مشكلة التوقف. ^{[ 1 ]}

فيما يلي،${\displaystyle W_{e}}$يشير إلى قائمة موحدة قياسية لجميع مجموعات ce.

• مجموعة${\displaystyle I\subseteq \mathbb {N} }$يُطلق عليه اسم المناعة إذا${\displaystyle I}$لا نهائي، ولكن لكل فهرس${\displaystyle e}$لدينا${\displaystyle W_{e}{\text{ infinite}}\implies W_{e}\not \subseteq I}$أو بصورة مكافئة: لا توجد مجموعة جزئية لانهائية من${\displaystyle I}$هذا هو ce.
• مجموعة${\displaystyle S\subseteq \mathbb {N} }$يُطلق عليه اسم بسيط إذا كان ce ومكمله محصن.
• مجموعة${\displaystyle I\subseteq \mathbb {N} }$يُطلق عليه اسم "محصن بشكل فعال" إذا${\displaystyle I}$هي لانهائية، ولكن توجد دالة تكرارية${\displaystyle f}$بحيث يكون لكل مؤشر${\displaystyle e}$لدينا ذلك${\displaystyle W_{e}\subseteq I\implies \#(W_{e})<f(e)}$.
• مجموعة${\displaystyle S\subseteq \mathbb {N} }$تُسمى المجموعة بسيطة فعلياً إذا كانت موجبة الشحنة ومكملتها محصنة فعلياً. كل مجموعة بسيطة فعلياً هي مجموعة بسيطة وكاملة تورينج.
• مجموعة${\displaystyle I\subseteq \mathbb {N} }$يُطلق عليه اسم فرط المناعة إذا${\displaystyle I}$لا نهائي، لكن${\displaystyle p_{I}}$لا تخضع للهيمنة الحسابية، حيث${\displaystyle p_{I}}$هي قائمة أعضاء${\displaystyle I}$بالترتيب. ^{[ 2 ]}
• مجموعة${\displaystyle S\subseteq \mathbb {N} }$يُطلق عليه اسم "مفرط البساطة" إذا كان بسيطًا وكان مكمله مفرط المناعة. ^{[ 3 ]}

• سواري، روبرت آي. (1987). المجموعات والدرجات القابلة للتعداد التكراري. دراسة للدوال القابلة للحساب والمجموعات المولدة حسابيًا . منظورات في المنطق الرياضي. برلين: سبرينغر-فيرلاغ . ISBN 3-540-15299-7. Zbl 0667.03030 . 
• أوديفردي، بييرجيورجيو (1988). نظرية الاستدعاء الذاتي الكلاسيكية. نظرية الدوال ومجموعات الأعداد الطبيعية . دراسات في المنطق وأسس الرياضيات. المجلد  125. أمستردام: نورث هولاند. ISBN 0-444-87295-7. Zbl 0661.03029 . 
• نيس، أندريه (2009). الحوسبة والعشوائية . أدلة أكسفورد المنطقية. المجلد  51. أكسفورد: مطبعة جامعة أكسفورد. ISBN 978-0-19-923076-1. Zbl 1169.03034 .