Direkt zum Inhalt

Lexikon der Mathematik: Postsches Problem

ein von E. Post 1944 aufgestelltes Problem der Berechnungstheorie: Gibt es rekursiv aufzählbare Mengen, die weder entscheidbar (Entscheidbarkeit) sind, noch denselben Turing-Grad wie das Halteproblem haben?

Um das Problem zu lösen, wurden von Post die einfachen Mengen und die immunen Mengen eingeführt (was aber nicht zum Erfolg führte). Das Problem wurde dann 1952 unabhängig von Friedberg und Muchnik im positiven Sinne gelöst. Der Beweis gelang mit einer neuen Beweistechnik, der Prioritätsmethode.

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