חישוביות

תורת החישוביות היא הבסיס למדעי המחשב, והיא עוסקת במודלים לחישוב ובפונקציות הניתנות לחישוב במסגרתם. השאלה הבסיסית בתורת החישוביות היא: מה מחשבים יכולים לחשב, ומה לא? בניגוד להנחה נפוצה, ישנן פונקציות שאי אפשר לחשב. בעיית העצירה מהווה דוגמה לפונקציה שכזו: ניתן להוכיח כי אין תוכנית היכולה לקבל כקלט תוכנית כלשהי וקלט לאותה התוכנית, ולהכריע האם התוכנית תעצור. למעשה, מספר הפונקציות שניתן לחשב הוא ${\displaystyle \!\,\aleph _{0}}$ (קרי: אָלֶף אֶפֶס), מאחר שלכל בעיה חשיבה ניתן לכתוב תוכנית מחשב, ומספר תוכניות מחשב שאנחנו יכולים לכתוב הוא ${\displaystyle \!\,\aleph _{0}}$. מאידך, מספר הבעיות החישוביות כולן הוא ${\displaystyle \aleph }$ (ז"א, מעוצמת הרצף). לכן, רק מהשוואת עוצמות, ניתן להסיק שבהכרח קיימות בעיות חישוביות אשר לא ניתנות לפתרון תחת מודלים חישוביים מסוימים, כדוגמת מכונת טיורינג.

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

את מחלקת השפות (בעיות) שניתנות להכרעה למחצה, דהיינו, שניתן לבנות מכונת טיורינג שתמיד מקבלת קלט שהוא בשפה (גם אם אינה עוצרת על קלט שאינו בשפה), מסמנים ב-RE ‏(Recursivley enumerable). באופן שקול, מגדירים את המחלקה coRE, כמחלקת השפות שניתן לחשב את דחייתן – כלומר, שעבור כל קלט ניתן לודא שהוא אינו בשפה. אם כן, כל שפה שהיא חשיבה נמצאת בחיתוך של RE ו-coRE.

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

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

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

• פונקציה בת-חישוב
• מספר חשיב
• בעיית העצירה
• הבונה העסוק
• תורת הסיבוכיות

• M. Sipser, Introduction to the Theory of Computation, PWS Publishing Co., 1997.
• J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Co., 1979

מיזמי קרן ויקימדיה
ערך מילוני בוויקימילון: חשוביות
ספר לימוד בוויקיספר: תורת החישוביות

• קורס בחישוביות ב־ArsDigita (הרצאות מוקלטות וחומרים)
• קורס בחישוביות באוניברסיטה העברית 2008 (סיכומי הרצאות חלקיים)
• חישוביות, באתר MathWorld (באנגלית)