חישוביות
מושג במדעי המחשב / ויקיפדיה האנציקלופדיה encyclopedia
תורת החישוביות היא הבסיס למדעי המחשב, והיא עוסקת במודלים לחישוב ובפונקציות הניתנות לחישוב במסגרתם. השאלה הבסיסית בתורת החישוביות היא: מה מחשבים יכולים לחשב, ומה לא? בניגוד להנחה נפוצה, ישנן פונקציות שאי אפשר לחשב. בעיית העצירה מהווה דוגמה לפונקציה שכזו: ניתן להוכיח כי אין תוכנית היכולה לקבל כקלט תוכנית כלשהי וקלט לאותה התוכנית, ולהכריע האם התוכנית תעצור. למעשה, מספר הפונקציות שניתן לחשב הוא (קרי: אָלֶף אֶפֶס), מאחר שלכל בעיה חשיבה ניתן לכתוב תוכנית מחשב, ומספר תוכניות מחשב שאנחנו יכולים לכתוב הוא . מאידך, מספר הבעיות החישוביות כולן הוא (ז"א, מעוצמת הרצף). לכן, רק מהשוואת עוצמות, ניתן להסיק שבהכרח קיימות בעיות חישוביות אשר לא ניתנות לפתרון תחת מודלים חישוביים מסוימים, כדוגמת מכונת טיורינג.
עיינו גם בפורטל פורטל מדעי המחשב הוא שער לכל הנושאים הקשורים במדעי המחשב. ניתן למצוא בו קישורים אל תחומי המשנה של הענף, מושגי יסוד בתחום, מדענים חשובים ועוד. |