Número computable
En matemáticas, especialmente en ciencia computacional teórica y lógica matemática, los números computables o recursivos son los números reales que pueden ser computados con la precisión que se desee por un algoritmo finito.
Marvin Minsky definió los números que se van a calcular más o menos como lo hizo allá por 1936 Alan Turing, como "una secuencia de dígitos interpretada como fracciones decimales" entre 0 y 1: Las claves de esta definición son: (1) se especifica n al principio, y (2) el cálculo tiene un número finito de pasos para cualquier n, después del cual la máquina produce el resultado deseado y termina.
Aun así, esta no es la definición formal y moderna, que únicamente requiere que el resultado sea preciso dado cualquier grado de precisión.
La definición informal está sujeta a un problema de redondeo mientras que la moderna no.
, la función produce un número entero k tal que: Hay dos definiciones similares que son equivalentes: Existe aún otra definición de números computables mediante cortaduras de Dedekind.
, y cumplen las siguientes condiciones: Un ejemplo puede ser un programa D que define la raíz cúbica de 3.
se define: Un número real es computable si y solo si existe una cortadura de Dedekind D que converge con él.
Estas operaciones son computables uniformemente; por ejemplo, existe una máquina de Turing que con entrada (A,B,
La razón es la siguiente: supongamos que la máquina A mantenga como salida 0 como aproximación
Esta idea muestra que la máquina no es correcta para algunas de las secuencias si completa una función total.
Un problema similar ocurre cuando los reales computables se representan como cortaduras de Dedekind.
Ocurre lo mismo para la relación de igualdad: el test no es computable.
La cuestión es si es posible disponer del conjunto completo de reales y usar números computables para todas las operaciones matemáticas.
Esta idea es atractiva desde el punto de vista constructivista, y ha sido perseguida por lo que Errett Bishop y Richman llamaban la escuela rusa del constructivismo matemático.
Pera desarrollar el análisis con los números computables requiere tener cuidado en muchos aspectos específicos.
Encontramos esta dificultad si solamente consideramos secuencias que tienen un módulo de convergencia computable.
