„Számítástudomány” változatai közötti eltérés

* [[kiszámíthatóságelmélet]], rekurzióelmélet: ez egyes függvényeknek, műveleteknek más függvényekkel való kiszámíthatóságával foglalkozik, tekinthető a számításelmélet egy olyan ágának vagy testvérterületének is; mely Turing-gépek és automaták helyett hagyományos matematikai fogalmakra (függvény, generált struktúra stb.) alapoz. E terület úttörője [[Stephen Cole Kleene]] volt (érdekesség, hogy tekinthető a [[matematikai logika]] részének is).<ref>[http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Kleene.html (ld. angolul)]</ref>

* automataelmélet,<ref name="ralston" /> számításelmélet, bonyolultságelmélet, vagy komplexitáselmélet: [[formális nyelv]]ek, formális nyelvtanok és [[absztrakt automata|automaták]] elmélete: ide sorolhatóak a [[generatív nyelvtan]]ok, általánosabban a [[produkciós rendszerek]], az automatatípusok által generált és elfogadott nyelvek vizsgálata, az egyes automatatípusok összehasonlítása; ennek az al-ágnak rengeteg fontos kutatója volt mind nyugaton, mind a [[Szovjetunió]]ban, ill. [[Oroszország]]ban; fontos terület a [[Turing-gép]]ek és hasonló automaták elmélete, mégpedig az ezek által futtatott [[algoritmus]]ok idő-és memóriaigényének vizsgálata, központi problémája a hatékonysági vagy bonyolultsági osztályok (P, NP stb.) közti kapcsolatok megállapítása, illetve az indeterminisztikus algoritmusok vizsgálata és alkalmazása;

* [[formális szemantika]]: ez a [[fordítóprogram]]ok különböző formális nyelvtanokkal való leírásának matematikai elméletéből nőtte ki magát, fontos szerepet játszanak benne az attribútumnyelvtanok és rekurzív nyelvtanok elmélete (például), vagy például a logikai programozás elméleti leírása;

* mesterségesintelligencia-kutatás<ref name="ralston" /> (pontosabban ennek matematikai alapjai): az az algoritmusok hatékonyságát azok önállóságának, önműködésének szempontjából vizsgálja; ez az elmélet a számítógép-tudomány, az informatika és a kognitív tudomány érdekes határterületeiből nőtt össze és ki;