La teoria de la computació comença pròpiament a principis del segle XX, poc abans que les computadores electròniques fossin inventades.

En aquesta època diversos matemàtics es preguntaven si existia un mètode universal per resoldre tots els problemes matemàtics. Per a això havien de desenvolupar la noció precisa de mètode per resoldre problemes , és a dir, la definició formal d' algorisme .

Un dels primers resultats d'aquesta teoria va ser l'existència de problemes impossibles de resoldre algorítmicament, i el problema de la parada el més famós d'ells. Per a aquests problemes no existeix ni existirà cap algoritme que els pugui resoldre, no important la quantitat de temps o memòria es disposi en un ordinador. Així mateix, amb l'arribada de les computadores modernes es va constatar que alguns problemes resolubles en teoria eren impossibles en la pràctica, ja que aquestes solucions necessitaven quantitats irrealistes de temps o memòria per poder-se trobar.

http://ca.wikipedia.org/wiki/Teoria_de_la_computaci%C3%B3#Hist.C3.B2ria