Nachdem wir in den letzten Kapiteln verschiedene Automatenmodelle und Grammatiken eingeführt bzw. gestreift haben, wollen wir in diesem Kapitel ein weiteres, sehr mächtiges Automatenmodell einführen: die Turingmaschine. Die Turingmaschine ähnelt zunächst sehr einem DFA. Wir erlauben der Turingmaschine aber zusätzlich auf dem Eingabeband nicht nur nach rechts, sondern auch nach links zu gehen und wir erlauben ihr nicht nur ein Symbol zu lesen, sondern auch ein Symbol auf das Band zu schreiben. Diese Änderung führen zu einem sehr mächtigen Modell. Tatsächlich gilt die Turingmaschine als abstraktes Modell dessen, was von jeder Maschine oder jedem Menschen berechnet werden kann, d.h. was immer wir oder eine von uns konstruierte Maschine berechnen kann, das kann auch die Turingmaschine berechnen. Wir werden dieser Aussage später als Church-Turing-These wieder begegnen. Diese These ist so formuliert nicht beweisbar, denn wer weiß schon mit Sicherheit, was wir in der Zukunft konstruieren? Sie hat sich aber als erstaunlich robust erwiesen, denn auch alle neueren Rechnermodelle wie bspw. Parallelrechner lassen sich von Turingmaschinen simulieren. Besonders interessant ist auch der Umkehrschluss: was von einer Turingmaschine nicht berechnet werden kann, das kann auch kein Mensch oder keine von ihm erbaute Maschine berechnen.

In den folgenden Abschnitten wollen wir die Turingmaschine einführen, Varianten von ihr wie z.B. eine nichtdeterministische Turingmaschine betrachten und dann die wichtigen Sprachfamilien der entscheidbaren und der aufzählbaren Sprachen einführen. Insb. die entscheidbaren Sprachen spielen bei Algorithmen eine wichtige Rolle. Wir werden dann zeigen, dass es auch unentscheidbare Probleme gibt, d.h. Probleme, für die es keinen Algorithmus geben kann, der sie löst. Ein Resultat, das von besonderer Bedeutung für die Informatik ist, da es uns unsere Grenzen mit dem Computer aufzeigt – und wir werden sehen, dass diese Grenze schon überraschend früh kommt.