لغة قابلة للتعداد بشكل متكرر

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

تُعرف اللغات القابلة للتعداد التكراري بلغات النوع صفر في تسلسل تشومسكي للغات الرسمية. جميع اللغات المنتظمة ، واللغات الخالية من السياق ، واللغات الحساسة للسياق، واللغات التكرارية هي لغات قابلة للتعداد التكراري.

تُسمى فئة جميع اللغات القابلة للتعداد بشكل متكرر RE .

توجد ثلاثة تعريفات متكافئة للغة القابلة للتعداد بشكل متكرر:

1. اللغة القابلة للتعداد بشكل متكرر هي مجموعة فرعية قابلة للتعداد بشكل متكرر في مجموعة جميع الكلمات الممكنة على أبجدية اللغة .
2. اللغة القابلة للتعداد التكراري هي لغة رسمية يوجد لها آلة تورينج (أو دالة حسابية أخرى ) قادرة على تعداد جميع السلاسل النصية الصحيحة في تلك اللغة. لاحظ أنه إذا كانت اللغة لانهائية ، فيمكن اختيار خوارزمية التعداد بحيث تتجنب التكرار، إذ يمكننا اختبار ما إذا كانت السلسلة النصية الناتجة للعدد n قد تم إنتاجها مسبقًا لعدد أقل من n . إذا كانت قد تم إنتاجها بالفعل، فاستخدم الناتج للمدخل n + 1 (تكراريًا)، ولكن اختبر مرة أخرى ما إذا كانت "جديدة".
3. اللغة القابلة للتعداد التكراري هي لغة رسمية يوجد لها آلة تورينج (أو دالة حسابية أخرى) تتوقف وتقبل أي سلسلة نصية من تلك اللغة كمدخل، ولكنها قد تتوقف وترفض أو تدخل في حلقة لا نهائية عند إدخال سلسلة نصية من خارج اللغة. على النقيض من ذلك ، فإن اللغات التكرارية تتطلب من آلة تورينج التوقف في جميع الحالات.

جميع اللغات المنتظمة ، واللغات الخالية من السياق ، واللغات الحساسة للسياق، واللغات المتكررة قابلة للتعداد بشكل متكرر.

تُظهر نظرية بوست أن RE ، جنبًا إلى جنب مع مكملها co-RE ، يتوافقان مع المستوى الأول من التسلسل الهرمي الحسابي .

مجموعة آلات تورينغ المتوقفة قابلة للتعداد التكراري، لكنها ليست تكرارية. في الواقع، يمكن تشغيل آلة تورينغ وقبول توقفها، لذا فهي قابلة للتعداد التكراري. من ناحية أخرى، المسألة غير قابلة للحل.

تتضمن بعض اللغات الأخرى القابلة للتعداد بشكل متكرر والتي ليست متكررة ما يلي:

• مشاكل المراسلات البريدية
• معدل الوفيات (نظرية الحوسبة)
• مشكلة اتخاذ القرار

تُعتبر اللغات القابلة للتعداد التكراري (REL) مغلقة تحت العمليات التالية. أي، إذا كانت L و P لغتين قابلتين للتعداد التكراري، فإن اللغات التالية قابلة للتعداد التكراري أيضًا:

• نجم كلين${\displaystyle L^{*}}$من L
• التسلسل​${\displaystyle L\circ P}$من L و P
• الاتحاد​${\displaystyle L\cup P}$
• التقاطع​${\displaystyle L\cap P}$.

اللغات القابلة للتعداد بشكل متكرر ليست مغلقة تحت نظرية الفرق بين المجموعات أو نظرية المكمل.${\displaystyle LP}$يكون قابلاً للتعداد بشكل متكرر إذا${\displaystyle P}$هي دالة تكرارية. إذا${\displaystyle L}$إذا كانت قابلة للتعداد بشكل متكرر، فإن مكملها${\displaystyle L}$تكون قابلة للتعداد بشكل متكرر إذا وفقط إذا${\displaystyle L}$وهي أيضاً متكررة.

• مجموعة قابلة للحساب والتعداد
• التكرار

• سيبسر، مايكل (1997). مقدمة في نظرية الحوسبة (  الطبعة الأولى). دار نشر PWS. رقم ISBN 978-0-534-94728-6.( متاح للزبائن ذوي الإعاقات البصرية )
• كوزين، دي سي (1997)، الأتمتة والحوسبة ، سبرينغر .

• حديقة حيوانات التعقيد : فئة RE