Hispanopedia Wiki
Articulo de referencia

Número computable

El número π se puede calcular con precisión arbitraria, mientras que casi ningún número real es computable. En matemáticas , los números computables son los números reales que p...

Hispanopedia WikiContenido en espanolLectura gratuita
El número π se puede calcular con precisión arbitraria, mientras que casi ningún número real es computable.

En matemáticas , los números computables son los números reales que pueden calcularse con la precisión deseada mediante un algoritmo finito y terminante . También se les conoce como números recursivos , [ 1 ] números efectivos , [ 2 ] 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 proporcionar definiciones equivalentes utilizando funciones μ-recursivas , máquinas de Turing o cálculo lambda como representación formal de algoritmos. Los números computables forman un cuerpo real cerrado y pueden utilizarse en lugar de números reales para muchos, aunque no todos, los propósitos matemáticos.

Definición informal

A continuación, Marvin Minsky define los números que se calcularán 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 se especifica algún n al principio, (2) para cualquier n el cálculo solo toma un número finito de pasos, después de los cuales la máquina produce la salida deseada y termina.

Una forma alternativa de (2) – la máquina imprime sucesivamente todos los n dígitos en 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 está utilizando una definición finita – en 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 se alcance un valor numérico con una precisión determinada. La definición informal anterior está sujeta a un problema de redondeo conocido como 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.F:norte→Z{\displaystyle f:\mathbb {N} \to \mathbb {Z} }De la siguiente manera: dado cualquier entero positivo n , la función produce un entero f ( n ) tal que:

F(norte)−1norte≤a≤F(norte)+1norte.{\displaystyle {f(n)-1 \over n}\leq a\leq {f(n)+1 \over n}.}

Un número complejo se denomina computable si sus partes real e imaginaria son computables.

Definiciones equivalentes

Existen dos definiciones similares que son equivalentes:

  • Existe una función computable que, dado cualquier límite de error racional positivoε{\displaystyle \varepsilon }, produce un número racional r tal que|r−a|≤ε.{\displaystyle |ra|\leq \varepsilon .}
  • Existe una secuencia computable de números racionales.qi{\displaystyle q_{i}}convergiendo aa{\displaystyle a}de tal manera que|qi−qi+1|<2−i{\displaystyle |q_{i}-q_{i+1}|<2^{-i}\,}para cada 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.D{\displaystyle D\;}que cuando se le proporciona un número racionalr{\displaystyle r}como retornos de entradaD(r)=trtúmi{\displaystyle D(r)=\mathrm {verdadero} \;}oD(r)=Falsmi{\displaystyle D(r)=\mathrm {falso} \;}que cumplan las siguientes condiciones:

∃rD(r)=trtúmi{\displaystyle \exists rD(r)=\mathrm {true} \;}
∃rD(r)=Falsmi{\displaystyle \exists rD(r)=\mathrm {false} \;}
(D(r)=trtúmi)∧(D(s)=Falsmi)⇒r<s{\displaystyle (D(r)=\mathrm {true} )\wedge (D(s)=\mathrm {false} )\Rightarrow r<s\;}
D(r)=trtúmi⇒∃s>r,D(s)=trtúmi.{\displaystyle D(r)=\mathrm {true} \Rightarrow \exists s>r,D(s)=\mathrm {true} .\;}

Un ejemplo lo proporciona un programa D que define la raíz cúbica de 3. Suponiendoq>0{\displaystyle q>0\;}Esto se define por:

pag3<3q3⇒D(pag/q)=trtúmi{\displaystyle p^{3}<3q^{3}\Rightarrow D(p/q)=\mathrm {verdadero} \;}
pag3>3q3⇒D(pag/q)=Falsmi.{\displaystyle p^{3}>3q^{3}\Rightarrow D(p/q)=\mathrm {false}.\;}

Un número real es computable si y solo si existe un corte de Dedekind computable D que le corresponda. La función D es única para cada número computable (aunque, por supuesto, dos programas diferentes pueden proporcionar la misma función).

Propiedades

No es enumerable computacionalmente

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

Si bien 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 dadoincógnita,{\displaystyle x,}El principio de ordenación del pozo establece que hay un elemento mínimo enS{\displaystyle S}que corresponde aincógnita{\displaystyle x}Por lo tanto, existe un subconjunto formado por los elementos mínimos, sobre el cual la aplicació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 numerables. Pero, de nuevo, este subconjunto no es computable, aunque los números reales computables estén ordenados.

Propiedades como un 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 son computables: a + b , a - b , ab y a / b si b es distinto de cero. Estas operaciones son en realidad uniformemente computables ; por ejemplo, hay una máquina de Turing que, con la entrada ( A , B ,ϵ{\displaystyle \epsilon }) produce la salida r , donde A es la descripción de una máquina de Turing que aproxima a , B es la descripción de una máquina de Turing que aproxima b , y r es unaϵ{\displaystyle \epsilon }aproximación de a + b .

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

