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

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

المجموعة غير القابلة للحساب تسمى "|غير قابلة للحساب " noncomputable أو غير قابلة للتقرير undecidable.

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

التعريف

مجموعة فرعية $S$ من الأعداد الطبيعية تسمى قابلة للحساب إذا كانت هناك دالة قابلة للحساب إجمالية $f$ مثل

$f(x)=1$ إذا كانت $x\in S$ و $f(x)=0$ إذا كانت $x\notin S$ .

بمعنى آخر ، المجموعة $S$ قابلة للحساب إذا وفقط إذا كانت دالة المؤشر $\mathbb {1} _{S}$ قابلة للحساب .

أمثلة وغير أمثلة

أمثلة:

• كل مجموعة فرعية منتهية أو مشتركة من الأعداد الطبيعية قابلة للحساب. يتضمن تلك الحالات الخاصة التالية :
  • المجموعة الفارغة قابلة للحساب.
  • المجموعة الكاملة من الأعداد الطبيعية قابلة للحساب.
  • كل رقم طبيعي ( كما هو محدد في نظرية المجموعة القياسية ) قابل للحساب ؛ أي أن مجموعة الأعداد الطبيعية الأقل من عدد طبيعي معين قابلة للحساب.
• المجموعة الفرعية من الأعداد الأولية قابلة للحساب.
• اللغة العودية prime numbers أي مجموعة فرعية قابلة للحساب من اللغة الشكلية .
• مجموعة أرقام Gödel من البراهين الحسابية الموصوفة في أطروحة Kurt Gödel "حول الافتراضات غير القابلة للتقرير رسميًا لـ Principia Mathematica والأنظمة ذات الصلة I" قابلة للحساب ؛ انظر نظريات عدم الاكتمال لجودل .

غير الأمثلة:

• مجموعة آلات تورينج التي تتوقف غير قابلة للحساب.
• لا يمكن حساب فئة التشابه لمجمعين بسيطين محددين.
• مجموعة أبطال القندس المشغول busy beaver champions غير قابلة للحساب.
• مشكلة هيلبرت العاشرة غير قابلة للحساب.

الخواص

إذا كانت A مجموعة قابلة للحساب ، فإن تكملة A تكون مجموعة قابلة للحساب. إذا كانت A و B مجموعتين قابلتين للحساب ، فإن A B و A ∪ B وصورة A × B ضمن دالة الاقتران Cantor هي مجموعات قابلة للحساب.

A هي مجموعة قابلة للحساب إذا وفقط إذا كان كل من A ومكملة A يمكن عدهما بشكل حسابي (c.e) computably enumerable . إن الصورة المسبقة لمجموعة قابلة للحساب ضمن دالة حسابية كلية هي مجموعة قابلة للحساب. يمكن حساب صورة مجموعة قابلة للحساب في ظل انحياز محسوب إجمالي. (بشكل عام تكون صورة مجموعة قابلة للحساب تحت دالة حسابية هي c.e ، ولكن ربما لا تكون قابلة للحساب).

A هي مجموعة قابلة للحساب فقط إذا كانت على المستوى $\Delta _{1}^{0}$ من التسلسل الهرمي الحسابي .

A هي مجموعة قابلة للحساب إذا وفقط ، إذا كانت إما نطاق دالة غير قابلة للحساب الإجمالية أو المجموعة الفارغة. صورة مجموعة قابلة للحساب تحت دالة غير قابلة للحساب الإجمالية تكون غير قابلة للحساب.

أنظر أيضًا

• لغة يمكن عدها بشكل متكرر
• اللغة العودية
• العودية

المراجع

• Cutland، N. Computability. مطبعة جامعة كامبريدج ، كامبريدج - نيويورك ، 1980.(ردمك 0-521-22384-9) ؛(ردمك 0-521-29465-7)
• روجرز ، هـ.نظرية الوظائف العودية والحساب الفعال ، مطبعة معهد ماساتشوستس للتكنولوجيا.(ردمك 0-262-68052-1)رقم ISBN 0-262-68052-1 ؛(ردمك 0-07-053522-1)
• Soare، R. المجموعات والدرجات التي يمكن عدها بشكل متكرر. وجهات نظر في المنطق الرياضي. Springer-Verlag ، برلين ، 1987.(ردمك 3-540-15299-7)رقم ISBN 3-540-15299-7

روابط خارجية

• Sakharov, Alex. "Recursive Set". MathWorld.