Beregnelige tal

Et beregneligt tal er et tal der kan beregnes med en given præcision af en 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æ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.