Bei der bisherigen Untersuchung von Sprachklassen haben wir festgestellt, dass die regulären Sprachen eine echte Teilmenge der kontextfreien Sprachen sind, und diese wiederum eine echte Teilmenge der entscheidbaren Sprachen. Der Fokus lag bislang darauf, die „Berechenbarkeit“ von Sprachen (bzw. Entscheidungsproblemen) nachzuweisen. Nun werden wir uns im Gegensatz dazu auf den Nachweis der „Nichtberechenbarkeit“ konzentrieren. Wir versuchen zudem, die Grenze zwischen Nichtberechenbaren und Berechenbaren möglichst gut zu bestimmen.