اللغة التكرارية

في الرياضيات والمنطق وعلوم الحاسوب ، تُعرَّف اللغة التكرارية ( أو القابلة للتقرير ) بأنها مجموعة فرعية تكرارية من إغلاق كلين لأبجدية ما . وبالمثل، تُوصف اللغة الرسمية بأنها تكرارية إذا وُجدت آلة تورينغ قادرة على تقريرها . ^{[ 1 ]} في علوم الحاسوب النظرية ، تُسمى آلات تورينغ التي تتوقف دائمًا بآلات تورينغ الكلية أو خوارزميات تورينغ الكلية . ^{[ 2 ]}

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

غالبًا ما يطلق على فئة جميع اللغات المتكررة اسم R ، على الرغم من أن هذا الاسم يستخدم أيضًا للفئة RP .

لم يُعرَّف هذا النوع من اللغات في التسلسل الهرمي لتشومسكي . ^{[ 3 ]} جميع اللغات الاسترجاعية قابلة للتعداد الاسترجاعي . جميع اللغات المنتظمة ، واللغات الخالية من السياق، واللغات الحساسة للسياق هي لغات استرجاعية.

يوجد تعريفان رئيسيان متكافئان لمفهوم اللغة التكرارية:

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

من جهة أخرى، يمكننا إثبات أن مسألة القرار قابلة للحل من خلال عرض آلة تورينج تُشغّل خوارزمية تتوقف عند جميع المدخلات. أما المسألة غير القابلة للحل فهي مسألة لا يمكن حلها.

كما ذُكر أعلاه، فإن كل لغة حساسة للسياق هي لغة تكرارية. ومن الأمثلة البسيطة على اللغة التكرارية المجموعة L={abc, aabbcc , aaabbbccc , ...} ؛ أو بشكل أكثر دقة، المجموعة

${\displaystyle L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ لبعض }}n\geq 1\,\}}$

هو حساس للسياق وبالتالي فهو تكراري.

يصعب وصف أمثلة اللغات القابلة للتقرير غير الحساسة للسياق. فعلى سبيل المثال، يتطلب الأمر بعض الإلمام بالمنطق الرياضي : حساب بريسبرغر هو نظرية الرتبة الأولى للأعداد الطبيعية مع الجمع (ولكن بدون الضرب). ورغم أن مجموعة الصيغ الصحيحة في حساب بريسبرغر مستقلة عن السياق، فإن كل آلة تورينغ حتمية تقبل مجموعة العبارات الصحيحة في حساب بريسبرغر يكون لها زمن تشغيل في أسوأ الحالات لا يقل عن${\displaystyle 2^{2^{pn}}}$، لثابت ما p > 0. ^{[ 4 ]} هنا، n يرمز إلى طول الصيغة المعطاة. بما أن كل لغة حساسة للسياق يمكن قبولها بواسطة آلة خطية محدودة ، ويمكن محاكاة هذه الآلة بواسطة آلة تورينج حتمية بوقت تشغيل في أسوأ الحالات لا يتجاوز${\displaystyle q^{n}}$بالنسبة لثابت ما q ، ^{[ 5 ]} فإن مجموعة الصيغ الصحيحة في حساب بريسبرغر غير حساسة للسياق. ومن الجدير بالذكر أنه من المعروف وجود آلة تورينغ حتمية تعمل في زمن أسي ثلاثي على الأكثر بالنسبة لـ n، وهي التي تحدد مجموعة الصيغ الصحيحة في حساب بريسبرغر. ^{[ 6 ]} وبالتالي، يُعد هذا مثالًا على لغة قابلة للتقرير ولكنها غير حساسة للسياق.

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

• نجم كلين${\displaystyle L^{*}}$
• الصورة φ(L) تحت تشاكل φ الخالي من e
• التسلسل${\displaystyle L\circ P}$
• الاتحاد${\displaystyle L\cup P}$
• التقاطع${\displaystyle L\cap P}$
• مكمل لـ${\displaystyle L}$
• الفرق بين المجموعات${\displaystyle LP}$

وتنتج الخاصية الأخيرة من حقيقة أنه يمكن التعبير عن فرق المجموعة من حيث التقاطع والمكمل.

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

• بوك، رونالد ف. (1974). "مقارنة فئات التعقيد". مجلة علوم الحاسوب والأنظمة . 9 : 213-229 . doi : 10.1016/S0022-0000(74)80008-5 . MR 0366099 . 
• تشومسكي، نعوم (1959). "حول بعض الخصائص الشكلية للقواعد النحوية". المعلومات والتحكم . 2 (2): 137-167 . doi : 10.1016/S0019-9958(59)90362-6 .
• فيشر، مايكل ج .؛ رابين، مايكل أو. (1974). "التعقيد الأسي الفائق لحساب بريسبرغر" . وقائع ندوة SIAM-AMS في الرياضيات التطبيقية . 7 : 27-41 .
• أوبن، ديريك سي. (1978). "حد أعلى من 2 ^{2 2 pn} لتعقيد حساب بريسبرغر" . مجلة علوم الحاسوب والأنظمة . 16 (3): 323-332 . doi : 10.1016/0022-0000(78)90021-1 .
• سيبسر، مايكل (1997). "قابلية الحسم" . مقدمة في نظرية الحوسبة . دار نشر PWS. الصفحات 151-170 . ISBN  978-0-534-94728-6.
• سيبسر، مايكل (2012). "أطروحة تشيرش-تورينغ". مقدمة في نظرية الحوسبة . سينغيج ليرنينج. ص  170. ISBN 978-1-133-18779-0.