Número computable

π se puede computar a la precisión arbitraria, mientras que casi todo número real no es computable.

En matemáticas, números computables son los números reales que se pueden calcular con cualquier precisión deseada mediante un algoritmo de terminación finito. También se les conoce como los números recursivos, números efectivos o los reales computables o reales recursivos.

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

Definición informal usando 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; es decir, como "secuencias de dígitos interpretadas como fracciones decimales" entre 0 y 1:

Un número computable [es] uno para el cual hay una máquina de Turing que, dada n en su cinta inicial, termina con la nt 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 principio, (2) para cualquier n el cálculo solo toma un número finito de pasos, después de lo cual la máquina produce la salida deseada y termina.

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

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

Definición formal

Un número real a es computable si puede ser aproximado por alguna función computable f:N→ → Z{displaystyle f:mathbb {N} to mathbb {Z} de la siguiente manera: dado cualquier entero positivo n, la función produce un entero f()nAsí que...

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

Hay dos definiciones similares que son equivalentes:

• Existe una función computable que, dada cualquier error racional positivo ε ε {displaystyle varepsilon }, produce un número racional r tales que Silencior− − aSilencio≤ ≤ ε ε .{displaystyle tenciónr-a muerteleq varepsilon.}
• Hay una secuencia computable de números racionales qi{displaystyle q_{i} convergiendo a a{displaystyle a} tales que <math alttext="{displaystyle |q_{i}-q_{i+1}|Silencioqi− − qi+1Silencio.2− − i{displaystyle ¿Qué?<img alt="|q_i - q_{i+1}| para cada uno i.

Hay otra definición equivalente de números computables a través de cortes computables de Dedekind. A computable Dedekind cut es una función computable D{displaystyle D;} que cuando se proporciona un número racional r{displaystyle r} como retornos de entrada D()r)=true{displaystyle D(r)=mathrm {true} o D()r)=false{displaystyle D(r)=mathrm {false};}, satisfaciendo las siguientes condiciones:

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

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

<math alttext="{displaystyle (D(r)=mathrm {true})wedge (D(s)=mathrm {false})Rightarrow r()D()r)=true)∧ ∧ ()D()s)=false)⇒ ⇒ r.s{displaystyle (D(r)=mathrm {true})wedge (D(s)=mathrm {false}) Derecha R:<img alt="(D(r)=mathrm{true}) wedge (D(s)=mathrm{false}) Rightarrow r

r,D(s)=mathrm {true}.;}" xmlns="http://www.w3.org/1998/Math/MathML">D()r)=true⇒ ⇒ ∃ ∃ s■r,D()s)=true.{displaystyle D(r)=mathrm {true} Rightarrow exists s confíar,D(s)=mathrm {true}.;}r, D(s)=mathrm{true}.;" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f09c5058a5e14e9a63a8da7548be5b8d53c598ed" style="vertical-align: -0.838ex; width:36.556ex; height:2.843ex;"/>

Un ejemplo es dado por un programa D que define la raíz del cubo de 3. Sumas 0;}" xmlns="http://www.w3.org/1998/Math/MathML">q■0{displaystyle q confía0;}0;" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/635f269fd2363378fcc30e18cc61cfa2e815c9a9" style="vertical-align: -0.671ex; width:5.976ex; height:2.509ex;"/> esto se define por:

<math alttext="{displaystyle p^{3}p3.3q3⇒ ⇒ D()p/q)=true{displaystyle p^{3} obedeció3q^{3}Rightarrow D(p/q)=mathrm {true} ;}<img alt="p^3

3q^{3}Rightarrow D(p/q)=mathrm {false}.;}" xmlns="http://www.w3.org/1998/Math/MathML">p3■3q3⇒ ⇒ D()p/q)=false.{displaystyle p^{3} {3q^{3}Rightarrow D(p/q)=mathrm {false}.;}3 q^3 Rightarrow D(p/q)=mathrm{false}.;" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7a8f9335cfedea0ca7bb13e9cb4ca589c52132c1" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:28.47ex; height:3.176ex;"/>

Un número real es computable si y solo si hay 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 real e imaginaria son computables.

Propiedades

No computablemente enumerable

