De kortste samenvatting
Zo kunnen we al meteen bewijzen dat er geen programma bestaat dat de kortste samenvatting van een tekst geeft, of zelfs maar de lengte van die kortste samenvatting. Immers, stel dat we dat programma, onder de naam „MinimumGrootte”, wel zouden hebben. Dan zou ik ook het volgende programma kunnen schrijven:
- LengteMeerDan N Tekst:
- Als (MinimumGrootte Tekst) > N), Produceer Ja;
- Anders Produceer Neen.
- TekstGroterDan N:
- Produceer TekstMet (LengteMeerDan N)
Daar lijkt nog niets mis mee, maar nu kunnen we ook dit schrijven.
- Tegenspraak:
- Produceer TekstGroterDan Grootte.
Hierbij kiezen we het getal Grootte zo, dat het groter is dan de lengte van al deze programmaatjes (MinimumGrootte + LengteMeerDan + TekstGroterDan + Tegenspraak) bij elkaar. Natuurlijk komt Grootte zelf voor in Tegenspraak, maar omdat het maar de logarithme aan tekens kost om dat getal op te schrijven kunnen we altijd een Grootte vinden die groot genoeg is.
Nu hebben we iets vreemds: een programma dat kleiner is dan Grootte, maar dat een tekst produceert waarvan de kortste samenvatting langer is dan Grootte. Maar dat programma is zelf een samenvatting van die tekst! Die tegenspraak bewijst dat de aanname (dat MinimumGrootte bestaat) onjuist is.
Informeel kunnen we hetzelfde zien in de paradoxꜛ van G.G.Berryꜛ: „Het kleinste natuurlijke getal dat niet in minder dan vijftien woorden omschreven kan worden”.