Número computable

Número real que se puede calcular con precisión arbitraria.

π se puede calcular con precisión arbitraria, mientras que casi todos los números reales no son computables.

En matemáticas , los números computables son los números reales que pueden calcularse con cualquier precisión deseada mediante un algoritmo finito y de terminación . También se conocen como números recursivos , ^[1] números efectivos ^[2] o reales computables ^[3] o reales recursivos . ^[4] El concepto de número real computable fue introducido por Émile Borel en 1912, utilizando la noción intuitiva de computabilidad disponible en ese momento. ^[5]

Se pueden dar definiciones equivalentes utilizando funciones μ-recursivas , máquinas de Turing o λ-cálculo como representación formal de algoritmos. Los números computables forman un cuerpo cerrado real y se pueden utilizar en lugar de números reales para muchos propósitos matemáticos, pero no todos.

Definición informal utilizando una máquina de Turing como ejemplo

A continuación, Marvin Minsky define los números a calcular de manera similar a los definidos por Alan Turing en 1936; ^[6] es decir, como "secuencias de dígitos interpretadas como fracciones decimales" entre 0 y 1: ^[7]

Un número computable es aquel para el cual existe una máquina de Turing que, dado n en su cinta inicial, termina con el n- ésimo dígito de ese número [codificado en su cinta].

Las nociones clave en la definición son (1) que algún n se especifica al inicio, (2) para cualquier n el cálculo solo toma un número finito de pasos, después de los cuales la máquina produce el resultado deseado y termina.

Una forma alternativa de (2) –la máquina imprime sucesivamente todos los n dígitos de su cinta, deteniéndose después de imprimir el n -ésimo– enfatiza la observación de Minsky: (3) que mediante el uso de una máquina de Turing, se utiliza una definición finita –en la forma de la tabla de estados de la máquina– para definir lo que es una cadena potencialmente infinita de dígitos decimales.

Sin embargo, esta no es la definición moderna, que solo exige que el resultado sea preciso dentro de un margen de precisión determinado. La definición informal anterior está sujeta a un problema de redondeo llamado el dilema del fabricante de tablas, mientras que la definición moderna no lo está.

Definición formal

Un número real a es computable si puede aproximarse mediante alguna función computable de la siguiente manera: dado cualquier entero positivo n , la función produce un entero f ( n ) tal que: ${\displaystyle f:\mathbb {N} \to \mathbb {Z} }$

${\displaystyle {f(n)-1 \over n}\leq a\leq {f(n)+1 \over n}.}$

Hay dos definiciones similares que son equivalentes:

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

Existe otra definición equivalente de números computables a través de cortes de Dedekind computables . Un corte de Dedekind computable es una función computable que, cuando se le proporciona un número racional como entrada, devuelve o , que satisface las siguientes condiciones: ${\displaystyle D\;}$ ${\displaystyle r}$ ${\displaystyle D(r)=\mathrm {true} \;}$ ${\displaystyle D(r)=\mathrm {false} \;}$

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

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

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

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

Un ejemplo lo da un programa D que define la raíz cúbica de 3. Suponiendo que esto está definido por: ${\displaystyle q>0\;}$

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

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

Un número real es computable si y sólo si existe un corte de Dedekind computable D correspondiente a él. La función D es única para cada número computable (aunque, por supuesto, dos programas diferentes pueden proporcionar la misma función).

Un número complejo se llama computable si sus partes reales e imaginarias son computables.

Propiedades

No computablemente enumerable

La asignación de un número de Gödel a cada definición de máquina de Turing produce un subconjunto de los números naturales correspondientes a los números computables e identifica una sobreyección de a los números computables. Solo hay un número contable de máquinas de Turing, lo que demuestra que los números computables son subcontables . Sin embargo, el conjunto de estos números de Gödel no es computablemente enumerable (y, en consecuencia, tampoco lo son los subconjuntos de que se definen en términos de él). Esto se debe a que no hay un algoritmo para determinar qué números de Gödel corresponden a las máquinas de Turing que producen números reales computables. Para producir un real computable, una máquina de Turing debe calcular una función total , pero el problema de decisión correspondiente está en el grado de Turing 0′′ . En consecuencia, no hay una función computable sobreyectiva de los números naturales al conjunto de máquinas que representan números reales computables, y el argumento diagonal de Cantor no se puede utilizar de forma constructiva para demostrar un número incontable de ellas. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

