مجموعة قابلة للحساب والتعداد

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

• توجد خوارزمية بحيث تكون مجموعة أرقام الإدخال التي تتوقف عندها الخوارزمية هي S بالضبط .

أو بعبارة أخرى،

• توجد خوارزمية تُحصي عناصر المجموعة S. أي أن مُخرجاتها عبارة عن قائمة بجميع عناصر S : s1 ، s2 _، s3 ، ... . إذا كانت S _{لانهائية ، فستستمر هذه الخوارزمية في العمل إلى ما لا نهاية، ولكن سيتم إرجاع كل عنصر من عناصر S بعد فترة زمنية محددة} . تجدر الإشارة إلى أنه ليس من الضروري ترتيب هذه العناصر بطريقة معينة، كأن يكون الترتيب من الأصغر إلى الأكبر.

يُفسر الشرط الأول سبب استخدام مصطلح "شبه قابل للتقرير" أحيانًا. بتعبير أدق، إذا كان العدد موجودًا في المجموعة، يُمكن تحديد ذلك بتشغيل الخوارزمية، أما إذا لم يكن العدد موجودًا، فقد تستمر الخوارزمية في العمل إلى ما لا نهاية دون الحصول على أي معلومات. تُسمى المجموعة "القابلة للتقرير تمامًا" مجموعة قابلة للحساب . يُفسر الشرط الثاني سبب استخدام مصطلح "قابلة للتعداد الحسابي ". غالبًا ما تُستخدم الاختصارات "ce" و "re" ، حتى في المطبوعات، بدلًا من العبارة الكاملة.

في نظرية التعقيد الحسابي ، تُسمى فئة التعقيد التي تحتوي على جميع المجموعات القابلة للتعداد الحسابي RE . وفي نظرية الاستدعاء الذاتي، يُرمز إلى شبكة مجموعات ce تحت التضمين بـ${\displaystyle {\mathcal {E}}}$.

تُسمى مجموعة S من الأعداد الطبيعية قابلة للحساب إذا كانت هناك دالة قابلة للحساب جزئيًا يكون مجالها هو S بالضبط ، مما يعني أن الدالة معرفة إذا وفقط إذا كان مدخلها عنصرًا من S.

فيما يلي جميع الخصائص المتكافئة لمجموعة S من الأعداد الطبيعية:

شبه قابلية الحسم :

• المجموعة S قابلة للحساب. أي أن S هي مجال (مدى مشترك) دالة قابلة للحساب جزئيًا.
• المجموعة S هي${\displaystyle \Sigma _{1}^{0}}$(في إشارة إلى التسلسل الهرمي الحسابي ). ^{[ 1 ]}
• توجد دالة قابلة للحساب جزئياً f بحيث:$${\displaystyle f(x)={\begin{cases}1&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ x\notin S\end{cases}}}$$

قابلية التعداد :

• المجموعة S هي مدى دالة قابلة للحساب جزئيًا.
• المجموعة S هي مدى دالة قابلة للحساب كليًا، أو فارغة. إذا كانت S لانهائية، فيمكن اختيار الدالة لتكون أحادية .
• المجموعة S هي مدى دالة تكرارية أولية أو فارغة. حتى لو كانت S لانهائية، فقد يكون تكرار القيم ضروريًا في هذه الحالة.

ديوفانتين :

• يوجد متعدد حدود p بمعاملات ومتغيرات صحيحة${\displaystyle x,a_{1},a_{2},a_{3},\dots ,a_{9}}$تتراوح بين الأعداد الطبيعية بحيث$${\displaystyle x\in S\Leftrightarrow \exists a_{1},a_{2},a_{3},\dots ,a_{9}\ (p(x,a_{1},a_{2},a_{3},\dots ,a_{9})=0).}$$(عدد المتغيرات المقيدة في هذا التعريف هو الأكثر شهرة حتى الآن؛ قد يكون من الممكن استخدام عدد أقل لتعريف جميع المجموعات الديوفانتية.)
• يوجد متعدد حدود من الأعداد الصحيحة إلى الأعداد الصحيحة بحيث تحتوي المجموعة S على الأعداد غير السالبة بالضبط في مداها.

