La teorio de komputado estas la branĉo de komputado, kiu traktas, ĉu kaj kiel komputaj taskoj povas esti kompetente solvitaj per komputilo. La kampo estas dividita en du ĉefajn branĉojn: teorio de komputebleco kaj komplikteorio, sed ambaŭ branĉoj formaligas modelojn de komputado.
Por efektivigi rigoran studadon de komputado, komputosciencistoj laboras kun matematikaj abstraktigoj de komputiloj nomataj modeloj de komputado. Kelkaj tipoj de tiaj modeloj estas uzataj, sed la plej kutimaj estas diversaj specoj de maŝino de Turing. Maŝino de Turing estas konceptebla kiel persona komputilo kun nelimigita memor-kapacito, kvankam ĉiupaŝe ĝi povas atingi nur etan diskretan porcion de de sia memoro. Fakuloj studas la maŝinon de Turing, ĉar ĝi estas simple formulebla, analizebla kaj kutime eblas pruvi la rezultojn, kaj ĉar ĝi prezentas tion, kion multaj konsideras adekvata modelo de la teorie plej pova komputo-kapablo. Dum la nelimigita memor-kapacito povus esti konsiderata nefizika atributo, por ajna problemo reale solvata per maŝino de Turing la memoro uzata ĉiam estas finia, do ajna problemo, kiu povas esti solvita per maŝino de Turing, principe povas esti solvita per kutima reala komputilo, kiu havas sufiĉan memoron.
Teorio de komputebleco traktas unuavice la demandon ĉu problemo estas entute solvebla per komputilo. La problemo de halto estas unu el la plej gravaj rezultoj en teorio de komputebleco, ĉar ĝi estas ekzemplo de konkreta problemo kiu estas kaj facile formulebla kaj kiun neeblas solvi per maŝino de Turing. Multo en teorio de komputebleco konstruiĝas sur la rezulto pri la problemo de halto.
Teorio de komputebleco estas proksime rilata al la branĉo de matematika logiko nomata kiel rekursia teorio, kiu forprenas la limigon de studado nur modelojn de kalkulado kiuj estas proksimaj al fizike realigeblaj. Multaj matematikistoj kiuj studas rekursian teorion nomas ĝin teorio de komputebleco. Estas neniu reala diferenco inter la kampoj krom tio, ĉu esploristo konsideras sin kiel fakulo pri komputoscienco aŭ pri matematiko.
Komplikteorio konsideras ne nur ĉu problemo entute povas esti solvita perr komputilo, sed ankaŭ kiel kompetente la problemo povas esti solvita. Du ĉefaj aspektoj estas konsiderataj: tempa komplikeco kaj spaca komplikeco, kiuj estas respektive kiu kvanto da paŝoj necesas por plenumi la kalkuladon, kaj kiu kvanto da memoro estas bezonata por plenumi la kalkuladon.
Por analizi bezonatajn tempon kaj spacon por donita algoritmo, oni esprimas la kvanton de la tempo aŭ spaco kiel funkcio de la amplekso de la enigo-problemo. Ekzemple, trovo de aparta nombro en longa listo de nombroj iĝas ju pli pezan des pli la listo estas longa. Se estas n nombroj en la listo, tiam se la listo estas ne ordigita aŭ indeksita en ia maniero, tiam oni eble devos kontroli ĉiun nombron por trovi la nombro kion oni celas. Oni tial diras, ke por solvi ĉi tiun problemon, la komputilo bezonas plenumi kvanton de paŝoj kreskas lineare laŭ la amplekso de la problemo.
Por simpligi tiun problemon, komputistoj uzas la notacion granda O, kiu permesas al funkcioj esti komparitaj kvazaŭ tiel ke apartaj aspektoj de maŝina aparataro ne bezone estas konsiderataj, sed konsiderante nur la asimptotan konduton de la problemoj, kiam la problemoj iĝas grandajn. Do en nia antaŭa ekzemplo oni povas diri, ke la problemo postulas O(n) paŝojn por solvado.
Eble la plej grava malferma problemo entute en komputiko estas la demando ĉu problemoj de certa larĝa klaso nomata kiel NP povas esti solvataj kompetente. Ĉi tiu estas diskutita plu en komplikecaj klasoj P kaj NP.
Krom maŝino de Turing, aliaj ekvivalentaj modeloj de kalkulado uzatas (pri la ekvivalenteco vidu en tezo de Church-Turing).
Aldone al la ĝeneralaj komputaj modeloj, iuj pli simplaj komputaj modeloj estas utilaj por specialaj, limigitaj aplikoj.
Ekzemple, Regulesprimoj, estas uzataj por precizigi liniajn ŝablonojn en Unikso kaj en iuj programlingvoj kiel Perl. Alia formalismo matematike ekvivalento al regulesprimoj, finiaj aŭtomatoj estas uzataj en cirkvita dizajno kaj en iuj specoj de problemo-solvado. Ĉirkaŭteksto-liberaj gramatikoj estas uzataj por precizigi programlingvan sintakson. Ne-determinismaj aŭtomatoj estas alia formalisma ekvivalento al ĉirkaŭteksto-liberaj gramatikoj. Primitivaj rekursiaj funkcioj estas difinita subklaso de la rekursiaj funkcioj.
Malsamaj modeloj de kalkulado havas la kapablon fari malsamajn taskojn. Unidirekta ebleco mezuri la povo de komputa modelo estas studi la klason de formalaj lingvoj, kiujn la modelo povas generi; tio kondukas al la hierarkio laŭ Ĉomski de lingvoj.