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

مجموعة فرعية ${\displaystyle S}$ من الأعداد الطبيعية تسمى قابلة للحساب إذا كانت هناك دالة قابلة للحساب إجمالية خطأ رياضيات (SVG (يمكن تمكين MathML عبر البرنامج المساعد للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "http://localhost:6011/ar.wikipedia.org/v1/":): {\displaystyle f} مثل

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

بمعنى آخر ، المجموعة ${\displaystyle S}$ قابلة للحساب إذا وفقط إذا كانت دالة المؤشر ${\displaystyle \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 هي مجموعة قابلة للحساب فقط إذا كانت على المستوى ${\displaystyle \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.

• بوابة رياضيات
• بوابة علم الحاسوب