يمكن الحصول على تكافؤ شبه قابلية الحسم وقابلية التعداد من خلال تقنية التعشيق .

على الرغم من أن التوصيفات الديوفانتية لمجموعة قابلة للتعداد الحسابي ليست مباشرة أو بديهية كالتعريفات الأولى، فقد توصل إليها يوري ماتياسيفيتش كجزء من الحل السلبي لمسألة هيلبرت العاشرة . تسبق المجموعات الديوفانتية نظرية الاستدعاء الذاتي، وبالتالي فهي تاريخيًا أول طريقة لوصف هذه المجموعات (مع أن هذه المكافئة لم تُلاحظ إلا بعد أكثر من ثلاثة عقود من ظهور المجموعات القابلة للتعداد الحسابي). ^{[ 2 ]}

• كل مجموعة قابلة للحساب قابلة للتعداد الحسابي، ولكن ليس صحيحًا أن كل مجموعة قابلة للتعداد الحسابي قابلة للحساب. بالنسبة للمجموعات القابلة للحساب، يجب على الخوارزمية أيضًا تحديد ما إذا كان أحد المدخلات غير موجود في المجموعة - وهذا غير مطلوب بالنسبة للمجموعات القابلة للتعداد الحسابي.
• اللغة القابلة للتعداد بشكل متكرر هي مجموعة فرعية قابلة للتعداد حسابيًا من لغة رسمية .
• إن مجموعة جميع الجمل القابلة للإثبات في نظام بديهي معروض بشكل فعال هي مجموعة قابلة للحساب والتعداد.
• تنص نظرية ماتياسيفيتش على أن كل مجموعة قابلة للحساب هي مجموعة ديوفانتين (والعكس صحيح بشكل بديهي).
• المجموعات البسيطة قابلة للتعداد الحسابي ولكنها غير قابلة للحساب.
• المجموعات الإبداعية قابلة للتعداد الحسابي ولكنها غير قابلة للحساب.
• أي مجموعة منتجة لا يمكن تعدادها حسابيًا.
• بالنظر إلى ترقيم غودل${\displaystyle \phi }$من الدوال القابلة للحساب، المجموعة${\displaystyle \{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}}$(أين${\displaystyle \langle i,x\rangle }$هي دالة اقتران كانتور و${\displaystyle \phi _{i}(x)\downarrow }$يشير${\displaystyle \phi _{i}(x)}$(معرّف) قابلة للحساب والتعداد (انظر الصورة لقيمة x ثابتة ). تُشفّر هذه المجموعة مشكلة التوقف لأنها تصف معلمات الإدخال التي تتوقف عندها كل آلة تورينج .
• بالنظر إلى ترقيم غودل${\displaystyle \phi }$من الدوال القابلة للحساب، المجموعة${\displaystyle \{\left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\}}$يمكن حسابها وتعدادها. هذه المجموعة ترمز إلى مشكلة تحديد قيمة دالة.
• إذا كانت لدينا دالة جزئية f من الأعداد الطبيعية إلى الأعداد الطبيعية، فإن f تكون دالة جزئية قابلة للحساب إذا وفقط إذا كان الرسم البياني لـ f ، أي مجموعة جميع الأزواج${\displaystyle \langle x,f(x)\rangle }$بحيث تكون f ( x ) معرفة، قابلة للتعداد الحسابي.

إذا كانت A و B مجموعتين قابلتين للحساب، فإن A ∩ B و A ∪ B و A × B (حيث يُقابل كل زوج مرتب من الأعداد الطبيعية عددًا طبيعيًا واحدًا باستخدام دالة اقتران كانتور ) هي مجموعات قابلة للحساب. الصورة العكسية لمجموعة قابلة للحساب تحت دالة قابلة للحساب جزئيًا هي مجموعة قابلة للحساب.

مجموعة${\displaystyle T}$يُطلق عليه اسم قابل للحساب المشترك أو co-ce إذا كان مكمله${\displaystyle \mathbb {N} \setminus T}$يمكن تعدادها حسابيًا. أو بعبارة أخرى، تكون المجموعة مشتركة إذا وفقط إذا كانت على مستوى${\displaystyle \Pi _{1}^{0}}$من التسلسل الهرمي الحسابي. يُرمز إلى فئة التعقيد للمجموعات القابلة للحساب المشترك بالرمز co-RE.

تكون المجموعة A قابلة للحساب إذا وفقط إذا كانت كل من A ومكملة A قابلة للحساب والتعداد.

بعض أزواج المجموعات القابلة للحساب قابلة للفصل بشكل فعال، وبعضها الآخر ليس كذلك.

يمكن تحويل مجموعة جميع المجموعات الجزئية القابلة للتعداد التكراري للأعداد الطبيعية إلى مجموعة مرتبة جزئيًا تحت تضمين المجموعة ؛ هذه المجموعة المرتبة جزئيًا هي شبكة . ^{[ 3 ]} من المعروف أن نظرية هذه الشبكة مسألة غير قابلة للتقرير . ^{[ 3 ]} وبالمثل، فإن مجموعة جميع الفضاءات المتجهة القابلة للتعداد الحسابي تُشكل أيضًا شبكة. ^{[ 4 ]} في الواقع، يمكن تعميم ذلك أكثر إلى الشبكة L(Q) ، والتي تُعرَّف بأنها تتكون من جميع المرشحات القابلة للتعداد التكراري ، حيث Q هي جبر بولياني حر بدون أي ذرات . ^{[ 5 ]} ترتبط هذه الشبكات ارتباطًا وثيقًا بدراسة فئات Pi-0-1 القابلة للتعداد التكراري . ^{[ 5 ]}

وفقًا لأطروحة تشرش-تورينج ، فإن أي دالة قابلة للحساب فعليًا تكون قابلة للحساب بواسطة آلة تورينج ، وبالتالي فإن المجموعة S قابلة للحساب إذا وفقط إذا وُجدت خوارزمية ما تُنتج تعدادًا للمجموعة S. مع ذلك، لا يمكن اعتبار هذا تعريفًا رسميًا، لأن أطروحة تشرش-تورينج هي تخمين غير رسمي وليست بديهية رسمية. ^{[ 8 ]}

يُعدّ تعريف المجموعة القابلة للحساب على أنها مجال دالة جزئية، بدلاً من مدى دالة قابلة للحساب كليًا، شائعًا في النصوص المعاصرة. ويستند هذا الاختيار إلى حقيقة أنه في نظريات الاستدعاء المعممة، مثل نظرية الاستدعاء من النوع ألفا ، وُجد أن التعريف المقابل للمجالات أكثر طبيعية. بينما تستخدم نصوص أخرى التعريف بدلالة التعدادات، وهو تعريف مكافئ للمجموعات القابلة للحساب.

• RE (التعقيد)
• لغة قابلة للتعداد بشكل متكرر
• التسلسل الهرمي الحسابي

• روغرز، هـ. نظرية الدوال التكرارية والحوسبة الفعالة ، مطبعة معهد ماساتشوستس للتكنولوجيا . رقم ISBN 0-262-68052-1رقم الكتاب المعياري الدولي ( ISBN) 0-07-053522-1.
• سواري، ر. المجموعات والدرجات القابلة للتعداد بشكل متكرر. منظورات في المنطق الرياضي. سبرينغر-فيرلاغ ، برلين، 1987. ISBN 3-540-15299-7.
• سواري، روبرت آي. المجموعات والدرجات القابلة للتعداد بشكل متكرر. نشرة الجمعية الأمريكية للرياضيات 84 (1978)، العدد 6، 1149-1181.