Sin embargo, los números reales computables no forman un cuerpo computable , porque la definición de un cuerpo 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úmeroa{\displaystyle a}. Entonces no hay ninguna máquina de Turing que, con la entrada A, produzca "SÍ" sia>0{\displaystyle a>0}y "NO" sia≤0.{\displaystyle a\leq 0.}Para ver por qué, supongamos que la máquina descrita por A sigue produciendo 0 comoϵ{\displaystyle \epsilon }aproximaciones. No está claro cuánto tiempo esperar antes de decidir que la máquina nunca producirá una aproximación que obligue a que a sea 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 es incorrecta 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 sucede con la relación de igualdad: la prueba de igualdad no es computable.

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, existe un programa que toma como entrada dos máquinas de Turing A y B que aproximan números.a{\displaystyle a}yb{\displaystyle b}, dóndea≠b{\displaystyle a\neq b}y produce sia<b{\displaystyle a<b}oa>b.{\displaystyle a>b.}Es suficiente con usarϵ{\displaystyle \epsilon }-aproximaciones dondeϵ<|b−a|/2,{\displaystyle \epsilon <|b-a|/2,}así que tomando cantidades cada vez más pequeñasϵ{\displaystyle \epsilon }(acercándose a 0), uno finalmente puede decidir sia<b{\displaystyle a<b}oa>b.{\displaystyle a>b.}

Otras propiedades

Los números reales computables no comparten todas las propiedades de los números reales utilizados en análisis. Por ejemplo, la cota superior mínima de una sucesión computable creciente y acotada de números reales computables no tiene por qué ser un número real computable. [ 9 ] Una sucesión con esta propiedad se conoce como sucesión 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 del análisis real pueden desarrollarse en el campo de los números computables, lo que lleva al estudio del análisis computable .

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

Números no computables

Todo número computable es aritméticamente definible , pero no a la inversa. Existen muchos números reales aritméticamente definibles pero no computables, entre ellos:

Ambos ejemplos definen, de hecho, un conjunto infinito de números definibles pero no computables , uno por cada máquina de Turing universal . 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 considera como una función característica) es computable.

Cadenas de dígitos y los 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 producida por algún algoritmo o máquina de Turing. El algoritmo toma un número entero.norte≥1{\displaystyle n\geq 1}como entrada y produce elnorte{\displaystyle n}-ésimo dígito de la expansión decimal del número real como resultado.

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

Turing era consciente de que esta definición es equivalente a laϵ{\displaystyle \epsilon }-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 de Turing.ϵ{\displaystyle \epsilon }sentido: sinorte>registro10⁡(1/ϵ){\displaystyle n>\log _{10}(1/\epsilon )}, entonces los primeros n dígitos de la expansión decimal para a proporcionan unϵ{\displaystyle \epsilon }aproximación de a . Para lo contrario, elegimos unϵ{\displaystyle \epsilon }Se toma un número real computable a y se generan aproximaciones cada vez más precisas hasta que el enésimo dígito después del punto decimal sea cierto. Esto siempre genera una expansión decimal igual a a, pero puede terminar impropiamente en una secuencia infinita de 9, en cuyo caso debe tener una expansión decimal propia finita (y por lo tanto computable).

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

Tenga en cuenta que esta propiedad de las expansiones decimales significa que es imposible identificar de manera efectiva los números reales computables definidos en términos de una expansión decimal y aquellos definidos en laϵ{\displaystyle \epsilon }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ϵ{\displaystyle \epsilon }aproximaciones para el número computable a , y produce como salida una máquina de Turing que enumera 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 en sus representaciones decimales como cuando se suman números decimales. Para producir un dígito, puede ser necesario mirar arbitrariamente lejos a la derecha para determinar si hay un acarreo a la posición actual. Esta falta de uniformidad es una razón por la que la definición contemporánea de números computables utilizaϵ{\displaystyle \epsilon }aproximaciones en lugar de expansiones decimales.

Sin embargo, desde una perspectiva teórica de la computabilidad o de la medida , las dos estructuras2ω{\displaystyle 2^{\omega }}y[0,1]{\displaystyle [0,1]}son esencialmente idénticos. Por lo tanto, los teóricos de la computabilidad a menudo se refieren a los miembros de2ω{\displaystyle 2^{\omega }}como reales. Mientras2ω{\displaystyle 2^{\omega }}está totalmente desconectado , para preguntas sobreΠ10{\displaystyle \Pi _{1}^{0}}clases o aleatoriedad es más fácil trabajar en2ω{\displaystyle 2^{\omega }}.

