Všeobecné počítače

Z definície, všeobecný počítač môže riešiť akýkoľvek algoritmizovateľný problém vyjadriteľný v rámci praktických obmedzení určených kapacitou pamäte, veľkosťou programu, rýchlosťou vykonania programu a spoľahlivosti stroja. Alan Turing v roku 1934 dokázal, že všeobecný počítač po zadaní správneho programu môže emulovať správanie akéhokoľvek iného všeobecného počítača. Tento matematický dôkaz bol čisto teoretický, keďže v tej dobe neexistoval žiaden všeobecný počítač. Dôsledky dôkazu sú však zásadného charakteru; napríklad ktorýkoľvek súčasný všeobecný počítač by bol schopný emulovať, hoci pomaly, akýkoľvek všeobecný počítač, ktorý môžeme skonštruovať v budúcnosti.
Počítače so chopnosťami všeobecného počítača sa nazývajú turingovo úplné a tento stav sa používa ako prahová možnosť schopností súčasného počítača. Definícia je však problematická. Pre niekoľko počítacích strojov triviálnej konštrukcie bola dokázaná turingova úplnosť. Počítač Z3, ktorý vyvinul v roku 1941 Konrad Zuse bol prvým počítačom, ktorému bola dokázaná turingova úplnosť (v roku 1998). Hoci je Z3 a iné rané zariadenia sú turingovo úplné, sú ako počítače nepraktické. Spadajú do oblasti, ktorá sa žartom prezýva Turingova dechtová diera -- "miesto, kde je čokovek možné, ale nič zaujímavé pre prax" (The Jargon File). Moderné počítače sú viac ako teoreticky všeobecné -- sú schopné všeobecne riešiť praktické úlohy. Moderné digitálne elektronické všeobecné počítače sa vyvinuli za prispenia mnohých ľudí počas obdobia od polovice 30. rokov 20. storočia do konca 40. rokov, kedy boli zostavené mnohé stroje, ktoré mali blízko turingovej úplnosti (ABC, ENIAC, Harvard Mk I, Colossus atď., pozri História hardvéru). O všetkých týchto strojoch sa hovorilo v určitom zmysle ako o prvom počítači, ale všetky mali obmedzenú použiteľnosť ako všeobecný počítač a ich konštrukcia bola prekonaná.