גבולות החישוביות
אף על פי שמחשבים בני זמננו הם מהירים ורבי עָצְמה, הם אינם כל-יכולים. מדעני מחשב עוסקים רבות בשאלה מה יכול המחשב לחשב מהבחינה העקרונית ומהבחינה המעשית. גם אם משימה היא אפשרית מן הבחינה העקרונית, יכול להיות שהמחיר גבוה מדי.
משימות בלתי אפשריות
"אי אפשר" הוא מושג רב משמעות. יש מספר סיבות אפשריות לכך שמחשב לא יוכל לפתור בעיה:
- יש משימות שמחשב – אפילו המהיר והחזק ביותר שקיים היום – לא יכול לבצע משום שיידרש לו זמן כה ממושך שגם גיל היקום – מהמפץ הגדול עד שיכבו הכוכבים – לא יספיק לביצוען. משימות כאלה, שאין מניעה עקרונית לפתרונן, תפתרנה רק אם יפותחו רעיונות חדשים ונצליח לבצע קפיצה מחשבתית משמעותית. זהו אתגר מרכזי של מדעני מחשב תיאורטיים. השאלה פה אינה שאלה טכנולוגית. אין מדובר על האצת הביצועים של מחשבים, כי אם על פיתוח דרכי חשיבה חדשות ואלגוריתמים חדשים אשר יאפשרו לבצע משימות שהיום מוגדרות קשות, אך הוכח שהן לא בלתי אפשריות.
לנושא הזה יש השלכה מעשית רבת חשיבות: שיטות ההצפנה הנהוגות היום, שמאפשרות למשל את המסחר המקוון באינטרנט, מתבססות על בעיות שאין מניעה עקרונית לפתור אותן, אך כיום אינן פתירות בזמן סביר. כלומר, עד היום לא נמצאה דרך זריזה לפתור את הבעיות הללו. אם מישהו יפתח אלגוריתם חדש ויעיל לבעיות אלה, תהיינה לכך השלכות מרחיקות לכת! יש משימות שדורשות מספר פעולות כה רב, עד שגם רעיונות חדשים לא יסייעו בפתרונן. לדוגמא, אם נבקש מהמחשב (ואפילו בנימוס) לרשום את כל המספרים השלמים מ-1 עד 21000000, לא כדאי שנצפה לראות את התוצאה לפני הארוחה הבאה. - יש גם משימות שהוכח כי לא ניתן לפתור בכלל. עבורן הוכח שמהבחינה העקרונית אין ולא יהיה מחשב (המבוסס על המודל של טיורינג) אשר יוכל להתמודד איתן.
ומה עם המוח שלנו?
קשה לדבר על גבולות יכולתו של המחשב בלי לתהות לגבי ההשלכות על גבולות החשיבה האנושית: האם המוח מסוגל לחשוב בכיוונים שחסומים בפני המחשב? האם גם החשיבה שלנו מוגבלת? מה דעתכם?
כבר במאמרו הבסיסי על מספרי בני חישוב, עם יישום לבעיית ההכרעה משנת 1936, השכיל אלן טיורינג להבחין כי המודל החישובי "שלו" מוגבל ביכולותיו, ויש שאלות שבמסגרתו הן בלתי ניתנות להכרעה.