Die theoretische Informatik beschäftigt sich mit der Theorie formaler Sprachen, Logik, Aussagenlogik, Prädikatenlogik und der Logik-Programmierung und bietet Grundlagen für den Bau von Programmiersprachen und die Formalisierung von mathematischen Problemstellungen. Sie ist das formale Rückgrad der Wissenschaft der Computer.
Sie beschäftigt sich außerdem mit der mathematischen Lösbarkeit von Problemen, also inwieweit sich Probleme überhaupt mathematisch formulieren und damit lösen kann, und welchen Aufwand man dazu treiben muss.
Dabei werden formale Systeme, Automaten, Graphen und Syntaxdiagramme dazu genutzt, die innere Logik eines formalen Problems exakt wiederzugeben. Oft ist dieser formale Schritt ein wesentlicher Teil zur Lösung der eigentlichen Problemstellung und erschließt eine durch Maschinensemantik noch bequemer gewordene Welt der Mathematik und Computerei.
Siehe auch: Algorithmus, Entscheidbarkeit, Turing, Turingmaschine, Registermaschine, Chomsky-Hierarchie, mathematisches Beweisen, reflexiv-transitive Hüllen, Graphentheorie, PNP, Traveling-Salesman-Problem, Syntaxbäume, Automatentheorie, Fixpunktsemantik, Semantik, LBA, Pumping-Lemma, Gödel, Gödel Escher Bach, Komplexitätstheorie, BNF, eBNF, reguläre Sprachen, kontextfreie Sprachen, DFA, NFA, Gödelnummer, Halteproblem