Mientras que el conjunto de los números reales es incontable , el conjunto de los números computables es clásicamente contable y, por lo tanto, casi todos los números reales no son computables. Aquí, para cualquier número computable dado, el principio de buen orden establece que hay un elemento mínimo en el que corresponde a , y por lo tanto existe un subconjunto que consiste en los elementos mínimos, en el que la función es una biyección . La inversa de esta biyección es una inyección en los números naturales de los números computables, lo que demuestra que son contables. Pero, de nuevo, este subconjunto no es computable, aunque los reales computables estén ordenados. ${\displaystyle x,}$ ${\displaystyle S}$ ${\displaystyle x}$

Propiedades como campo

Las operaciones aritméticas sobre números computables son en sí mismas computables en el sentido de que siempre que los números reales a y b sean computables, entonces los siguientes números reales también lo serán: a + b , a - b , ab y a/b si b es distinto de cero. Estas operaciones son en realidad computables de manera uniforme ; por ejemplo, hay una máquina de Turing que en la entrada ( A , B , ) produce la salida r , donde A es la descripción de una máquina de Turing que se aproxima a a , B es la descripción de una máquina de Turing que se aproxima a b , y r es una aproximación de a + b . ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$

El hecho de que los números reales computables forman un campo fue demostrado por primera vez por Henry Gordon Rice en 1954. ^[8]

Sin embargo, los reales computables no forman un campo computable, porque la definición de un campo computable requiere igualdad efectiva.

No computabilidad del ordenamiento

La relación de orden en los números computables no es computable. Sea A la descripción de una máquina de Turing que aproxima el número . Entonces no hay ninguna máquina de Turing que en la entrada A dé como salida "SÍ" si y "NO" si Para ver por qué, supongamos que la máquina descrita por A sigue dando como salida 0 como aproximaciones. No está claro cuánto tiempo esperar antes de decidir que la máquina nunca dará como salida una aproximación que fuerce a a ser positivo. Por lo tanto, la máquina eventualmente tendrá que adivinar que el número será igual a 0, para producir una salida; la secuencia puede luego volverse diferente de 0. Esta idea puede usarse para mostrar que la máquina está equivocada en algunas secuencias si calcula una función total. Un problema similar ocurre cuando los reales computables se representan como cortes de Dedekind . Lo mismo se aplica a la relación de igualdad: la prueba de igualdad no es computable. ${\displaystyle a}$ ${\displaystyle a>0}$ ${\displaystyle a\leq 0.}$ ${\displaystyle \epsilon }$

Si bien la relación de orden completa no es computable, la restricción de la misma a pares de números desiguales sí lo es. Es decir, hay un programa que toma como entrada dos máquinas de Turing A y B que aproximan números y , donde , y da como salida si o Es suficiente usar aproximaciones - donde entonces al tomar valores cada vez más pequeños (acercándose a 0), uno puede eventualmente decidir si o ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\neq b}$ ${\displaystyle a<b}$ ${\displaystyle a>b.}$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon <|b-a|/2,}$ ${\displaystyle \epsilon }$ ${\displaystyle a<b}$ ${\displaystyle a>b.}$

Otras propiedades

Los números reales computables no comparten todas las propiedades de los números reales utilizados en el análisis. Por ejemplo, el límite superior mínimo de una secuencia computable creciente acotada de números reales computables no necesita ser un número real computable. ^[9] Una secuencia con esta propiedad se conoce como secuencia de Specker , ya que la primera construcción se debe a Ernst Specker en 1949. ^[10] A pesar de la existencia de contraejemplos como estos, partes del cálculo y el análisis real se pueden desarrollar en el campo de los números computables, lo que conduce al estudio del análisis computable .

Todo número computable es definible aritméticamente , pero no viceversa. Hay muchos números reales no computables y definibles aritméticamente, entre ellos:

