שפה רקורסיבית

שפה רקורסיבית, או שפה כריעה היא מונח במתמטיקה, לוגיקה ומדעי המחשב, המתאר שפה פורמלית (קבוצה של רצפים סופיים של סמלים שנלקחו  מאלף-בית מסוים) המהווה תת קבוצה רקורסיבית של הקבוצה של כל הרצפים הסופיים מעל האלפבית של השפה. באופן שקול, שפה רשמית היא רקורסיבית אם קיימת מכונת טיורינג טוטאלית (מכונת טיורינג העוצרת על כל קלט), אשר בהנתן רצף סופי של סימנים כקלט, מקבלת אם הרצף שייך לשפה ודוחה אחרת. שפות רקורסיבית שפות נקראים גם כְּרִיעׂות.

רעיון הכריעוּת ניתן להרחבה על ידי מודלים חישוביים אחרים. למשל, אפשר לדבר על שפות כריעות במכונת טיורינג לא-דטרמיניסטית. לכן, בכל פעם שיש אי-בהירות, "שפה רקורסיבית" בעלת משמעות זהה לשפה הניתנת להכרעה על ידי מכונת טיורינג.

המחלקה של כל השפות הרקורסיבית שפות נקראת בספרות R, אם כי שם זה משמש לעיתים גם עבור המחלקה RP.

סוג זה של שפה לא הוגדר בהיררכיה של חומסקי (Chomsky 1959). כל השפות הרקורסיבית גם ניתנות למנייה רקורסיבית (Recursively Enumerable). כל שפה רגולרית, שפה חפשית הקשר, ושפה תלוית הקשר היא גם רקורסיבית.

דוגמאות

שפות תלויות-הקשר גם הן רקורסיביות. לדוגמא השפה $L={abc,aabbcc,aaabbbccc,...}$ או בכתיב הפורמלי:

$L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 1\,\}$

סגירוּת אלגברית

רקורסיבית שפות סגורה תחת הפעולות הבאות. כלומר, אם L ו P הן שתי שפות רקורסיביות, השפות הבאות גם הן רקורסיביות:

• כוכב קלין $L^{*}$
• התמונה (φ(L תחת הומומורפיזם  φ (כלומר e-free homomorphism)
• השרשור $L\circ P$
• האיחוד $L\cup P$
• החיתוך $L\cap P$
• המשלים של $L$
• קבוצת ההפרש $L-P$