Welche Probleme lassen sich eigentlich mit einem Computer (allgemeiner in diesem Kapitel Automat genannt) lösen? Wie aufwendig oder simpel muss ein Automat aufgebaut sein, damit er welche Probleme für uns lösen kann? In einem simplen Getränkeautomaten ist ganz sicher kein Superrechner verbaut. Mit dieser Frage beschäftigt man sich seit über 100 Jahren in der Theorie der Berechenbarkeit, der Automaten und der formalen Sprachen, die z. B. in den Büchern von Hopcroft et al. (2007), Schöning (2005) und Wagner (2003) in allen formalen Details beschrieben wird.