In diesem Themenkomplex steht die Berechenbarkeitstheorie als Teilgebiet der theoretischen Informatik und der mathematischen Logik im Mittelpunkt. Der Begriff der Berechenbarkeit befasst sich insbesondere damit, welche Probleme mit einer Maschine (genauer: dem Modell einer Maschine) lösbar sind.
Zu Beginn der Informatikausbildung wurde ein intuitiver Begriff des Algorithmus definiert. Über diese Definition kann man Probleme als intuitiv berechenbar einstufen, falls es einen Algorithmus gibt, der diese löst.
Für genauere Betrachtungen muss der Begriff der Berechenbarkeit exakter formuliert und formalisiert werden. Als weitgehend anerkannte Antwort hat sich die Turingmaschine als mögliches Model durchgesetzt (Church-Turing-These). Es wurde zudem nachgewiesen, dass die Berechnungsfähigkeit der Turingmaschine gleichmächtig zu vielen anderen Berechnungsmodellen ist, so z. B. auch zur Registermaschine.
In diesem Kontext wird auch untersucht, welche Art Aufgaben welche Klasse von Maschinen lösen kann. Insbesondere werden deterministische und nichtdeterministische Varianten folgender Modelle untersucht:
- endlicher Automat
- Kellerautomat
- linear beschränkte Turingmaschine (LBA)
- Turingmaschine
- Registermaschine
Neben der Klassifizierung eines Problems als berechenbar bzw. nicht berechenbar ist die Durchführbarkeit dieser Berechnung zu diskutieren. Selbst wenn ein Problem als berechenbar gilt, kann es trotzdem sein, dass eine Lösung nicht möglich ist. Dies gilt u.a. für alle Probleme die sich nur mit exponentiellem Aufwand lösen lassen, z. B. bestimmte Graphenprobleme.
Ein weitere wichtige Eigenschaft von Problemen (bzw. für Algorithmen, die diese lösen) ist deren Entscheidbarkeit. Hierbei wird untersucht, ob für jedes Element einer Grundmenge entscheiden werden kann, ob es eine bestimmte Eigenschaft besitzt; das wohl bekannteste dieser Probleme ist das Halteproblem.
