Sein Hauptarbeitsgebiet ist die Berechenbarkeitstheorie. Er steht damit in der Tradition von Kurt Gödel und Alan Turing, deren Theoreme (Unvollständigkeitssatz, Turing-Berechenbarkeit) er zur Algorithmischen Informationstheorie verallgemeinert, auch bekannt als Theorie der Kolmogorov-Komplexität.

Seine Ergebnisse betreffen die Struktur mathematischer Theorien. Er sucht Aussagen zur prinzipiellen Berechenbarkeit und zur prinzipiellen Entscheidbarkeit mathematischer Sätze.

Eine seiner zentralen Schlussfolgerungen ist, dass unendlich viele mathematische Sätze prinzipiell unentscheidbar sind. Es ist 'zufällig', ob ein Satz wahr oder falsch ist.

Seine komplexen Ergebisse werden oft schlagwortartig vereinfacht:

"Ein Beweis, dass die Arithmetik im innersten zufällig ist."

Populäre Veröffentlichungen

The Limits of Mathematics, Springer-Verlag, 1998.

The Unknowable, Springer-Verlag, 1999.

Exploring Randomness, Springer-Verlag, 2001.

Conversations with a Mathematician, Springer-Verlag, 2002.