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

מ
בוט החלפות: לעיתים
מ (בוט החלפות: לעתים, דוגמה\1, בהינתן)
מ (בוט החלפות: לעיתים)
רעיון הכריעוּת ניתן להרחבה על ידי [[מודל חישובי|מודלים חישוביים אחרים]]. למשל, אפשר לדבר על שפות כריעות ב[[מכונת טיורינג לא-דטרמיניסטית]]. לכן, בכל פעם שיש אי-בהירות, "שפה רקורסיבית" בעלת משמעות זהה לשפה הניתנת להכרעה על ידי מכונת טיורינג.
 
המחלקה של כל השפות הרקורסיבית שפות נקראת בספרות '''R''', אם כי שם זה משמש לעתיםלעיתים גם עבור המחלקה [[RP]].
 
סוג זה של שפה לא הוגדר ב[[ההיררכיה של חומסקי|היררכיה של חומסקי]] {{Harv|Chomsky|1959}}. כל השפות הרקורסיבית גם ניתנות למנייה רקורסיבית (Recursively Enumerable). כל [[שפה רגולרית]], [[שפה חופשית הקשר|שפה חפשית הקשר,]] ו[[שפה תלוית הקשר]] היא גם '''רקורסיבית'''.