Direkt zum Inhalt

Lexikon der Mathematik: unentscheidbare Theorie

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).

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.