הבדלים בין גרסאות בדף "חישוביות"

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

עריכות