| Wikipedia ויקיפדיה העברית - האנציקל... |
כריעות
במדעי המחשב, שפה נקראת כריעה אם קיים אלגוריתם שמקבל כקלט מילה, וקובע אם היא שייכת לשפה או לא. באופן פורמלי, שפה 
תיקרא כריעה אם קיימת מכונת טיורינג M אשר עוצרת על כל קלט ומקבלת בדיוק את השפה . במילים אחרות, אם מכונת טיורינג M תקבל כקלט מילה בשפה, היא תעצור במצב מקבל, ואם הקלט הוא מילה שאינה בשפה L, המכונה תעצור במצב דחייה. את מחלקת הבעיות (השפות) הכריעות מסמנים ב-R.
הדיון התאורטי בכריעות של שפות מקביל למושג החישוביות של אלגוריתמים. לדוגמה, השאלה אם קיים אלגוריתם אשר לכל מספר נתון יודע להגיד אם המספר ראשוני או פריק, שקול לשאלה אם השפה המכילה את כל המספרים הראשוניים, היא כריעה.
| להמשך המאמר ראה Wikipedia.org... |
© מאמר זה משתמש בתוכן מ-ויקיפדיה® וכפוף לרשיון לשימוש חופשי במסמכים של גנו GNU Free Documentation License וכפוף לרישיון Creative Commons ייחוס-שיתוף זהה