Asignar un número de Gödel a cada definición de máquina Turing produce un subset S{displaystyle S. de los números naturales correspondientes a los números computables e identifica una subjeción de S{displaystyle S. a los números computables. Sólo hay muchas máquinas Turing, mostrando que los números computables son subcontables. El set S{displaystyle S. de estos números de Gödel, sin embargo, no es computadamente enumerable (y en consecuencia, tampoco son subconjuntos de S{displaystyle S. que se definen en términos de ella). Esto es porque no hay algoritmo para determinar qué números de Gödel corresponden a las máquinas de Turing que producen 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 grado de Turing 0. En consecuencia, no existe una función computable subjetiva de los números naturales a los reales computables, y el argumento diagonal de Cantor no se puede utilizar constructivamente para demostrar incontablemente muchos de ellos.

Aunque el conjunto de números reales es incontable, el conjunto de 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 x,{displaystyle x,} el principio de orden bien establece que hay un elemento mínimo en S{displaystyle S. que corresponde a x{displaystyle x}, y por lo tanto existe un subconjunto que consta de los elementos mínimos, en el que el mapa es una bijeción. El inverso de esta bijección es una inyección en los números naturales de los números computables, demostrando que son contables. Pero, de nuevo, este subconjunto no es computable, a pesar de que los propios reales computables son ordenados.

Propiedades como campo

Las operaciones aritméticas en números computables son computables en el sentido de que cada número real a y b son computables entonces los siguientes números reales también son computables: a + b, a - b, ab, y a/b si b No es cero. Estas operaciones son en realidad uniformemente computable; por ejemplo, hay una máquina de Turing que en la entrada (A,B,ε ε {displaystyle epsilon }) produce salida r, donde A es la descripción de una máquina de Turing aproximándose a, B es la descripción de una máquina de Turing aproximándose b, y r es un ε ε {displaystyle epsilon } aproximación de a+b.

Henry Gordon Rice demostró por primera vez en 1954 que los números reales computables forman un campo.

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

No computabilidad del pedido

La relación de pedido en los números computables no es computable. Vamos A ser la descripción de una máquina de Turing aproximándose el número a{displaystyle a}. Entonces no hay ninguna máquina de Turing que en la entrada A salidas "Sí" si 0}" xmlns="http://www.w3.org/1998/Math/MathML">a■0{displaystyle a confía0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f34a80ea013edb56e340b19550430a8b6dfd7b9" style="vertical-align: -0.338ex; width:5.491ex; height:2.176ex;"/> y "NO" si a≤ ≤ 0.{displaystyle aleq 0} Para ver por qué, suponga la máquina descrita por A mantiene la salida 0 como ε ε {displaystyle epsilon } aproximaciones. No está claro cuánto tiempo esperar antes de decidir que la máquina nunca jamás nunca jamás nunca jamás nunca jamás nunca jamás jamás nunca jamás nunca jamás nunca jamás nunca jamás nunca jamás nunca jamás nunca jamás nunca jamás nunca jamás jamás nunca jamás nunca jamás nunca jamás nunca jamás jamás nunca jamás nunca jamás nunca jamás jamás nunca jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás jamás salida una aproximación que obliga a para ser positivo. Por lo tanto, la máquina tendrá que adivinar que el número será igual a 0, con el fin de producir una salida; la secuencia puede llegar a ser diferente de 0. Esta idea se puede utilizar para demostrar que la máquina es incorrecta en algunas secuencias si calcula una función total. Un problema similar ocurre cuando los reales computables están representados como cortes Dedekind. Lo mismo sostiene la relación de igualdad: la prueba de igualdad no es computable.

Aunque la relación de orden completo no es computable, la restricción de ella a pares de números desiguales es computable. Es decir, hay un programa que toma como entrada dos máquinas Turing A y B Números aproximados a{displaystyle a} y b{displaystyle b}, donde aل ل b{displaystyle aneq b}, y productos si <math alttext="{displaystyle aa.b{displaystyle a meantb}<img alt="a o b.}" xmlns="http://www.w3.org/1998/Math/MathML">a■b.{displaystyle a prendab.}b.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19f3dbc209b9e7a3f89d6b918f0f67a5fd7cc2d6" style="vertical-align: -0.338ex; width:5.973ex; height:2.176ex;"/> Es suficiente para usar ε ε {displaystyle epsilon }-aproximaciones donde <math alttext="{displaystyle epsilon ε ε .Silenciob− − aSilencio/2,{displaystyle epsilon - No.<img alt="{displaystyle epsilon así, tomando cada vez más pequeñas ε ε {displaystyle epsilon } (aproximadamente 0), uno eventualmente puede decidir si <math alttext="{displaystyle aa.b{displaystyle a meantb}<img alt="a o b.}" xmlns="http://www.w3.org/1998/Math/MathML">a■b.{displaystyle a prendab.}b.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19f3dbc209b9e7a3f89d6b918f0f67a5fd7cc2d6" style="vertical-align: -0.338ex; width:5.973ex; height:2.176ex;"/>

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. Una secuencia con esta propiedad se conoce como secuencia de Specker, ya que la primera construcción se debe a Ernst Specker en 1949. A pesar de la existencia de contraejemplos como estos, se pueden desarrollar partes del cálculo y el análisis real en el campo de los números computables, lo que lleva al estudio del análisis computable.

Todo número computable es definible aritméticamente, pero no al revés. Hay muchos números reales no computables y definibles aritméticamente, que incluyen:

• cualquier número que codifica la solución del problema de suspensión (o cualquier otro problema indecible) según un esquema de codificación elegido.
• Chaitin es constante, Ω Ω {displaystyle Omega }, que es un tipo de número real que es Turing equivalente al problema de suspensión.

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 todo subconjunto contable, densamente ordenado de números reales computables sin extremos) es isomorfo al orden del conjunto de números racionales.

Cadenas de dígitos y espacios de Cantor y Baire

El artículo original de Turing definió 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 entero n≥ ≥ 1{displaystyle ngeq 1} como entrada y produce el n{displaystyle n}- el dígito de la expansión decimal del número real como salida.

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

Turing was aware that this definition is equivalent to the ε ε {displaystyle epsilon }- definición de aproximación dada arriba. 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 ε ε {displaystyle epsilon } sentido: si log _{10}(1/epsilon)}" xmlns="http://www.w3.org/1998/Math/MathML">n■log10⁡ ⁡ ()1/ε ε ){displaystyle n confianzalog _{10}(1/epsilon)} log_{10} (1/epsilon)" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b9bd94300e7f9be6774a24ce634de8d722b248b4" style="vertical-align: -0.838ex; width:14.419ex; height:2.843ex;"/>, entonces el primero n dígitos de la expansión decimal para a proporcionar un ε ε {displaystyle epsilon } aproximación de a. Para el contrario, escogemos un ε ε {displaystyle epsilon } número real computable a y generar aproximaciones cada vez más precisas hasta nt dígito después del punto decimal es seguro. Esto siempre genera una expansión decimal igual a a pero puede terminar indebidamente en una secuencia infinita de 9's en cuyo caso debe tener una expansión decimal adecuada 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 de 2⋅ ⋅ {displaystyle 2^{omega } (total 0,1 funciones valoradas) en lugar de números reales en [0,1]{displaystyle [0,1]}. Los miembros de 2⋅ ⋅ {displaystyle 2^{omega } se puede identificar con expansiones binarias decimales, pero desde las expansiones decimales .d1d2...... dn0111...... {displaystyle.d_{1}d_{2}ldots ♪ 0111 'ldots ♪ y .d1d2...... dn10{displaystyle.d_{1}d_{2}ldots D_{n}10} denota el mismo número real, el intervalo [0,1]{displaystyle [0,1]} sólo puede ser bijetivamente (y homeomorfamente bajo la topología subconjunta) identificada con el subconjunto de 2⋅ ⋅ {displaystyle 2^{omega } no terminando en los 1.

Tenga en cuenta que esta propiedad de expansiones decimales significa que es imposible identificar eficazmente los números reales computables definidos en términos de una expansión decimal y los definidos en el ε ε {displaystyle epsilon } Sentido de aproximación. Hirst ha demostrado que no hay algoritmo que toma como entrada la descripción de una máquina de Turing que produce ε ε {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. Del mismo modo, significa que las operaciones aritméticas en los reales computables no son eficaces en sus representaciones decimales como cuando agregan números decimales. Para producir un dígito, puede ser necesario mirar arbitrariamente lejos al derecho a determinar si hay un transporte a la ubicación actual. Esta falta de uniformidad es una razón por la cual 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 computacional o teorética de medida, las dos estructuras 2⋅ ⋅ {displaystyle 2^{omega } y [0,1]{displaystyle [0,1]} son esencialmente idénticos. Así, los teóricos de computación a menudo se refieren a miembros de 2⋅ ⋅ {displaystyle 2^{omega } como real. Mientras tanto 2⋅ ⋅ {displaystyle 2^{omega } está totalmente desconectado, para preguntas sobre ▪ ▪ 10{displaystyle Pi _{1} {0}} clases o aleatoriedad es más fácil trabajar en 2⋅ ⋅ {displaystyle 2^{omega }.

Elementos de ⋅ ⋅ ⋅ ⋅ {displaystyle omega ^{omega } son a veces llamados reales también y aunque contiene una imagen homeomorfa de R{displaystyle mathbb {R} ⋅ ⋅ ⋅ ⋅ {displaystyle omega ^{omega } además de estar totalmente desconectado, ⋅ ⋅ ⋅ ⋅ {displaystyle omega ^{omega } ni siquiera es localmente compacto. Esto conduce a diferencias genuinas en las propiedades computacionales. Por ejemplo, x▪ ▪ R{displaystyle xin mathbb {R} satisfacción О О ()n▪ ▪ ⋅ ⋅ )φ φ ()x,n){displaystyle forall (nin omega)phi (x,n)}, con φ φ ()x,n){displaystyle phi (x,n)} quantifier libre, debe ser computable mientras que el único x▪ ▪ ⋅ ⋅ ⋅ ⋅ {displaystyle xin omega ^{omega } satisfacer una fórmula universal puede tener una posición arbitrariamente alta en la jerarquía hiperaritmética.

Usar en lugar de las reales