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. Se puede llegar al mismo resultado utilizando funciones recursivas, Máquinas de Turing o cálculo-λ.
Marvin Minsky define 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.
Una forma diferente de decir (2) podría ser que la máquina escribe sucesivamente todos los dígitos en la cinta y para con el n-ésimo dígito, y esta definición enfatiza la observación de Minsky: (3) utilizando una Máquina de Turing se da una definición finita de lo que es potencialmente una cadena infinita de dígitos decimales.
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.
Un número real a es computable si se puede dar una aproximación de él mediante una función computable de la siguiente forma: dado cualquier número entero , 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. Una cortadura de Dedekind computable es una función computable que, proporcionado un número racional como entrada, devuelve ó , y cumplen las siguientes condiciones:
Un ejemplo puede ser un programa D que define la raíz cúbica de 3. Asumiendo se define:
Un número real es computable si y solo si existe una cortadura de Dedekind D que converge con él. La función D es única para cada número computable irracional (aunque dos programas diferentes puedan dar la misma función).
Un número complejo es computable si sus partes real e imaginaria son ambas computables.
Aunque el conjunto de números reales es un conjunto no numerable, el conjunto de números computables es numerable y, por tanto, la mayoría de números reales no son computables. Los números computables pueden ser contados asignando una numeración de Gödel a cada definición de máquina de Turing. Aunque los números computables están ordenados, el conjunto de números de Gödel correspondiente no es un conjunto recursivamente enumerable, porque no es posible determinar qué números de Gödel corresponden a las máquinas de Turing que producen los reales computables. Para producir un real computable, una máquina de Turing debe calcular una función total, pero el problema de decisión tiene un grado de Turing 0′′. Por lo tanto, no puede utilizarse la diagonalización de Cantor para producir reales computables; como mucho, los reales formados con este método serán no-computables.
Los resultados de las operaciones aritméticas de números computables son también computables con los números reales a y b de la siguiente forma: a+b, a-b, ab y a/b si b ≠ 0. Estas operaciones son computables uniformemente; por ejemplo, existe una máquina de Turing que con entrada (A,B,) produce la salida r, donde A es la descripción de una máquina de Turing que aproxima el número a, B es la descripción de una máquina de Turing que aproxima el número b y r es una aproximación de a+b.
No todos los números reales computables comparten todas las propiedades de los números reales explicadas en el análisis. Por ejemplo, la cota superior mínima de una sucesión computable acotada creciente de números reales computables no tiene por qué ser un número real computable (Bridges and Richman, 1987:58). Una secuencia con esta propiedad se conoce como secuencia Specker. A pesar de contraejemplos como este, se pueden desarrollar partes de cálculo y análisis real en el campo de los números computables utilizando análisis computable.
La relación de orden en los números computables no es computable. No existe una máquina de Turing que con entrada A (la descripción de una máquina de Turing que aproxima el número a) tenga como salida "SI" si y "NO" si . La razón es la siguiente: supongamos que la máquina A mantenga como salida 0 como aproximación . No está claro cuánto tiempo hay que esperar antes de decidir que la máquina nunca dará una salida que fuerce a a a ser positivo. Por lo tanto, la máquina tendrá que adivinar que el número es 0 para poder dar una salida; más tarde, esta secuencia puede ser distinta de 0. 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.
Si bien la relación de orden total no es computable, su restricción a los pares de números desiguales es computable. Esto es, existe un programa tal que toma como entrada dos máquinas de Turing A y B que aproximan los números a y b, y a≠b, y que dé como resultado a<b o a>b. Es suficiente utilizar aproximaciones ε donde ε<|b-a|/2; tomando cada vez una ε más pequeña (con límite 0), se puede decidir si a<b o a>b.
Todo número computable es un número real definible, pero no a la inversa. Hay varios números reales definibles pero no computables, incluyendo:
Un número real es computable si y solo si el conjunto de números naturales que representa (cuando está escrito en binario y es vista como una función característica) es computable.
Los números computables incluyen muchos de los números reales, incluyendo todos los números algebraicos, así como e, y otros números trascendentes. Aunque los computables reales agotan todos los reales que podemos calcular o aproximar, la suposición de que todos los números reales son computables conduce a conclusiones muy diferentes acerca de los números reales. 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.
Para desarrollar análisis con los números computables hay que hacerlo con cuidado. Por ejemplo, si se usa la definición clásica de una secuencia, el conjunto de números computables no está cerrado bajo la operación básica de tomar el supremo de una secuencia limitada (considérese la secuencia Specker). Encontramos esta dificultad si solamente consideramos secuencias que tienen un módulo de convergencia computable. La teoría matemática resultante se denomina análisis computable.
Los números computables fueron definidos independientemente por Turing, Post y Church. Véase The Undecidable, ed. Martin Davis, para más datos.