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: ?, ?2, 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.