computation

(ש"ע) חישוב, הערכה

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