غير قابلة للفصل حسابيًا

في نظرية الحوسبة ، يُطلق على مجموعتين منفصلتين من الأعداد الطبيعية اسم "غير قابلتين للفصل حسابيًا" أو "غير قابلتين للفصل تكراريًا " إذا تعذر "فصلهما" باستخدام مجموعة قابلة للحوسبة . ^{[ 1 ]} تظهر هذه المجموعات في دراسة نظرية الحوسبة نفسها، لا سيما فيما يتعلق بـ${\displaystyle \Pi _{1}^{0}}$الفئات . تظهر المجموعات غير القابلة للفصل حسابيًا أيضًا في دراسة نظرية عدم اكتمال غودل .

الأعداد الطبيعية هي المجموعة${\displaystyle \mathbb {N} =\{0,1,2,\dots \}}$. بالنظر إلى المجموعات الجزئية المنفصلة${\displaystyle A}$و${\displaystyle B}$ل${\displaystyle \mathbb {N} }$، مجموعة فاصلة${\displaystyle C}$هي مجموعة فرعية من${\displaystyle \mathbb {N} }$بحيث ${\displaystyle A\subseteq C}$و${\displaystyle B\cap C=\emptyset }$(أو ما يعادل ذلك، ${\displaystyle A\subseteq C}$و${\displaystyle B\subseteq C'}$، أين${\displaystyle C'=\mathbb {N} \setminus C}$يشير إلى مكمل لـ${\displaystyle C}$). على سبيل المثال،${\displaystyle A}$هي نفسها مجموعة فاصلة للزوج، كما هو الحال${\displaystyle B'}$.

إذا كان زوج من المجموعات المنفصلة${\displaystyle A}$و${\displaystyle B}$إذا لم يكن للمجموعة مجموعة فصل قابلة للحساب ، فإن المجموعتين تكونان غير قابلتين للفصل حسابيًا .

لو${\displaystyle A}$إذا كانت مجموعة غير قابلة للحساب،${\displaystyle A}$ومتممتها غير قابلة للفصل حسابيًا. ومع ذلك، هناك العديد من الأمثلة على المجموعات${\displaystyle A}$و${\displaystyle B}$وهي منفصلة، ​​وغير متكاملة، وغير قابلة للفصل حسابيًا. علاوة على ذلك، من الممكن لـ${\displaystyle A}$و${\displaystyle B}$أن تكون غير قابلة للفصل حسابيًا، ومنفصلة، ​​وقابلة للتعداد حسابيًا .

• يترك${\displaystyle \varphi }$ليكن الفهرس القياسي للدوال القابلة للحساب الجزئي . عندئذٍ تكون المجموعات${\displaystyle A=\{e:\varphi _{e}(0)=0\}}$و${\displaystyle B=\{e:\varphi _{e}(0)=1\}}$لا يمكن فصلها حسابيًا ( ويليام غاسارش 1998، ص  1047).
• يترك${\displaystyle \#}$ليكن ترقيم غودل القياسي لصيغ حساب بيانو . ثم المجموعة${\displaystyle A=\{\#(\psi ):PA\vdash \psi \}}$من الصيغ القابلة للإثبات والمجموعة${\displaystyle B=\{\#(\psi ):PA\vdash \lnot \psi \}}$لا يمكن فصل مجموعات الصيغ القابلة للدحض حسابيًا. وينطبق عدم قابلية فصل مجموعات الصيغ القابلة للإثبات والقابلة للدحض على العديد من النظريات الرسمية الأخرى للحساب (سموليان 1958).

• سينزر، دوغلاس (1999)، "فئات Π ⁰ ₁ في نظرية الحوسبة"، دليل نظرية الحوسبة ، دراسات في المنطق وأسس الرياضيات، المجلد  140، أمستردام: نورث هولاند، الصفحات 37-85 ، doi : 10.1016/S0049-237X(99)80018-4 ، MR 1720779  
• غاسارش، ويليام (1998)، "مسحٌ للتوافقية التكرارية"، دليل الرياضيات التكرارية، المجلد 2 ، دراسات في المنطق وأسس الرياضيات، المجلد  139، أمستردام: نورث هولاند، الصفحات 1041-1176 ، doi : 10.1016/S0049-237X(98)80049-9 ، MR 1673598  
• مونك، ج. دونالد (1976)، المنطق الرياضي ، نصوص الدراسات العليا في الرياضيات، برلين، نيويورك: سبرينغر-فيرلاغ ، ISBN 978-0-387-90170-1
• Smullyan، Raymond M. (1958)، “Undecidability and recursive inseparability”، Zeitschrift für Mathematische Logik und Grundlagen der Mathematik ، 4 ( 7– 11): 143– 147، دوى : 10.1002 / malq.19580040705 ، ISSN 0044-3050 ، م.ر 0099293