Stopt dit programma?
Sommige programma's stoppen, andere blijven eeuwig doorlopen, en dat hangt ook van de invoer af. Zo stopt het volgende programma voor enkelcijferige invoer, maar niet voor getallen boven de tien.
- Klein Getal:
- Als het Getal 10 is, stop dan;
- Doe anders Klein met Getal plus 1.
Het zou natuurlijk fijn zijn als we konden weten of een programma uiteindelijk zal stoppen, maar helaas is er geen programma dat ons dat kan vertellen. Stel dat zo'n programma, „EindigheidVan”, wel bestond, en ons kon vertellen of een bepaald programma met bepaalde invoer al dan niet zou stoppen. „EindigheidVan Klein 5” zou dan „ja” opleveren, en „EindigheidVan Klein 15” „neen”. Maar dan zouden we het volgende kunnen doen.
- Pervers Programma:
- Als (EindigheidVan Programma Programma), doe dan Klein 15;
- Stop anders.
Dit programma stopt precies dan, wanneer het Programma, als het zichzelf als invoer krijgt, niet zou stoppen. En daarmee krijgen we eenvoudig een tegenspraak.
- Tegenspraak:
- Doe Pervers Pervers.
Het programma Tegenspraak stopt precies dan als het niet stopt.
((Toevoegen: dit betekent niet dat we programma's niet correct kunnen bewijzen: een goede programmeur ontwikkelt een correctheidsbewijs samen met zijn programma, en de theorie kan dat bewijs controleren. Zo is bijvoorbeeld de software voor de ondergrondse in Parijs correct bewezen.))