פורטל:מדעי המחשב/הידעת?/29

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