Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten von Spektrum der Wissenschaft frei zugänglich.

Mathematische Logik: Bedrohliche Unentscheidbarkeit

Aussagen, die man prinzipiell weder beweisen noch widerlegen kann, sind keineswegs so esoterisch, wie es klingt. Man findet sie, indem man das Verhalten kleiner Turing-Maschinen untersucht.
Eine Turing-Maschine tut nichts weiter, als das unter ihrem Schreib-Lese-Kopf befindliche Zeichen von einem unendlich langen Magnetband zu lesen und daraufhin den Befehl aus der Liste auszuführen, der zu dem gelesenen Zeichen und ihrem inneren Zustand gehört.
Errata: In der Definition des fleißigen Bibers mit 2 Zuständen (Kasten S. 76) muss es in der dritten Zeile [B 0 -> 1 links A] heißen (nicht … links B). Weiter unten in der Definition des fleißigen Bibers mit 4 Zuständen muss die dritte Zeile lauten [B 0 -> 1 links A] (nicht rechts). Robert Krell hat uns auf die Fehler aufmerksam gemacht.

Wenn ein mathematisches Problem einfach aussieht, wie die Frage "Ist 4n4+1 für alle natürlichen Zahlen eine Primzahl?", dann ist der durchschnittliche Mathematiker überzeugt, es lösen zu können. Im Einzelfall werden unterschiedliche Auffassungen da­rüber bestehen, wie schwierig ein konkretes Problem ist; aber je besser sich ein Mathematiker in einem Teilgebiet auskennt, desto sicherer ist sein Urteil über den Schwierigkeitsgrad.

In manchen Fällen versagt allerdings die Erfahrung der fähigsten Fachvertreter. Pierre de Fermat (1607–1665) hat sich sicherlich nicht vorgestellt, dass die unschuldig aussehende Aussage "Es gibt keine Lösung der Gleichung nq + mq = pq mit natürlichen Zahlen n, m und p und einer natürlichen Zahl q > 2" seine wissenschaftlichen Nachkommen 350 Jahre lang beschäftigen würde. Hinter scheinbar einfachen Aussagen verbergen sich zuweilen äußerst hartnäckige Hindernisse.

Die schwierigsten Probleme sind diejenigen, die man als "unentscheidbar" bezeichnet. Und was tun die Mathematiker? Sie suchen nach den einfachsten unter den unentscheidbaren Problemen. Dieses Spiel ist keineswegs müßig; es hilft die wesentlichen Hindernisse genauer einzugrenzen, die einer Lösung oder eben der Entscheidbarkeit entgegenstehen. Das wiederum bringt die Problemlösefähigkeit voran – und damit die Mathematik im Allgemeinen.

Was genau bedeutet Unentscheidbarkeit? Eine Aussage ist unentscheidbar in einer gegebenen Theorie, wenn sie sich in dieser Theorie weder beweisen noch widerlegen lässt. Und diese doppelte Unmöglichkeit muss ihrerseits beweisbar sein. Damit das überhaupt möglich ist, muss man die Theorie sehr präzise definiert haben und sie mindestens so weit beherrschen, dass man in ihr Aussagen beweisen kann …

September 2017

Dieser Artikel ist enthalten in Spektrum der Wissenschaft September 2017

Lesermeinung

4 Beiträge anzeigen

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Lesermeinungen können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

  • Quellen

Aaronson, S.: The 8000th Busy Beaver Number Eludes ZF Set Theory: New paper by Adam Yedidia and me. In: www.scottaaronson.com/blog/?m=201605, Mai 2016

Calude, C. S., Calude, E.: Evaluating the Complexity of Mathematical Problems. Part 1: Complex Systems 18, S. 267–285, 2009; Part 2: Complex Systems 18, S. 387–401, 2010

Marxen, H.: List of the Known Busy Beaver values, 2016

Michel, P.: The Busy Beaver Competition: A Historical Survey, 2009

Soler-Toscano, F. et al.: Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines. In: PLoS One 8, e96223, 2014

Yedidia, A., Aaronson, S.: A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory, 2016