חישוביות – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
מ ←תחומי המחקר ומונחי יסוד: קישורים פנימיים |
||
שורה 10:
== תחומי המחקר ומונחי יסוד ==
את [[קבוצה ניתנת למנייה רקורסיבית|מחלקת השפות (בעיות) שניתנות להכרעה למחצה]], דהיינו, שניתן לבנות [[מכונת טיורינג]] שתמיד מקבלת קלט שהוא בשפה (גם אם אינה עוצרת על קלט שאינו בשפה), מסמנים ב-RE {{כ}}(Recursivley enumerable). באופן שקול, מגידירים את המחלקה coRE, כמחלקת השפות שניתן לחשב את דחייתן - כלומר, שעבור כל קלט ניתן לודא שהוא אינו בשפה. אם כן, כל שפה שהיא חשיבה נמצאת ב[[חיתוך (מתמטיקה)|חיתוך]] של RE ו-coRE.
במסגרת תורת החישוביות נבחנות תכונותיהם של מודלים חישוביים שונים, על ידי בדיקת [[מחלקת פונקציות|מחלקת הפונקציות]] שניתן לחשב במודל, ושקילותה למחלקת הפונקציות של מודל אחר. ה[[היררכיית חומסקי|היררכיה של חומסקי]] מתארת היררכיית מחלקות הניתנות לחישוב במודלים שונים, כך שלכל מחלקת פונקציות בהיררכיה מתאימים מודלים רבים, השקולים זה לזה. למשל, [[דקדוק חופשי הקשר|דקדוקים חופשיי הקשר]] שקולים ל[[אוטומט מחסנית|אוטומטי מחסנית]], מבחינה זו, וה[[אוטומט סופי|אוטומטים הסופיים]] שקולים ל[[דקדוק ליניארי ימני|דקדוקים ליניאריים ימניים]]. במסגרת היררכיה זו מתקיימים גם השוויונות שתוארו לעיל, בין תחשיב למדא, מכונת טיורינג, והדקדוקים הבלתי מוגבלים.
| |||