חישוביות

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

חישוביות היא הבסיס למדעי המחשב, והיא עוסקת במודלים לחישוב ובפונקציות הניתנות לחישוב במסגרתם.

בניגוד להנחה נפוצה, ישנן פונקציות שאי אפשר לחשב. בעיית העצירה מהווה דוגמה לפונקציה שכזו: ניתן להוכיח כי אין תוכנית היכולה לקבל כקלט תוכנית כלשהי והקלט לאותה התוכנית, ולומר האם התוכנית תעצור.

תאוריית החישוביות החלה להתפתח בתחילת המאה העשרים, במחקרים מתמטיים שעסקו בשאלה איזה בעיות מתמטיות ניתנות לפתרון בדרכים פשוטות. ראשית היה צריך לקבוע מהי "דרך פשוטה", ולשם כך היה צורך במודל של חישוב. אחד המודלים הראשונים שנוצרו הוא מכונת טיורינג, אשר מהווה אבן דרך בתורת החישוביות כולה, בשל פשטותו ודמיונו למחשב (שטרם הומצא בעת יצירת מודל זה). מודל אחר הוא זה של תחשיב למדא. הוכח ששני מודלים אלה, ומודלים רבים נוספים אחרים שהוצעו (כגון דקדוקים תלויי הקשר), שקולים זה לזה בעוצמתם - חישוב שניתן לבצע באחד מהמודלים ניתן לבצע גם באחרים. מודלים אלה שקולים גם למחשב, אם נניח קיומו של זיכרון בלתי מוגבל בגודלו. תזת צ'רץ'-טיורינג משערת שכל פורמליזציה סבירה של מושג האלגוריתם תהיה שקולה למכונת טיורינג.

במסגרת תאוריית החישוביות נבחנות תכונותיהם של מודלים חישוביים שונים, על ידי בדיקת מחלקת הפונקציות שניתן לחשב במודל, ושקילותה למחלקת הפונקציות של מודל אחר. ההיררכיה של חומסקי מתארת היררכיית מחלקות הניתנות לחישוב במודלים שונים, כך שלכל מחלקת פונקציות בהיררכיה מתאימים מודלים רבים, אשר שקולים אחד לשני. למשל, דקדוקים חופשיי הקשר שקולים לאוטומטי מחסנית, מבחינה זו, והאוטומטים הסופיים שקולים לדקדוקים לינאריים ימניים. במסגרת היררכיה זו מתקיימים גם השוויונות שתוארו לעיל, בין תחשיב למדא, מכונת טיורינג, והדקדוקים תלויי ההקשר.

בנוסף, ניתן לחקור תכונות כלליות של מחלקות של פונקציות. למשל, מחלקות פונקציות שהן פונקציות פרימיטיביות רקורסיביות, והקשר בינן לבין מחלקות אחרות.

גם כאשר בעיות ניתנות לפתרון, ייתכן שהן דורשות זמן כה רב להשגת הפתרון עד שהפתרון חדל להיות מעשי - בסוגיה זו עוסק התחום הקרוי סיבוכיות.