• cualquier número que codifique la solución del problema de detención (o cualquier otro problema indecidible ) según un esquema de codificación elegido.
• La constante de Chaitin , , que es un tipo de número real que es equivalente de Turing al problema de parada. ${\displaystyle \Omega }$

De hecho, ambos ejemplos definen un conjunto infinito de números definibles e incomputables, uno para cada máquina universal de Turing . Un número real es computable si y solo si el conjunto de números naturales que representa (cuando se escribe en binario y se ve como una función característica) es computable.

El conjunto de números reales computables (así como cada subconjunto contable y densamente ordenado de números reales computables sin fines) es isomorfo en orden al conjunto de números racionales.

Cadenas de dígitos y espacios de Cantor y Baire

El artículo original de Turing definía los números computables de la siguiente manera:

Un número real es computable si su secuencia de dígitos puede ser generada por algún algoritmo o máquina de Turing. El algoritmo toma un número entero como entrada y genera el dígito -ésimo de la expansión decimal del número real como salida. ${\displaystyle n\geq 1}$ ${\displaystyle n}$

(La expansión decimal de a sólo se refiere a los dígitos que siguen al punto decimal).

Turing era consciente de que esta definición es equivalente a la definición de aproximación dada anteriormente. El argumento procede de la siguiente manera: si un número es computable en el sentido de Turing, entonces también es computable en el sentido: si , entonces los primeros n dígitos de la expansión decimal para a proporcionan una aproximación de a . Para el caso inverso, elegimos un número real computable a y generamos aproximaciones cada vez más precisas hasta que el n º dígito después del punto decimal sea seguro. Esto siempre genera una expansión decimal igual a a pero puede terminar incorrectamente en una secuencia infinita de 9, en cuyo caso debe tener una expansión decimal propia finita (y por lo tanto computable). ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$ ${\displaystyle n>\log _{10}(1/\epsilon )}$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$

A menos que ciertas propiedades topológicas de los números reales sean relevantes, a menudo es más conveniente tratar con elementos de (funciones con valores totales de 0,1) en lugar de números reales en . Los miembros de pueden identificarse con expansiones decimales binarias, pero dado que las expansiones decimales y denotan el mismo número real, el intervalo solo puede identificarse biyectivamente (y homeomórficamente bajo la topología de subconjuntos) con el subconjunto de que no termina en todos los 1. ${\displaystyle 2^{\omega }}$ ${\displaystyle [0,1]}$ ${\displaystyle 2^{\omega }}$ ${\displaystyle .d_{1}d_{2}\ldots d_{n}0111\ldots }$ ${\displaystyle .d_{1}d_{2}\ldots d_{n}10}$ ${\displaystyle [0,1]}$ ${\displaystyle 2^{\omega }}$

Obsérvese que esta propiedad de las expansiones decimales significa que es imposible identificar eficazmente los números reales computables definidos en términos de una expansión decimal y aquellos definidos en el sentido de aproximación. Hirst ha demostrado que no existe ningún algoritmo que tome como entrada la descripción de una máquina de Turing que produzca aproximaciones para el número computable a y produzca como salida una máquina de Turing que enumere los dígitos de a en el sentido de la definición de Turing. ^[11] De manera similar, significa que las operaciones aritméticas sobre los números reales computables no son efectivas sobre sus representaciones decimales como cuando se suman números decimales. Para producir un dígito, puede ser necesario mirar arbitrariamente hacia la derecha para determinar si hay un acarreo a la ubicación actual. Esta falta de uniformidad es una de las razones por las que la definición contemporánea de números computables utiliza aproximaciones en lugar de expansiones decimales. ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$

Sin embargo, desde una perspectiva de teoría de la computabilidad o de la medición , las dos estructuras y son esencialmente idénticas. Por lo tanto, los teóricos de la computabilidad a menudo se refieren a los miembros de como reales. Si bien está totalmente desconectado , para preguntas sobre clases o aleatoriedad es más fácil trabajar en . ${\displaystyle 2^{\omega }}$ ${\displaystyle [0,1]}$ ${\displaystyle 2^{\omega }}$ ${\displaystyle 2^{\omega }}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle 2^{\omega }}$

