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-λ.

Definición informal utilizando Máquinas de Turing

Marvin Minsky define de 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:

"Un número computable [es] aquél para el que hay una máquina de Turing que, dado n en su cinta inicial, termina con el n-ésimo digito de ese número [codificado en esa cinta]." (Minsky 1967:159)

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 resultadeo sea preciso dado cualquier grado de precisión. La definición informal está sujeta a un problema de redondeo mientras que la moderna no.

Definición formal

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 $n \ge 1$, la función produce un número entero k tal que:

${k-1\over n} \leq a \leq {k+1\over n}$

Hay dos definiciones similares que son equivalentes:

• Existe una función computable que, dado cualquier márgen de error $\varepsilon$, produce un número racional r tal que $|r - a| \leq \varepsilon$
• Existe una secuencia computable de números racionales q_i que convergen en a tal que $|q_i - q_{i+1}| < 2^{-i}\,$ para cada i.

Existe aún otra definición de números computables mediante cortaduras de Dedekind. Una cortadura de Dadekind computable es una función computable $D\;$ que, proporcionado un número racional r como entrada, devuelve $D(r)=\mathrm{true}\;$ ó $D(r)=false\;$, y cumplen las siguientes condiciones:

$\exists r D(r)=\mathrm{true}\;$

$\exists r D(r)=\mathrm{false}\;$

$(D(r)=\mathrm{true}) \wedge (D(s)=\mathrm{false}) \Rightarrow r<s\;$

$D(r)=\mathrm{true} \Rightarrow \exist s>r, D(s)=\mathrm{true}\;$

Un ejemplo puede ser un programa D que define la raíz cúbica de 3. Asumiendo $q>0\;$ se define:

$p^3<3 q^3 \Rightarrow D(p/q)=\mathrm{true}\;$

$p^3>3 q^3 \Rightarrow D(p/q)=\mathrm{false}\;$

Un número real es computable si y sólo si existe una cortadura de Dadekind 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.

Propiedades

Aunque el conjunto de números reales es un conjunto no numerable, el conjunto de números computables es numberable 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,$\epsilon$) 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 $\epsilon$ 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 a > 0 y "NO" si $a \le 0$. La razón es la siguiente: supongamos que la máquina A mantenga como salida 0 como aproximación $\epsilon$. No está claro cuánto tiempo hay que esperar antes de decidir que la máquina nunca dara 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:

• La representación binaria del problema de la parada (o cualquier otro conjunto no computable de números naturales).
• La constante de Chaitin, Ω, que es un tipo de número real que es Turing equivalente al problema de la parada.

Un número real es computable si y sólo 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.

¿Pueden los números computables sustituir a los reales?

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 sólamente consideramos secuencias que tienen un módulo de convergencia computable. La teoría matemática resultante se denomina análisis computable.

Referencias

• Oliver Aberth 1968, Analysis in the Computable Number Field, Journal of the Association for Computing Machinery (JACM), vol 15, iss 2, pp 276–299. Describe el desarrollo del cálculo sobre los números computables.

• Errett Bishop y Douglas Bridges, Constructive Analysis, Springer, 1985, ISBN 0-387-15066-8

• Douglas Bridges y Fred Richman. Varieties of Constructive Mathematics, Oxford, 1987.

• Jeffry L. Hirst, Representations of reals in reverse mathematics, Bulletin of the Polish Academy of Sciences, Mathematics, 55, (2007) 303–316.

• Marvin Minsky 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, NJ. No ISBN. Library of Congress Card Catalog No. 67-12342. El capítulo §9 "The Computable Real Numbers" expande los temas de este artículo.

• E. Specker, "Nicht konstruktiv beweisbare Sätze der Analysis" J. Symbol. Logic , 14 (1949) pp. 145–158

• Turing, A.M. (1936), «On Computable Numbers, with an Application to the Entscheidungsproblem», Proceedings of the London Mathematical Society, 2 42 (1): 230–65, 1937, doi:10.1112/plms/s2-42.1.230, http://www.abelard.org/turpap2/tp2-ie.asp  (and Turing, A.M. (1938), «On Computable Numbers, with an Application to the Entscheidungsproblem: A correction», Proceedings of the London Mathematical Society, 2 43 (6): 544–6, 1937, doi:10.1112/plms/s2-43.6.544 ). Los números computables (y las máquinas de Turing) están en este documento; la definición de números computables usa secuencias infinitas de decimales.

• Klaus Weihrauch 2000, Computable analysis, habla de ciencias de la computación, Springer, ISBN 3-540-66817-9. El capítulo §1.3.2 introduce la definición mediante el principio de los intervalos encajados. También se habla de otras representaciónes en el capítulo §4.1.

• Klaus Weihrauch, A simple introduction to computable analysis

Los números computables fueron definidos independientemente por Turing, Post y Church. Véase The Undecidable, ed. Martin Davis, para más datos.