مجموعة قابلة للعد بطريقة حسابية

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

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

أو على نحو مكافئ،

• توجد خوارزمية تقوم بإحصاء عناصر S. وهذا يعني أن ناتجها عبارة عن قائمة بكل عناصر S : s ₁ ، s ₂ ، s ₃ ، .... وإذا كانت S غير محدودة، فسوف تعمل هذه الخوارزمية إلى الأبد.

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

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

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

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

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

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

القدرة على العد:

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

ديوفانتين:

• هناك كثيرة حدود p ذات معاملات ومتغيرات صحيحة x و a و b و c و d و e و f و g و h و i تتراوح على الأعداد الطبيعية بحيث (عدد المتغيرات المقيدة في هذا التعريف هو الأفضل حتى الآن؛ وقد يكون من الممكن استخدام عدد أقل لتحديد جميع مجموعات ديوفانتين.)$${\displaystyle x\in S\Leftrightarrow \exists a,b,c,d,e,f,g,h,i\ (p(x,a,b,c,d,e,f,g,h,i)=0).}$$
• هناك حدود متعددة من الأعداد الصحيحة إلى الأعداد الصحيحة بحيث تحتوي المجموعة S على الأعداد غير السالبة الموجودة في نطاقها بالضبط.

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

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

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

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

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

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

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

وفقًا لأطروحة تشيرش-تورنج ، فإن أي دالة قابلة للحساب فعليًا يمكن حسابها بواسطة آلة تورنج ، وبالتالي فإن المجموعة S قابلة للحساب إذا وفقط إذا كانت هناك بعض الخوارزميات التي تنتج تعدادًا لـ S. ومع ذلك، لا يمكن اعتبار هذا تعريفًا رسميًا، لأن أطروحة تشيرش-تورنج هي تخمين غير رسمي وليس بديهية رسمية.

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

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

• روجرز، هـ. نظرية الوظائف المتكررة والحوسبة الفعالة ، مطبعة معهد ماساتشوستس للتكنولوجيا . ISBN 0-262-68052-1 ؛ ISBN 0-07-053522-1 .  
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag ، برلين، 1987. ISBN 3-540-15299-7 . 
• Soare, Robert I. Recursively enumable sets and degrees. مجلة الجمعية الأمريكية للرياضيات 84 (1978)، العدد 6، 1149-1181.