חישוביות

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

תורת החישוביות היא הבסיס למדעי המחשב, והיא עוסקת במודלים לחישוב ובפונקציות הניתנות לחישוב במסגרתם. השאלה הבסיסית בתורת החישוביות היא: מה מחשבים יכולים לחשב, ומה לא? בניגוד להנחה נפוצה, ישנן פונקציות שאי אפשר לחשב. בעיית העצירה מהווה דוגמה לפונקציה שכזו: ניתן להוכיח כי אין תוכנית היכולה לקבל כקלט תוכנית כלשהי וקלט לאותה התוכנית, ולהכריע האם התוכנית תעצור. למעשה, מספר הפונקציות שניתן לחשב הוא \!\, \aleph_0 (קרי: אֲלף אפס), מאחר שלכל בעיה חשיבה ניתן לכתוב תוכנית מחשב, ומספר תוכניות מחשב שאנחנו יכולים לכתוב הוא \!\, \aleph_0. מאידך, מספר השפות כולן הוא \aleph (ז"א, מעוצמת הרצף).


היסטוריה[עריכת קוד מקור | עריכה]

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

תחומי המחקר ומונחי יסוד[עריכת קוד מקור | עריכה]

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

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

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

תחומי מחקר משיקים[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

עיינו גם בפורטל

P Computer-science.png

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


קישורים חיצוניים[עריכת קוד מקור | עריכה]