Direkt zum Inhalt

Lexikon der Mathematik: Prioritätsmethode

eine insbesondere in der Theorie der Unlösbarkeitsgrade (Berechnungstheorie) sehr nützliche und wirksame beweistechnische Methode zur Konstruktion einer i. allg. rekursiv aufzählbaren Menge, die bestimmte zusätzliche Bedingungen erfüllen soll.

Solche Bedingungen stellen sich üblicherweise dar in Form von unendlich vielen einfachen Einzelbedingungen b1, b2, …, die sich an einer Aufzählung W1, W2, … aller rekursiv aufzählbaren Mengen orientieren. Die Bedingungen werden dabei nach absteigender Priorität behandelt. Die Prioritätsmethode ist eingebettet in einen Aufzählungsalgorithmus für die Elemente der zu konstruierenden Menge A. Wird ein Element x in die Menge A gesetzt, so können dadurch gewisse Bedingungen erfüllt, andere jedoch gerade verhindert werden. Für jede Bedingung gibt es im Laufe des Verfahrens aber unendlich oft die Möglichkeit, diese zu erfüllen. Wenn zu einem bestimmten Zeitpunkt im Ablauf des Verfahrens eine Bedingung bi erfüllt werden kann (i sei der kleinste Index einer bisher noch nicht erfüllten Bedingung), so wird diese Aktion nur dann ausgeführt, wenn nicht eine Bedingung höherer Priorität verletzt wird; Bedingungen niedrigerer Priorität, die bereits etabliert sind, dürfen aber wieder verletzt werden. Man kann zeigen, daß jede Bedingung schließlich erfüllt wird.

Mit Hilfe der Prioritätsmethode haben Friedberg und Muchnik 1952 erstmals gezeigt, daß es unentscheidbare, rekursiv aufzählbare Mengen gibt, die nicht im selben Turing-Grad wie das Halteproblem liegen. Damit wurde das Postsche Problem von 1944 gelöst.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte