De meeste reële getallen zijn niet berekenbaar

Aan de andere kant kunnen echte getallen niet worden berekend. Cantor kon dit in 1877 bewijzenDat de kardinaliteit van reële getallen noodzakelijkerwijs groter is dan die van natuurlijke getallen: er is geen manier om alle reële getallen in een lijst op te sommen (ongeacht hun lengte) zonder enkele waarden weg te laten. Echte getallen vormen een ontelbare set. Zijn redenering ging als volgt: Stel dat je een complete lijst hebt van alle reële getallen. Dan kun je het zien als een tabel, elke rij heeft een nummer en elke kolom heeft een decimaal. Nu kunt u een nieuw reëel getal maken door één toe te voegen aan elke diagonale invoer in de tabel (het eerste getal in de eerste rij, het tweede getal in de tweede rij, enz.) en ze één voor één op te schrijven. Dit nieuwe nummer kan niet in de lijst worden opgenomen – de lijst is dus niet compleet.

Maar zoals Turing zei, alle berekenbare getallen moeten telbaar zijn: want voor elk van deze getallen kun je een machine ontwikkelen die alleen de waarde ervan berekent. Aangezien deze rekenmachines kunnen worden genummerd, zijn de getallen die kunnen worden geteld onvermijdelijk telbaar. Het gevolg hiervan is echter dat de onberekenbare getallen verreweg het grootste deel van de reële getallen uitmaken: er zijn er talloze!

Dus als je de waarschijnlijkheid berekent van het soort reëel getal dat je tegenkomt als je er willekeurig een kiest, krijg je een duidelijk resultaat: 100% van de tijd is dit getal onvoorspelbaar. Maar dat betekent niet dat je geen ander getal kunt kiezen – met oneindige combinaties van gebeurtenissen betekent nul waarschijnlijkheid niet dat het onmogelijk is. Dit is behoorlijk verbazingwekkend omdat we niet te veel getallen kennen om te tellen.

Het stopprobleem als inspiratie

De paar voorbeelden van niet-berekenbare getallen zijn speciaal voor dit doel gemaakt. De meeste methoden maken gebruik van het beroemde stopprobleem uit de informatica: volgens dit kan geen enkele machine beoordelen of de computer die het uitvoert uiteindelijk zal stoppen of niet, volgens alle mogelijke algoritmen. Als je een algoritme aan een computer overhandigt, kun je misschien beoordelen of het in een beperkte tijd kan worden uitgevoerd. Maar er is geen bewezen methode die dit voor alle mogelijke code kan doen. Het stopprobleem is een directe toepassing van Gödels stellingen van onvolledigheid, die stellen dat niet alle wiskundige beweringen bewezen kunnen worden.

De Argentijns-Amerikaanse wiskundige Gregory Chitin gebruikte het stopprobleem om een ​​onberekenbaar getal te definiëren. Dit wordt de constante Ω van Schitten genoemd De kans dat een theoretisch model van een computer (Turingmachine) stopt bij een gegeven input is gelijk aan: Ω = ∑_S½^|S|door S Hiermee stelt u in dat alle programma’s stoppen na de opgegeven looptijd. |S| Beschrijft de lengte van het programma in bits. Om de constante van Chaitin nauwkeurig te berekenen, moet men weten welke programma’s stoppen en welke niet – wat volgens het stopprobleem niet mogelijk is. Christian S. Claude en collega’s slaagden er echter in 2000 inOm de eerste cijfers van de constante van Chaitin te berekenen: 0,0157499939956247687… Dat wil zeggen, als je toevallig een programma bouwt in een taal die Calwood en zijn collega’s gebruikten, is er een kans van 1,58% dat het op een bepaald tijdstip wordt uitgevoerd. Zelfs als het resultaat een hoge mate van nauwkeurigheid heeft, kan de constante van Chaitin niet met enige mate van nauwkeurigheid worden berekend.

Een onverwacht nummer en een bezige bever

Een ander onberekenbaar getal komt voort uit de “busy beaver function” BB (N): Berekent de grootst mogelijke uitvoer (gemeten in bits) die het algoritme kan berekenen N kan bits genereren. Een onberekenbaar getal ontstaat bijvoorbeeld uit de volgende constructie: ∑_N½^{BB (N)}. Tot op heden zijn alleen de eerste vier waarden van de ijverige beverfunctie bekend en kunnen er nog minstens twee andere waarden worden geschat.