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

قبل الخوض في التفاصيل، في نظرية الحوسبة ، تسمى مجموعة من الأرقام الطبيعية القابلة للحساب أ أو القابلة للتقرير computable إذا كانت هناك خوارزمية تأخذ رقمًا كمدخلات ، وتنتهي بعد فترة زمنية محدودة (ربما اعتمادًا على الرقم المحدد) وتقرر بشكل صحيح ما إذا كان الرقم ينتمي إلى المجموعة أم لا. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
علاوةً على ذلك، تتكون فئة المجموعات الأكثر عمومية من المجموعات القابلة للحساب من مجموعات القابلة للحساب ، والتي تسمى كذلك المجموعات شبه القابلة للتقرير semidecidable sets. بالنسبة لهذه المجموعات ، يلزم فقط وجود خوارزمية تقرر بشكل صحيح متى يكون الرقم في المجموعة ؛ قد لا تعطي الخوارزمية إجابة (لكن ليس الإجابة الخاطئة) للأرقام غير الموجودة في المجموعة.
من جانب آخر، المجموعة غير القابلة للحساب تسمى "|غير قابلة للحساب " noncomputable أو غير قابلة للتقرير undecidable.
أمثلة وغير أمثلة
كذلك، كل رقم طبيعي ( كما هو محدد في نظرية المجموعة القياسية ) قابل للحساب ؛ أي أن مجموعة الأعداد الطبيعية الأقل من عدد طبيعي معين قابلة للحساب.
- غير الأمثلة:
- مجموعة آلات تورينج التي تتوقف غير قابلة للحساب.
- لا يمكن حساب فئة التشابه لمجمعين بسيطين محددين.
- مجموعة أبطال القندس المشغول busy beaver champions غير قابلة للحساب.
- مشكلة هيلبرت العاشرة غير قابلة للحساب.
المجموعة الكاملة من الأعداد الطبيعية قابلة للحساب.
المجموعة الفارغة قابلة للحساب.
وفي السياق ذاته، اللغة العودية prime numbers أي مجموعة فرعية قابلة للحساب من اللغة الشكلية .
المجموعة الفرعية من الأعداد الأولية قابلة للحساب.
علاوةً على ذلك، مجموعة أرقام Gödel من البراهين الحسابية الموصوفة في أطروحة Kurt Gödel "حول الافتراضات غير القابلة للتقرير رسميًا لـ Principia Mathematica والأنظمة ذات الصلة I" قابلة للحساب ؛ انظر نظريات عدم الاكتمال لجودل .
وفي هذا الصدد، كل مجموعة فرعية منتهية أو مشتركة من الأعداد الطبيعية قابلة للحساب. يتضمن تلك الحالات الخاصة التالية :
أمثلة:
التعريف
من جهة ثانية، مجموعة فرعية من الأعداد الطبيعية تسمى قابلة للحساب إذا كانت هناك دالة قابلة للحساب إجمالية مثل
إذا كانت و إذا كانت .
وعلى صعيد آخر، بمعنى آخر ، المجموعة قابلة للحساب إذا وفقط إذا كانت دالة المؤشر قابلة للحساب .
الخواص
من جهة ثانية، A هي مجموعة قابلة للحساب إذا وفقط ، إذا كانت إما نطاق دالة غير قابلة للحساب الإجمالية أو المجموعة الفارغة. صورة مجموعة قابلة للحساب تحت دالة غير قابلة للحساب الإجمالية تكون غير قابلة للحساب.
من جهة ثانية، إذا كانت A مجموعة قابلة للحساب ، فإن تكملة A تكون مجموعة قابلة للحساب. إذا كانت A و B مجموعتين قابلتين للحساب ، فإن A B و A ∪ B وصورة A × B ضمن دالة الاقتران Cantor هي مجموعات قابلة للحساب.
وفي هذا السياق، A هي مجموعة قابلة للحساب إذا وفقط إذا كان كل من A ومكملة A يمكن عدهما بشكل حسابي (c.e) computably enumerable . إن الصورة المسبقة لمجموعة قابلة للحساب ضمن دالة حسابية كلية هي مجموعة قابلة للحساب. يمكن حساب صورة مجموعة قابلة للحساب في ظل انحياز محسوب إجمالي. (بشكل عام تكون صورة مجموعة قابلة للحساب تحت دالة حسابية هي c.e ، ولكن ربما لا تكون قابلة للحساب).
في هذا الإطار، A هي مجموعة قابلة للحساب فقط إذا كانت على المستوى من التسلسل الهرمي الحسابي .
- أنظر كذلك
- لغة يمكن عدها بشكل متكرر
- اللغة العودية
- العودية
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