En matemáticas , los números computables son los números reales que se pueden calcular con cualquier precisión deseada mediante un algoritmo finito de terminación . También se les conoce como números recursivos , números efectivos (vanDerHoeven) o reales computables o reales recursivos . [ cita requerida ]
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 campo cerrado real y se pueden usar en lugar de 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 que se calcularán de una 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: [1]
Un número computable [es] uno para el que hay 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 alguna 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 dígitos en su cinta, deteniéndose después de imprimir el n - enfatiza la observación de Minsky: (3) Que mediante el uso de una máquina de Turing, una definición finita - en la forma de la tabla de la máquina - se está utilizando para definir lo que es una cadena potencialmente infinita de dígitos decimales.
Sin embargo, esta no es la definición moderna que solo requiere que el resultado sea exacto 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á.
Definicion formal
Un número real a es computable si puede ser aproximado por alguna función computable de la siguiente manera: dado cualquier entero positivo n , la función produce un entero f ( n ) tal que:
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
- Hay una secuencia computable de números racionales. convergiendo a tal que 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 que cuando se le proporciona un número racional como retorno de entrada o , cumpliendo las siguientes condiciones:
Un ejemplo lo da un programa D que define la raíz cúbica de 3. Suponiendo esto se define por:
Un número real es computable si y solo si hay un corte D computable de Dedekind 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 de Turing produce un subconjuntode los números naturales correspondientes a los números computables e identifica una sobreyección dea los números computables. Solo hay muchas máquinas de Turing contables, lo que muestra que los números computables son subcontables . El conjuntode estos números de Gödel, sin embargo, no es computablemente enumerable (y, en consecuencia, tampoco lo son los subconjuntos deque se definen en términos de ella). Esto se debe a que no existe un 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 el grado de Turing 0 ′ ′ . En consecuencia, no existe una función computable sobreyectiva de los números naturales a los reales computables, y el argumento diagonal de Cantor no puede usarse de manera constructiva para demostrar incontables veces de ellos.
Si bien 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 dadoEl principio de ordenamiento correcto establece que hay un elemento mínimo en que corresponde a , y por lo tanto existe un subconjunto que consta de los elementos mínimos, en los que el mapa 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.
Propiedades como campo
Las operaciones aritméticas sobre números computables son ellos mismos computable en el sentido de que cada vez que los números reales a y b son computables a continuación los siguientes números reales también son computables: a + b , ab , ab , y A / B si B es distinto de cero. En realidad, estas operaciones se pueden calcular de manera uniforme ; por ejemplo, hay una máquina de Turing que en la entrada ( A , B ,) Produce una salida r , donde A es la descripción de una máquina de Turing que se aproximan a una , B es la descripción de una máquina de Turing aproximar b , y r es unaaproximación de a + b .
El hecho de que los números reales computables forman un campo fue probado por primera vez por Henry Gordon Rice en 1954 (Rice 1954).
Sin embargo, los reales computables no forman un campo computable , porque la definición de un campo computable requiere igualdad efectiva.
No computabilidad del pedido.
La relación de orden de los números computables no es computable. Sea A la descripción de una máquina de Turing que se aproxima al número. Entonces no hay ninguna máquina de Turing que en la entrada A emite "SÍ" si y "NO" si Para ver por qué, suponga que la máquina descrita por A sigue produciendo 0 comoaproximaciones. No está claro cuánto tiempo esperar antes de decidir que la máquina nunca generará una aproximación que obligue a a ser positiva. 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 ser más tarde 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 vale para la relación de igualdad: la prueba de igualdad no es computable.
Si bien la relación de orden completo no es computable, su restricción a pares de números desiguales es computable. Es decir, no es un programa que toma como entrada dos máquinas de Turing A y B los números que se aproxima a y b , donde un ≠ b , y si las salidas o Es suficiente usar aproximaciones ε donde por lo que al tomar ε cada vez más pequeños (aproximándose a 0), eventualmente se puede decidir si o
Otras propiedades
Los números reales computables no comparten todas las propiedades de los números reales usados 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 (Bridges y Richman, 1987: 58). Una secuencia con esta propiedad se conoce como secuencia de Specker , ya que la primera construcción se debe a E. Specker (1949). A pesar de la existencia de contraejemplos como estos, se pueden desarrollar partes del cálculo y del análisis real en el campo de los números computables, lo que lleva al estudio del análisis computable .
Cada número computable es definible , pero no al revés. Hay muchos números reales definibles y no calculables, que incluyen:
- cualquier número que codifique la solución del problema de detención (o cualquier otro problema indecidible ) de acuerdo con un esquema de codificación elegido.
- La constante de Chaitin ,, que es un tipo de número real que equivale a Turing al problema de la detención.
Ambos ejemplos, de hecho, definen un conjunto infinito de números definibles e incontables, 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.
Todo número computable es aritmético .
El conjunto de números reales computables (así como todos los subconjuntos contables y densamente ordenados de reales computables sin fines) es orden-isomorfo 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 producida por algún algoritmo o máquina de Turing. El algoritmo toma un número entero como entrada y produce el -ésimo 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 sabía 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 de Turing. sentido: si , A continuación, los primeros n dígitos de la expansión decimal para un proporcionan unaaproximación de a . Por el contrario, elegimos uncomputable número real una y generar aproximaciones cada vez más precisas hasta que el n º dígitos después de la coma decimal es cierto. 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).
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 valor 0,1 total) en lugar de números reales en . Los miembros de puede identificarse con expansiones decimales binarias, pero dado que las expansiones decimales y denotar el mismo número real el intervalo sólo se puede identificar bijetivamente (y homeomórficamente bajo la topología de subconjunto) con el subconjunto de sin terminar en todos los 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 los definidos en la sentido de aproximación. Hirst ha demostrado que no existe un algoritmo que tome como entrada la descripción de una máquina de Turing que produceaproximaciones 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 (ver Hirst 2007). De manera similar, significa que las operaciones aritméticas en los reales computables no son efectivas en sus representaciones decimales, ya que al sumar números decimales, para producir un dígito puede ser necesario mirar arbitrariamente hacia la derecha para determinar si hay un arrastre al 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.
Sin embargo, desde una perspectiva teórica computacional o de medidas , las dos estructuras y son esencialmente idénticos, y los teóricos de la computabilidad a menudo se refieren a miembros de como reales. Tiempo está totalmente desconectado , para preguntas sobre clases o aleatoriedad es mucho menos complicado trabajar en .
Elementos de a veces también se llaman reales y, aunque contienen una imagen homeomórfica de además de estar totalmente desconectado, ni siquiera localmente es compacto. Esto conduce a verdaderas diferencias en las propiedades computacionales. Por ejemplo, el satisfactorio con cuantificador libre debe ser computable mientras que el único satisfacer una fórmula universal puede ser arbitrariamente alto en la jerarquía hiperaritmética .
Úselo 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 los reales que podemos calcular o aproximar, la suposición de que todos los reales son computables lleva 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 lo que Bishop y Richman denominan la escuela rusa de matemáticas constructivas.
Para desarrollar realmente un análisis sobre números computables, se debe tener cierto cuidado. Por ejemplo, si uno usa la definición clásica de una secuencia, el conjunto de números computables no se cierra bajo la operación básica de tomar el supremo de una secuencia acotada (por ejemplo, considere una secuencia de Specker , vea la sección anterior). Esta dificultad se aborda considerando solo secuencias que tienen un módulo de convergencia computable . La teoría matemática resultante se llama análisis computable .
Implementación
Hay algunos paquetes de computadora que funcionan con números reales computables, que representan los números reales como programas que calculan aproximaciones. Un ejemplo es el paquete RealLib Lambov (2015) .
Ver también
- Número definible
- Función semicomputable
- Problema transcomputacional
Referencias
- ^ 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 .
- Aberth, Oliver (1968). "Análisis en el campo numérico computable". Revista de la Asociación de Maquinaria Informática . 15 (2): 276–299. doi : 10.1145 / 321450.321460 . S2CID 18135005 . Este artículo describe el desarrollo del cálculo sobre el campo numérico computable.
- Obispo, Errett; Bridges, Douglas (1985). Análisis constructivo . Saltador. ISBN 0-387-15066-8.
- Bridges, Douglas; Richman, Fred (1987). Variedades de matemáticas constructivas . Prensa de la Universidad de Cambridge. ISBN 978-0-521-31802-0.
- Hirst, Jeffry L. (2007). "Representaciones de 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.
- 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 .
- Turing, AM (1936). "Sobre números computables, con una aplicación al problema Entscheidungs". Actas de la London Mathematical Society . Serie 2 (publicada en 1937). 42 (1): 230–65. doi : 10.1112 / plms / s2-42.1.230 .
Turing, AM (1938). "En números computables, con una aplicación al Entscheidungsproblem: una corrección" . Actas de la London Mathematical Society . Serie 2 (publicada en 1937). 43 (6): 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 usa infinitas secuencias decimales. - Weihrauch, Klaus (2000). Análisis computable . Textos en Informática Teórica. Saltador. ISBN 3-540-66817-9.§1.3.2 introduce la definición por secuencias anidadas de intervalos que convergen al singleton real. Otras representaciones se discuten en §4.1.
- Weihrauch, Klaus (1995). Una simple introducción al análisis computable . Fernuniv., Fachbereich Informatik.
- Stoltenberg-Hansen, V .; Tucker, JV (1999). "Campos y anillos computables" . En Griffor, ER (ed.). Manual de teoría de la computabilidad . Elsevier. págs. 363–448. ISBN 978-0-08-053304-9.
- van der Hoeven, Joris (2006). "Cálculos con números reales efectivos". Informática Teórica . 351 (1): 52–60. doi : 10.1016 / j.tcs.2005.09.060 .