תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
דוגמאות |
מ הגהה |
||
שורה 1:
{{תורת החישוביות}}
נאמר שמ"ט M '''מכריעה''' שפה L אם היא <u>מקבלת</u> כל מילה ב־L ו<u>דוחה</u> כל מילה שאינה ב־L. כלומר, M עוצרת על כל מילת קלט (אין מילים שגורמות למכונה להכנס ללולאה אינסופית).
{{הגדרה|תוכן=שפה L '''ניתנת להכרעה''' אם קיימת מ"ט M שמכריעה אותה. }}
| |||