La constant de Chaitin és un exemple (en realitat una família d'exemples) d'un nombre no computable. representa la probabilitat que un programa generat aleatòriament (en un model determinat) s'atura. Es pot calcular aproximadament, però no hi ha (de provable) cap algorisme per calcular-lo amb precisió arbitrària.
Què fa que un nombre sigui computable?
Un nombre computable és un nombre que es pot calcular mitjançant un programa informàtic finit. Tots els nombres dels quals heu sentit a parlar, com ara 3, √2, π, e, etc. són computables. Alguns nombres (com ara π) es representen per una cadena infinita de dígits que no es repeteixen.
Què vol dir no computable?
Un no computable és un problema per al qual no hi ha cap algorisme que es pugui utilitzar per resoldre'l. L'exemple més famós de no-computabilitat (o indecidibilitat) és el problema de l'aturada.
Existen números no computables?
No només existeixen els nombres no computables, sinó que de fet són molt més abundants que els números computables. Molts, molts nombres reals són simplement seqüències infinites de dígits aparentment aleatoris, sense patró ni propietat especial. … Com a exemple, considereu un nombre la part del qual abans del punt decimal és 0.
Els nombres reals són computables?
Un nombre real és computable si i només si el conjunt de nombres naturals que representa (quan s'escriu en binari i es veu com una funció característica) és computable. Cada computableel nombre és aritmètic.
