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.

Definition

Oprindeligt var et beregneligt tal defineret som et tal, hvis n'te ciffer kunne komputeres af en algoritme, som kan komputeres af en Turing-maskine.

I dag definerer vi et beregneligt tal sådan: Et reelt tal, a, er beregneligt, hvis tallet kan blive approksimeret af en beregnelig funktion $f:\mathbb {N} \to \mathbb {Z}$, som opfylder ${f(n)-1 \over n}\leq a\leq {f(n)+1 \over n}$ for alle n ϵ N

Kilder

• Oliver Aberth 1968, Analysis in the Computable Number Field, Journal of the Association for Computing Machinery (JACM), vol 15, iss 2, pp 276–299.