Chaitin's constante is een voorbeeld (eigenlijk een familie van voorbeelden) van een niet-berekenbaar getal. Het staat voor de kans dat een willekeurig gegenereerd programma (in een bepaald model) stopt. Het kan bij benadering worden berekend, maar er is (aantoonbaar) geen algoritme om het met willekeurige precisie te berekenen.
Wat maakt een getal berekenbaar?
Een berekenbaar getal is een getal dat kan worden berekend door een eindig computerprogramma. Alle getallen waar je ooit van hebt gehoord, zoals 3, √2, π, e, etc. zijn berekenbaar. Sommige getallen (zoals π) worden weergegeven door een oneindige reeks niet-herhalende cijfers.
Wat betekent niet-berekenbaar?
Een niet-berekenbaar is een probleem waarvoor er geen algoritme is dat kan worden gebruikt om het op te lossen. Het bekendste voorbeeld van een niet-berekenbaarheid (of onbeslisbaarheid) is het stopprobleem.
Bestaan er niet-berekenbare getallen?
Er bestaan niet alleen niet-berekenbare getallen, ze zijn in feite veel overvloediger dan berekenbare getallen. Vele, vele reële getallen zijn gewoon oneindige reeksen van schijnbaar willekeurige cijfers, zonder patroon of speciale eigenschap. … Neem als voorbeeld een getal waarvan het deel vóór de komma 0 is.
Zijn de echte getallen berekenbaar?
Een reëel getal is berekenbaar als en slechts dan als de verzameling natuurlijke getallen die het vertegenwoordigt (wanneer geschreven in binair en gezien als een karakteristieke functie) berekenbaar is. Elke berekenbaregetal is rekenkundig.