Beräkningsbart tal

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2017-12) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Inom matematik och beräkningsteori är ett beräkningsbart tal ett reellt tal som kan beräknas med en ändlig algoritm. Närmare bestämt är ett tal a beräkningsbart om det finns ett program som, givet ett godtyckligt noggrannhetskrav ε > 0 som indata, matar ut ett rationellt tal r för vilket

${\displaystyle |r-a|\leq \varepsilon .}$

Nästan alla reella tal är oberäkningsbara, en följd av att mängden av alla algoritmer är uppräknelig medan mängden av reella tal är ouppräknelig. Dock utgör de beräkningsbara talen en algebraiskt sluten kropp, och nästan alla tal som förekommer i matematik i praktiken är beräkningsbara (däribland alla algebraiska tal och även vanligt förekommande transcendenta tal som e och π). Det är tänkbart att större delen av den matematiska analysen skulle kunna konstrueras enbart med hjälp av beräkningsbara tal.

Alla beräkningsbara tal är definierbara, men omvändningen gäller inte. Ett exempel på ett definierbart men oberäkningsbart tal är Chaitins konstant.