Nozares teorijas Par mūsdienu datorzinātnes matemātisko pamatu uzskata austriešu un amerikāņu matemātiķa Kurta Gēdeļa (Kurt Gödel) 1931. gadā publicēto teorēmu par nepilnību. Teorēma parāda, ka jebkuras formālas sistēmas ietvaros pastāv apgalvojumi, kurus nevar ne pierādīt, ne apgāzt.
Par datorzinātnes pamatlicēju tiek uzskatīts angļu matemātiķis Alans Tjūrings (Alan Mathison Turing), vairāk zināms kā Otrā pasaules kara laika vācu šifrēšanas mašīnas Enigma kodu atšifrētājs. A. Tjūrings pārformulēja K. Gēdeļa teorēmu par pierādīšanas un izrēķināmības robežām, aizvietojot K. Gēdeļa aritmētikā balstīto formālo valodu ar formālām un vienlaikus vienkāršām hipotētiskām ierīcēm, kas vēlāk kļuva pazīstamas kā Tjūringa mašīnas (Turing machines). A. Tjūrings pierādīja, ka allaž atradīsies tāda mašīna, kas spēs veikt konkrētu iedomātu matemātisku skaitļojumu, ja tas pierakstīts kā algoritms. Viņš pierādīja, ka izlemjamības problēma (vācu Entscheidungsproblem, angļu decision problem; citiem vārdiem, vai eksistē algoritms, kas vienmēr var pateikt, vai matemātisks apgalvojums ir patiess, vai nav?) nav atrisināma, vispirms pierādot, ka Tjūringa mašīnas apstāšanās problēma nav atrisināma, t. i., vispārīgā gadījumā nav iespējams algoritmiski noteikt, vai Tjūringa mašīna jebkad apstāsies. Šo pašu rezultātu, tikai pierādīšanā izmantojot lambda rēķinus, dažus mēnešus agrāk neatkarīgi ieguva amerikāņu matemātiķis Alonso Čērčs (Alonzo Church, A. Tjūringa doktora darba vadītājs). A. Tjūringa pieeja ir vieglāk uztverama un intuitīva. Izrēķināmības teorijas un visas datorzinātnes pamats ir t. s. Čērča (arī Čērča-Tjūringa, Tjūringa-Čērča) tēze jeb pieņēmums par izrēķināmām funkcijām. Čērča tēze apgalvo, ka ikviena funkcija pār naturāliem skaitļiem ir izrēķināma neformālā izpratnē (t. i., funkcijas vērtību var iegūt cilvēks, izmantojot “papīra un zīmuļa metodi”, pieņemot, ka resursi – papīrs, zīmuļi un rēķināšanas laiks – ir neierobežoti) tad un tikai tad, ja šo funkciju var izrēķināt kāda Tjūringa mašīna.
Līdz 1949. gadam, kad sāka darbināt vienu no pirmajiem datoriem – EDVAC (Electronic Discrete Variable Automatic Computer ’elektroniskais diskrētais maināmais automātiskais skaitļotājs’) Pensilvānijas Universitātē (University of Pennsylvania) ASV, visām programmējamām skaitļošanas mašīnām programmas un apstrādājamie dati bija fiziski nošķirti. Glabāt datus un programmu vienā un tajā pašā mašīnas atmiņā vienā t. s. adrešu telpā 1944. gadā izlēma EDVAC konstruktori Džons Prespērs Ekerts (John Presper Eckert) un Džons Moklijs (John Mauchly), bet 1945. gadā tehniskā pārskatā dokumentēja ungāru un amerikāņu matemātiķis, fiziķis un datorzinātnieks Džons fon Neimans (John von Neumann). Šāda datoru uzbūve drīz vien kļuva par valdošo līdz pat mūsdienām, to dēvē par fon Neimana arhitektūru.
Pie datorzinātnes nozīmīgākajiem pētījumiem būtu jāpieskaita arī t. s. Tjūringa tests leģendārā jautājuma “Vai mašīna spēj domāt [līdzvērtīgi cilvēkam]?” kontekstā. Tā kā nav iespējams pārbaudīt, vai konkrēts objekts domā, A. Tjūrings piedāvāja procedūru, kur cilvēks novērtētājs, izmantojot tikai rakstītus tekstus, sazinās ar diviem tam neredzamiem objektiem, no kuriem viens ir cilvēks, bet otrs – mašīna. Ja novērtētājs nespēj droši noteikt, kurš no abiem ir mašīna, atliek secināt, ka mašīna demonstrē tādu intelektuālu uzvedību, kas nav atšķirama no cilvēciskas, un tātad jāpieņem, ka mašīna domā. Mūsdienās mākslīgā intelekta izmantojums dabisko valodu tehnoloģijās ir pārvarējis Tjūringa testu.
Līdz 20. gs. 30. gadu beigām elektroinženieri būvēja elektroniskās shēmas matemātisku un loģikas problēmu risināšanai nesistemātiskā veidā, maz balstoties uz stingrām teorijām, kamēr 1937. gadā amerikāņu matemātiķis, elektroinženieris un kriptografiķis Klods Elvūds Šenons (Claude Elwood Shannon), iepazinies ar angļu matemātiķa Džordža Būla (George Boole) darbiem algebriskajā loģikā, izdomāja, ka elektromehāniskos relejus (tolaik tos izmantoja telefonu komutatoros) var lietot loģisku problēmu risināšanā. Šī koncepcija kļuva plaši izplatīta elektronisko digitālo datoru jomā kopš Otrā pasaule kara.
K. E. Šenons turpināja pētniecību, un 1948. gadā lika pamatus informācijas teorijai. Šī teorija izmanto varbūtību teorijas rezultātus, lai risinātu problēmu, kā vislabāk kodē informāciju, ko pārraida sūtītājs saņēmējam. K. E. Šenona rezultāti ir viens no teorētiskajiem pamatiem daudzām turpmākām pētniecības jomām, to vidū datu saspiešanai un kriptogrāfijai.
Piedaloties eksperimentos ar pretaviācijas aizsardzības sistēmām, kas interpretēja radaru attēlus pretinieka lidmašīnu atklāšanai, amerikāņu matemātiķis un loģiķis Norberts Vīners (Norbert Wiener) ieviesa jēdzienu “kibernētika”. N. Vīnera 1948. gadā publicētā grāmata “Kibernētika: jeb vadība un saziņa dzīvniekos un mašīnās” (Cybernetics: Or Control and Communication in the Animal and the Machine) nozīmīgi ietekmēja mākslīgā intelekta jomas izaugsmi. N. Vīners norādīja uz analoģijām starp rēķināšanu, skaitļošanas mašīnām, atmiņas ierīcēm un citiem kognitīviem aspektiem ar smadzeņu viļņu analīzē atklāto.
1949. gadā kanādiešu psihologs Donalds Oldings Hebs (Donald Olding Hebb) piedāvāja smadzeņu mācīšanās matemātisko modeli, kā rezultātā, papildinot modeli ar bioloģiskiem datiem, tika radītas mākslīgo neironu tīklu un paralēlās dalītās apstrādes jomas.
1971. gadā amerikāņu un kanādiešu matemātiķis un datorzinātnieks Stīvens Kuks (Stephen Arthur Cook) un neatkarīgi padomju un amerikāņu matemātiķis un datorzinātnieks Leonīds Levins (Leonid Levin) pierādīja, ka eksistē praktiski nozīmīgas problēmas, kas ir nedeterministiski polinomiālā laikā (nondeterministic polynomial time) pilnas. Tas bija nozīmīgs atklājums skaitļošanas sarežģītības teorijā, jo tika pierādīts, ka reālu skaitļošanas uzdevumu izpilde var nebūt pieņemamā laikā īstenojama. 20. gs. sākumā, attīstoties fizikas kvantu teorijai, radās redzējums, ka matemātiskas darbības varētu veikt visas elementārdaļiņas viļņa funkcijas jeb matemātiskas funkcijas vērtības var rēķināt vienlaicīgi daudzos stāvokļos. 20. gs. otrajā pusē šī ideja tika formalizēta kvantdatora modelī; piemēram, 1997. gadā amerikāņu matemātiķis un datorzinātnieks Pīters Šors (Peter Williston Shor) pierādīja, ka kvantdatoru varētu praktiski izmantot ļoti lielu skaitļu sadalīšanai pirmreizinātājos polinomiālā laikā (parastais dators to nespēj). Ja P. Šora algoritmu varētu īstenot ar reāli eksistējošu kvantdatoru, lielākā daļa mūsdienu datu aizsardzības sistēmu izrādītos nederīgas.
Mūsdienu teorētiskā datorzinātne tiek balstīta uz šiem rezultātiem, taču ietver arī daudzu citu matemātisku un pārdisciplināru problēmu pētīšanu.
Tims Berners-Lī (Tim Berners-Lee) 1989. gadā, būdams Eiropas kodolpētījumu organizācijas (European Organization for Nuclear Research) CERN līdzstrādnieks, iesniedza priekšlikumu oriģinālai informācijas apstrādes sistēmai, kas tika novērtēta kā “neskaidra, bet aizraujoša”. Priekšlikumā bija aprakstīta hiperteksta iezīmēšanas valoda jeb HTML (HyperText Markup Language), vienotais resursu vietrādis jeb URL (Uniform Resource Locator) un hiperteksta transporta protokols jeb HTTP (HyperText Transfer Protocol). T. Berners-Lī pats sāka izstrādi un ātri vien tapa prototips tam, ko mūsdienās pazīstam kā globālo tīmekli (World Wide Web, www).