Elementos deωω{\displaystyle \omega ^{\omega }}a veces también se les llama reales y aunque contienen una imagen homeomórfica deR{\displaystyle \mathbb {R} },ωω{\displaystyle \omega ^{\omega }}ni siquiera es localmente compacto (además de estar totalmente desconectado). Esto conlleva diferencias genuinas en las propiedades computacionales. Por ejemplo,incógnita∈R{\displaystyle x\in \mathbb {R} }satisfactorio∀(norte∈ω)ϕ(incógnita,norte){\displaystyle \forall (n\in \omega )\phi (x,n)}, conϕ(incógnita,norte){\displaystyle \phi (x,n)}cuantificador libre, debe ser computable mientras que el únicoincógnita∈ωω{\displaystyle x\in \omega ^{\omega }}Satisfacer una fórmula universal puede tener una posición arbitrariamente alta en la jerarquía hiperaritmética .

Utilizar 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. Surge naturalmente la pregunta de si es posible disponer del conjunto completo de los reales y utilizar números computables para todas las matemáticas. Esta idea resulta atractiva desde un punto de vista constructivista y ha sido desarrollada por la escuela rusa de matemáticas constructivas. [ 12 ]

Para desarrollar un análisis sobre números computables, es necesario tener cuidado. Por ejemplo, si se utiliza la definición clásica de sucesión, el conjunto de números computables no es cerrado bajo la operación básica de tomar el supremo de una sucesión acotada (por ejemplo, considérese una sucesión de Specker , véase la sección anterior). Esta dificultad se resuelve considerando únicamente sucesiones que tienen un módulo de convergencia computable . La teoría matemática resultante se denomina análisis computable .

Implementaciones de aritmética exacta

Desde 1985 se han propuesto paquetes informáticos que representan números reales como programas que calculan aproximaciones, bajo el nombre de "aritmética exacta". [ 13 ] Ejemplos modernos incluyen la biblioteca CoRN (Coq), [ 14 ] y el paquete RealLib (C++). [ 15 ] Una línea de trabajo relacionada se basa en tomar un programa de 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

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" . Advances in Mathematics . 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 las máquinas de Turing". Journal of the Society for Industrial and Applied Mathematics . 7 : 114–130 . doi : 10.1137/ 0107009.MR 0099923 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
  5. ↑ P. Odifreddi, Teoría clásica de la recursión (1989), pág. 8. North-Holland, 0-444-87295-7
  6. ↑ Turing (1936) .
  7. ↑ Minsky (1967) .
  8. ↑ Rice (1954) .
  9. ↑ Bridges y Richman (1987) , pág. 58.
  10. ↑ Specker (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 . JSTOR 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-09-2020. 
  14. ↑ O'Connor, Russell (2008). "Cálculo certificado exacto de números reales trascendentales en Coq". Demostración de teoremas en lógicas de orden superior . Lecture Notes in Computer Science. Vol. 5170. pp. 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 de aritmética exacta» (PDF) . Computabilidad y complejidad en el análisis . Notas de clase en ciencias de la computación. Vol. 2064. Springer. págs. 30–47 . doi : 10.1007/3-540-45335-0_3 . ISBN   978-3-540-42197-9Archivado (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-9OCLC 0131655639​​ 
  • Rice, Henry Gordon (1954). "Números reales recursivos" . Actas de la Sociedad Matemática Americana . 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 los números computables, con una aplicación al problema de decisión". Actas de la Sociedad Matemática de Londres . Serie 2. 42 (1) (publicado en 1937): 230– 65. doi : 10.1112/plms/s2-42.1.230 . S2CID 73712 . Turing, AM (1938). "Sobre los números computables, con una aplicación al problema de decisión: una corrección" . Actas de la Sociedad Matemática de Londres . 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" . Theoretical Computer Science . 351 (1): 52– 60. doi : 10.1016/j.tcs.2005.09.060 .

Lecturas adicionales

  • Aberth, Oliver (1968). "Análisis en el campo de números computables" . Journal of the Association for Computing Machinery . 15 (2): 276– 299. doi : 10.1145/321450.321460 . S2CID 18135005 . Este artículo describe el desarrollo del cálculo sobre el cuerpo de los números computables.
  • Bishop, Errett; Bridges, Douglas (1985). Análisis constructivo . Springer. ISBN 0-387-15066-8.
  • Stoltenberg-Hansen, V.; Tucker, JV (1999). «Anillos y cuerpos computables» . En Griffor, ER (ed.). Manual de teoría de la computabilidad . Elsevier. pp. 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 apartado 1.3.2 introduce la definición mediante secuencias anidadas de intervalos que convergen al número real unitario. Otras representaciones se analizan en el apartado 4.1.
  • Weihrauch, Klaus (1995). Una sencilla introducción al análisis computable . Fernuniv., Fachbereich Informatik.