Beregnelige tal: Forskelle mellem versioner

Et '''beregnelige tal''' er et tal der kan beregnes med en givet præcision af en endende [[algoritme]], som kan beregnes af en [[Turing-maskine]]. Eksempler på beregnelige tal er e, π, √2 og 1. Alle tal som kan skrives som en [[sum]] er beregnelige.

Selvom [[mængden]] af [[reelle tal]] er [[overtællelig]] er mængden af beregnelige tal [[tællelighed|tællelige]] (samme [[kardinalitet]] som de naturlige tals mængde), da enhver beregnelig algoritme kan gives et unikt [[naturligt tal]] (f.eks. et kompileret program), og hver algoritme, der giver et nyt resultat, kan gives et nyt naturligt tal.