תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←כריעות (מלאה): מוטיבציה |
|||
שורה 11:
===כריעות (מלאה)===
כפי שראינו, התנהגות מ״ט על קלט מסוים יכולה להיות אחת משלוש האפשרויות הבאות: קבלה, דחייה, או אי־עצירה.
כשאנו כותבים למשל תוכנית מחשב הפותרת בעיה כלשהי, מן הסתם לא נרצה שהיא "תתקע" ותכנס ללולאה אינסופית. מבחינה פרקטית, יותר מעניינות אותנו תוכנות־מחשב שלא נתקעות, ותמיד מצליחות לסיים את החישוב. באופן דומה, עבור בעיות הכרעה,
נרצה להגדיר תחילה את המכונות שמתנהגות "יפה", כלומר תמיד עוצרות (מקבלות או דוחות כל קלט), ולעולם לא "נתקעות" בלולאה אינסופית.
{{הגדרה|תוכן=
| |||