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

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

مجموعة فرعية${\displaystyle S}$تكون دالة الأعداد الطبيعية قابلة للحساب إذا وُجدت دالة قابلة للحساب كليًا${\displaystyle f}$بحيث:

${\displaystyle f(x)=1}$لو${\displaystyle x\in S}$

${\displaystyle f(x)=0}$لو${\displaystyle x\notin S}$.

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

• كل لغة تكرارية قابلة للحساب.
• كل مجموعة جزئية منتهية أو متكافئة من الأعداد الطبيعية قابلة للحساب.
  • المجموعة الفارغة قابلة للحساب.
  • مجموعة الأعداد الطبيعية بأكملها قابلة للحساب.
  • كل عدد طبيعي قابل للحساب. ^{[ ملاحظة 1 ]}
• مجموعة الأعداد الأولية قابلة للحساب.
• مجموعة أعداد غودل قابلة للحساب. ^{[ ملاحظة 2 ]}

كلا من A و B عبارة عن مجموعات في هذا القسم.

• إذا كانت A قابلة للحساب ، فإن متممة A قابلة للحساب.
• إذا كانت A و B قابلتين للحساب، فإن:
  • A ∩ B قابلة للحساب.
  • A ∪ B قابلة للحساب.
  • صورة A × B تحت دالة اقتران كانتور قابلة للحساب.

بشكل عام، فإن صورة مجموعة قابلة للحساب تحت دالة قابلة للحساب تكون قابلة للتعداد الحسابي، ولكن ربما لا تكون قابلة للحساب.

• تكون A قابلة للحساب إذا وفقط إذا كانت A ومكملة A كلاهما قابلين للحساب والتعداد (ce ) .
• الصورة العكسية لمجموعة قابلة للحساب تحت دالة قابلة للحساب كليًا هي قابلة للحساب.
• صورة مجموعة قابلة للحساب تحت تقابل قابل للحساب كليًا هي قابلة للحساب.

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

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

• قابل للحساب والتعداد
• قابلية الحسم (المنطق)
• لغة قابلة للتعداد بشكل متكرر
• اللغة التكرارية
• التكرار

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

• ساخاروف، أليكس . "المجموعة المتكررة" . عالم الرياضيات .