Theoretische Informatik

Manche Probleme sind für jeden Rechner prinzipiell unlösbar, andere nur praktisch — ihre Laufzeit explodiert. Formale Sprachen legen mit präzisen Regeln fest, welche Zeichenfolgen wohlgeformt sind; endliche Automaten sind das einfachste Maschinenmodell, das solche Sprachen erkennt; die Turingmaschine erweitert es um unbegrenzten Speicher und macht Berechenbarkeit fassbar. Am Halteproblem zeigt sich die prinzipielle Grenze, an der O-Notation die praktische.