Wenn ein mathematisches Problem einfach aussieht, wie die Frage "Ist 4n⁴+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 n^q + m^q = p^q 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 ...