Algorithmentheorie, Berechenbarkeitstheorie, mathematische Theorie, die sich mit dem formalen Begriff der Berechenbarkeit und der Algorithmen befaßt.

Die Aufgabe, eine adäquate Definition für „berechenbar“ zu finden, gilt aufgrund der Churchschen These als gelöst, da alle bislang vorgeschlagenen Berechenbarkeitsbegriffe sich als untereinander äquivalent herausgestellt haben (Turing-Maschine). Die Formalisierung des Berechnungsbegriffs hat sich als notwendig herausgestellt, nachdem um 1900 eher die Vorstellung vorherrschte, daß die gesamte Mathematik in gewisser Weise algorithmisierbar sei. Diese Vorstellung wurde durch den Gödelschen Unvollständigkeits-satz 1931 zunichte gemacht, welcher an der Grenze zwischen mathematischer Logik und Berechnungstheorie angesiedelt ist. Durch diesen Satz wurde klar gemacht, daß es nicht-berechenbare Funktionen bzw. nicht-entscheidbare Probleme gibt.

Beispiele hierzu sind die Nicht-Entscheidbarkeit der Prädikatenlogik (unentscheidbare Theorie), des Halteproblems, des Dominoproblems, des Postschen Korrespondenzproblems, des zehnten Hilbertschen Problems und des Wortproblems für Semi-Thue-Systemen.

Die fortgeschrittene Berechnungstheorie befaßt sich u. a. mit relativer Berechenbarkeit und Turing-Reduzierbarkeit, die vermittels sog. Orakel-Turing-Maschinen definiert werden kann. Auf diese Weise können innerhalb der nicht-entscheidbaren Mengen Hierarchien, wie die arithmetische Hierarchie, betrachtet werden, und es können Probleme, die gegenseitig Turing-reduzierbar sind, zu Äquivalenzklassen, sog. Turing-Graden, zusammengefaßt werden. In der Theorie der Unlösbarkeitsgrade werden insbesondere deren verbandstheoretische Strukturen untersucht.

Besondere Aufmerksamkeit ist auch auf die Struktur der rekursiv aufzählbaren Mengen gerichtet.

Eine besonders erfolgreiche Beweistechnik zur Konstruktion von Mengen, die einerseits erwünschte Eigenschaften erhalten sollen, und andererseits andere Eigenschaften meiden sollen, ist die Prioritätsmethode.