Dieses Kapitel führt in die theoretische Informatik ein und zeigt ihre Bedeutung für die kognitive KI: Programme können genutzt werden, um kognitive Prozesse zu modellieren und zu prüfen. Dafür sind theoretische Konzepte nötig, die Programme beschreiben, vergleichen und bewerten. Algorithmen werden am Beispiel des Euklidischen Algorithmus erläutert, inklusive Kriterien wie Korrektheit und Effizienz. Turing-Maschinen werden als universelles Berechnungsmodell eingeführt, ergänzt durch die Church–Turing-These. Formale Sprachen und Grammatiken strukturieren Eingaben, die Chomsky-Hierarchie ordnet Sprachtypen nach ihrer Mächtigkeit.