Los elementos de a veces también se denominan reales y, aunque contienen una imagen homeomórfica de , ni siquiera son localmente compactos (además de estar totalmente desconectados). Esto conduce a diferencias genuinas en las propiedades computacionales. Por ejemplo, el satisfactorio , con cuantificador libre, debe ser computable mientras que el único que satisface una fórmula universal puede tener una posición arbitrariamente alta en la jerarquía hiperaritmética . ${\displaystyle \omega ^{\omega }}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \omega ^{\omega }}$ ${\displaystyle x\in \mathbb {R} }$ ${\displaystyle \forall (n\in \omega )\phi (x,n)}$ ${\displaystyle \phi (x,n)}$ ${\displaystyle x\in \omega ^{\omega }}$

Usar en lugar de los reales

Los números computables incluyen los números reales específicos que aparecen en la práctica, incluidos todos los números algebraicos reales , así como e , π y muchos otros números trascendentales . Aunque los reales computables agotan aquellos reales que podemos calcular o aproximar, la suposición de que todos los reales son computables conduce a conclusiones sustancialmente diferentes sobre los números reales. Naturalmente, surge la pregunta de si es posible deshacerse del conjunto completo de reales y usar números computables para todas las matemáticas. Esta idea es atractiva desde un punto de vista constructivista y ha sido perseguida por la escuela rusa de matemáticas constructivas. ^[12]

Para desarrollar realmente el análisis sobre números computables, se deben tomar ciertas precauciones. Por ejemplo, si se utiliza 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 acotada (por ejemplo, considere una secuencia de Specker , consulte la sección anterior). Esta dificultad se soluciona considerando solo secuencias que tienen un módulo de convergencia computable . La teoría matemática resultante se llama análisis computable .

Implementaciones de aritmética exacta

Ya en 1985 se propusieron paquetes informáticos que representan números reales como programas que calculan aproximaciones, bajo el nombre de "aritmética exacta". ^[13] Algunos ejemplos modernos son la biblioteca CoRN (Coq), ^[14] y el paquete RealLib (C++). ^[15] Una línea de trabajo relacionada se basa en tomar un programa RAM real y ejecutarlo con números racionales o de punto flotante de precisión suficiente, como el paquete iRRAM. ^[16]

Véase también

• Número construible
• Número definible
• Función semicomputable
• Problema transcomputacional

Notas

1. Mazur, Estanislao (1963). Grzegorczyk, Andrzej ; Rasiowa, Helena (eds.). Análisis computable. Rozprawy Matematyczne. vol. 33. Instituto de Matemáticas de la Academia Polaca de Ciencias . pag. 4.
2. van der Hoeven (2006).
3. Pour-El, Marian Boykan ; Richards, Ian (1983). "No computabilidad en análisis y física: una determinación completa de la clase de operadores lineales no computables". Avances en Matemáticas . 48 (1): 44–74. doi : 10.1016/0001-8708(83)90004-X . MR  0697614.
4. Rogers, Hartley, Jr. (1959). "La teoría actual de la computabilidad de la máquina de Turing". Revista de la Sociedad de Matemáticas Industriales y Aplicadas . 7 : 114–130. MR  0099923.{{cite journal}}: CS1 maint: multiple names: authors list (link)
5. P. Odifreddi, Teoría de la recursión clásica (1989), pág. 8. Holanda del Norte, 0-444-87295-7
6. Turing (1936).
7. Minski (1967).
8. Arroz (1954).
9. Bridges y Richman (1987), pág. 58.
10. Edgar García (1949).
11. Hirst (2007).
12. Kushner, Boris A. (2006). "Las matemáticas constructivas de AA Markov". The American Mathematical Monthly . 113 (6): 559–566. doi :10.2307/27641983. MR  2231143.
13. Boehm, Hans-J.; Cartwright, Robert; Riggle, Mark; O'Donnell, Michael J. (8 de agosto de 1986). "Aritmética real exacta: un estudio de caso en programación de orden superior" (PDF) . Actas de la conferencia ACM de 1986 sobre LISP y programación funcional - LFP '86 . págs. 162-173. doi :10.1145/319838.319860. ISBN . 0897912004. S2CID  12934546. Archivado (PDF) del original el 24 de septiembre de 2020.
14. O'Connor, Russell (2008). "Cálculo exacto certificado de números reales trascendentales en Coq". Demostración de teoremas en lógica de orden superior . Apuntes de clase en informática. Vol. 5170. págs. 246–261. arXiv : 0805.2438 . doi :10.1007/978-3-540-71067-7_21. ISBN 978-3-540-71065-3.S2CID 17959745  .
15. Lambov (2015).
16. Gowland, Paul; Lester, David (2001). "Un estudio de las implementaciones aritméticas exactas" (PDF) . Computabilidad y complejidad en el análisis . Apuntes de clase en informática. Vol. 2064. Springer. págs. 30–47. doi :10.1007/3-540-45335-0_3. ISBN. 978-3-540-42197-9. Archivado (PDF) del original el 24 de marzo de 2022.

