Número Computable

Es un número real con una sucesión de dígitos potencialmente infinita, pero también con una descripción finita, es decir, existe un algoritmo que lo calcula:

 

Tomando n como entrada, produce el enésimo dígito an, con un número finito de pasos, (tiene una complejidad de Kolmogórov finita). Por ejemplo: π, e, …

 

Por contra, un número no computable sería aquel que no tiene algoritmo que permita ver todos sus dígitos decimales, por ejemplo, el Ω de G. J. Chaitin.

 

La definición de Alan Turing es: «The computable numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means», frase contenida en la descripción de su máquina. También se puede definir como:

 

Un número real es computable si y sólo si hay un corte «D» Dedekind computable convergiendo a él.

 

Números computables son todos los:

La mayoría de los irracionales no son computables.

Un número complejo se denomina computable si sus partes real e imaginaria son computables.