eine logische Theorie, die, als Menge von Formeln aufgefaßt, eine nicht entscheidbare Menge darstellt (Entscheid- barkeit).

Dies bedeutet, daß es keinen Algorithmus gibt, der bei jeder vorgelegten Formel in endlich vielen Schritten entscheiden kann, ob die Formel zur Theorie gehört oder nicht.

Ein Beispiel für eine unentscheidbare Theorie ist die elementare Zahlentheorie (Gödelscher Unvollständigkeitssatz). Ein weiteres Beispiel stellt die Menge der wahren Formeln der Prädikatenlogik der ersten Stufe dar (Unentscheidbarkeit der Prädika- tenlogik).