שפה רקורסיבית: הבדלים בין גרסאות

(יצירה באמצעות תרגום הדף "Recursive language")
 
תגית: עריכת קוד מקור 2017
'''שפה רקורסיבית''', או '''שפה כריעה''' היא מונח ב[[מתמטיקה]], [[לוגיקה]] ו[[מדעי המחשב]], המתאר [[שפה פורמלית]] ([[קבוצה (מתמטיקה)|קבוצה]] של רצפים סופיים של סמלים שנלקחו  מאלף-בית מסוים) המהווה [[קבוצה רקורסיבית|תת קבוצה רקורסיבית]] של הקבוצה של כל הרצפים הסופיים מעל ה[[אלפבית]] של השפה. באופן שקול, שפה רשמית היא רקורסיבית אם קיימת מכונת טיורינג טוטאלית ([[מכונת טיורינג]] העוצרת על כל קלט), אשר בהנתן רצף סופי של סימנים כקלט, מקבלת אם הרצף שייך לשפה ודוחה אחרת. שפות רקורסיבית שפות נקראים גם '''[[כריעות|כְּרִיעׂות]]'''.
 
רעיון הכריעוּת ניתן להרחבה על ידי [[מודל חישובי|מודלים חישוביים אחרים]]. למשל, אפשר לדבר על שפות כריעות ב[[מכונת טיורינג לא-דטרמיניסטית]]. לכן, בכל פעם שיש אי-בהירות, "שפה רקורסיבית" בעלת משמעות זהה לשפה הניתנת להכרעה על ידי מכונת טיורינג.