Referencias

• Bridges, Douglas; Richman, Fred (1987). Variedades de matemáticas constructivas. Cambridge University Press. ISBN 978-0-521-31802-0.
• Hirst, Jeffry L. (2007). "Representaciones de números reales en matemáticas inversas". Boletín de la Academia Polaca de Ciencias, Matemáticas . 55 (4): 303–316. doi : 10.4064/ba55-4-2 .
• Lambov, Branimir (5 de abril de 2015). "RealLib". GitHub.
• Minsky, Marvin (1967). "9. Los números reales computables". Computación: máquinas finitas e infinitas . Prentice-Hall. ISBN 0-13-165563-9.OCLC 0131655639  .
• Rice, Henry Gordon (1954). "Números reales recursivos". Actas de la American Mathematical Society . 5 (5): 784–791. doi : 10.1090/S0002-9939-1954-0063328-5 . JSTOR  2031867.
• Specker, E. (1949). "Nicht konstruktiv beweisbare Sätze der Analysis" (PDF) . Revista de Lógica Simbólica . 14 (3): 145-158. doi :10.2307/2267043. JSTOR  2267043. S2CID  11382421. Archivado (PDF) desde el original el 21 de julio de 2018.
• Turing, AM (1936). "Sobre números computables, con una aplicación al problema de Entscheidung". Actas de la London Mathematical Society . Serie 2. 42 (1) (publicado en 1937): 230–65. doi :10.1112/plms/s2-42.1.230. S2CID  73712.
  Turing, AM (1938). "Sobre números computables, con una aplicación al problema de Entscheidung: una corrección". Actas de la London Mathematical Society . Serie 2. 43 (6) (publicado en 1937): 544–6. doi :10.1112/plms/s2-43.6.544.En este artículo se introdujeron los números computables (y las máquinas A de Turing); la definición de números computables utiliza secuencias decimales infinitas.
• van der Hoeven, Joris (2006). "Cálculos con números reales efectivos". Ciencias de la Computación Teórica . 351 (1): 52–60. doi : 10.1016/j.tcs.2005.09.060 .

Lectura adicional

• Aberth, Oliver (1968). "Análisis en el campo numérico computable". Revista de la Asociación de Maquinaria Computacional . 15 (2): 276–299. doi : 10.1145/321450.321460 . S2CID  18135005.Este artículo describe el desarrollo del cálculo sobre el cuerpo de números computables.
• Obispo, Errett; Puentes, Douglas (1985). Análisis constructivo . Saltador. ISBN 0-387-15066-8.
• Stoltenberg-Hansen, V.; Tucker, JV (1999). "Anillos y campos computables". En Griffor, ER (ed.). Manual de teoría de la computabilidad . Elsevier. págs. 363–448. ISBN 978-0-08-053304-9.
• Weihrauch, Klaus (2000). Análisis computable . Textos de Informática Teórica. Saltador. ISBN 3-540-66817-9.El §1.3.2 introduce la definición mediante secuencias anidadas de intervalos que convergen al real unitario. Otras representaciones se analizan en el §4.1.
• Weihrauch, Klaus (1995). Una sencilla introducción al análisis computable. Fernuniv., Fachbereich Informatik.