הצגת המקור של הדף "חישוביות"

{{תקציר פורטל|מדעי המחשב}}
תורת ה'''חישוביות''' היא הבסיס ל[[מדעי המחשב]], והיא עוסקת במודלים ל[[חישוב (מדעי המחשב)|חישוב]] וב[[פונקציה|פונקציות]] [[כריעות|הניתנות לחישוב]] במסגרתם. השאלה הבסיסית בתורת החישוביות היא: מה מחשבים יכולים לחשב, ומה לא? בניגוד להנחה נפוצה, ישנן פונקציות שאי אפשר לחשב. [[בעיית העצירה]] מהווה דוגמה לפונקציה שכזו: ניתן להוכיח כי אין [[תוכנית מחשב|תוכנית]] היכולה לקבל כקלט תוכנית כלשהי וקלט לאותה התוכנית, ו[[כריעות|להכריע]] האם התוכנית תעצור.
למעשה, מספר הפונקציות שניתן לחשב הוא <math>\!\, \aleph_0</math> (קרי: [[אלף אפס|אָלֶף אֶפֶס]]), מאחר שלכל בעיה חשיבה ניתן לכתוב תוכנית מחשב, ומספר תוכניות מחשב שאנחנו יכולים לכתוב הוא <math>\!\, \aleph_0</math>. מאידך, מספר הבעיות החישוביות כולן הוא <math>\aleph</math> (ז"א, מ[[עוצמת הרצף]]). לכן, רק מהשוואת עוצמות, ניתן להסיק שבהכרח קיימות בעיות חישוביות אשר לא ניתנות לפתרון תחת מודלים חישוביים מסוימים, כדוגמת מכונת טיורינג.

== היסטוריה ==
תורת החישוביות החלה להתפתח בתחילת [[המאה ה-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

==קישורים חיצוניים==
{{מיזמים|ויקיספר=תורת החישוביות|שם ויקיספר=תורת החישוביות|ויקימילון=חשוביות}}
* [http://aduni.org/courses/theory/ קורס בחישוביות ב־ArsDigita] (הרצאות מוקלטות וחומרים)
* [https://web.archive.org/web/20140801015832/http://coursebooks.cs.huji.ac.il/wikis/MediaWiki/coursebooks/index.php/%D7%97%D7%99%D7%A9%D7%95%D7%91%D7%99%D7%95%D7%AA קורס בחישוביות באוניברסיטה העברית 2008] (סיכומי הרצאות חלקיים)
* {{MathWorld}}

{{מדעי המחשב}}

[[קטגוריה:חישוביות|*]]
[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]