¿Es posible probar si un número computable es racional o entero?

18

¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational?

Supongo que no es posible, y que esto está relacionado de alguna manera con el hecho de que no es posible probar si dos números son iguales, pero no veo cómo demostrarlo.

Editar: Un número computable x viene dado por una función fx(ϵ) que puede devolver una aproximación racional de x con precisión ϵ : |xfx(ϵ)|ϵ , para cualquier ϵ>0 . Dada tal función, ¿es posible probar si xQ o xZ ?

dbarbosa
fuente
3
¿Cómo se da el número computable?
Tsuyoshi Ito
10
Cómo se da el número es, por supuesto, relevante. Como un ejemplo tonto, si la entrada contiene una bandera si el número es un número entero o no, decidir si la entrada es un número entero o no es trivial.
Tsuyoshi Ito
3
Pregunta similar: cstheory.stackexchange.com/questions/10495/…
Kristoffer Arnsfelt Hansen
3
(1) “¿Cómo sabes que esto es un número entero?” ¿Por qué debería importarme? No dijiste nada sobre los requisitos sobre las operaciones. (2) “Si ves las dos respuestas hasta ahora, no mencionan nada sobre la implementación”. No sé qué quieres decir con “implementación” aquí, o por qué esta oración es relevante para mis comentarios.
Tsuyoshi Ito
16
Espero que mi respuesta entierre esta discusión. Tsuyoshi, estás equivocado, es relevante qué operaciones son computables. No implementamos números reales en el vacío, sino para manipularlos . Según usted, podríamos usar el tipo de unidad para implementar todo. Sí, podríamos, pero algunas operaciones no serían computables, y ese es precisamente el criterio por el cual juzgamos las representaciones.
Andrej Bauer

Respuestas:

32

Es fácil confundirse acerca de lo que significa "representar" o "implementar" un número real. De hecho, estamos presenciando una discusión en los comentarios donde la representación es contenciosa. Así que déjame abordar esto primero.

¿Cómo sabemos que una implementación es correcta?

La teoría que explica cómo representar cosas en una computadora es la realizabilidad . La idea básica es que, dado un conjunto , elegimos un tipo de datos τ y para cada x X un conjunto de valores de tipo τ que lo dan cuenta. Escribimos v x X cuando v es un valor que realiza x . Por ejemplo (usaré Haskell sin una buena razón), una implementación sensata de N podría ser el tipo de datos donde v k N cuando vXτxXτvxXvxNIntegervkNvevalúa el número (por lo tanto, en particular , no representa un número natural, y tampoco lo hace un programa divergente). Pero algún bromista podría pasar y sugerir que usemos para representar números naturales con T r u e F a l s en N para n 42 . ¿Por qué es esto incorrecto? Necesitamos un criterio .k¯-42Bool yTrue42NFalsenNn42

En el caso de los "números comodín", la observación fácil es que no se puede implementar la suma. Supongamos que le digo que tengo dos números, ambos representados por . ¿Puedes dar un realizador por su suma? Bueno, eso depende de si la suma es 42, pero no se puede saber. Dado que la suma es una "parte esencial de lo que son los números naturales", esto es inaceptable. En otras palabras, la implementación no se trata de conjuntos, sino de estructuras , es decir, tenemos que representar conjuntos de tal manera que sea posible implementar también la estructura relevante. Déjame enfatizar esto:False

Implementamos estructuras, no conjuntos desnudos. Por lo tanto, debemos poder implementar toda la estructura, junto con las operaciones y todos los axiomas, para que la implementación sea correcta.

Si no cumple con este principio, debe sugerir un criterio matemático alternativo de corrección. No se de uno.

Ejemplo: representación de números naturales.

Para los números naturales, la estructura relevante es descrita por los axiomas de Peano, y el axioma crucial que debe implementarse es la inducción (pero también , sucesor, + y × ). Podemos calcular, utilizando la realizabilidad, lo que hace la implementación de la inducción. Resulta ser un mapa (dondeestá el tipo de datos aún desconocido que representa los números naturales)0+×nat

induction : 'a -> (nat -> 'a -> 'a) -> 'nat -> 'a

satisfactorio induction x f zero = xy induction x f (succ n) = f n (induction x f n). Todo esto surge de la realizabilidad. Tenemos un criterio: una implementación de números naturales es correcta cuando permite una implementación de axiomas de Peano. Un resultado similar se obtendría si se utilizó la caracterización de los números como el álgebra inicial para el funtor .X1+X

Correcta implementación de números reales

Volvamos la atención a los números reales y la pregunta en cuestión. La primera pregunta es "¿cuál es la estructura relevante de los números reales?" La respuesta es: Archimedean Cauchy completa el campo ordenado . Este es el significado establecido de "números reales". No puede cambiarlo, otros lo han arreglado para usted (en nuestro caso, los reales alternativos de Dedekind resultan ser isomorfos a los reales de Cauchy, que estamos considerando aquí). No puede quitarle ninguna parte. no puede decir "No me importa implementar la adición" o "No me importa la orden". Si hace eso, no debe llamarlo "números reales", sino algo así como "números reales donde olvidamos el orden lineal".

No voy a entrar en todos los detalles, pero permítanme explicarles cómo las diversas partes de la estructura ofrecen varias operaciones en reales:

  • El axioma de Arquímedes trata de calcular aproximaciones racionales de reales
  • la estructura de campo proporciona las operaciones aritméticas habituales
  • el orden lineal nos da un procedimiento semidecidable para probar x<y
  • la integridad de Cauchy nos da una función lim : (nat -> real) -> realque toma una (representación de) secuencia rápida de Cauchy y devuelve su límite. (Una secuencia es rápida si | x n - x m |2 min ( n , m )(xn)n|xnxm|2min(n,m) para todos los .)m,n

Que hacemos no obtenemos es una función de prueba para la igualdad. No hay nada en los axiomas para los reales que pida que sea ​​decidible. (En contraste, los axiomas de Peano implican que los números naturales son decidibles, y puede probarlo implementando el uso solo como un ejercicio divertido).=eq : nat -> nat -> Boolinduction

Es un hecho que la representación decimal habitual de los reales que usa la humanidad es mala porque con ella ni siquiera podemos implementar la suma. El punto flotante con mantisa infinita también falla (ejercicio: ¿por qué?). Sin embargo, lo que funciona es la representación de dígitos con signo , es decir, una en la que permitimos dígitos negativos y positivos. O podríamos usar secuencias de racionales que satisfagan la prueba rápida de Cauchy, como se indicó anteriormente.

La representación de Tsuyoshi también implementa algo, pero no R

Consideremos la siguiente representación de números reales: una verdadera está representada por un par ( q , b ) donde ( q n ) n es una secuencia de Cauchy rápida convergiendo a x y b es un valor booleano que indica si x es un entero. Para que esto sea una representación de los reales, tendríamos que implementar la suma, pero resulta que no podemos calcular las banderas booleanas. Entonces esto no es una representación de los reales. Pero todavía representa algo, es decir, el subconjunto de los reales Z( RZ )x(q,b)(qn)nxbxZ(RZ). De hecho, de acuerdo con la interpretación realizabilidad una unión se lleva a cabo con una bandera que indica qué parte de la unión que estamos. Por cierto, es un no igual a R , a menos que crea en medio excluido, lo cual no se puede implementar y, por lo tanto, es bastante irrelevante para esta discusión. Las computadoras nos obligan a hacer cosas intuitivamente.Z(RZ)R

No podemos probar si un real es un entero

Finalmente, déjame responder la pregunta que se hizo. Ahora sabemos que una representación aceptable de los reales es una de las rápidas secuencias de racionales de Cauchy. (Un teorema importante afirma que dos representaciones de reales que son aceptables son en realidad computacionalmente isomorfas).

Teorema: probar si un real es un entero no es decidible.

Prueba. Supongamos que pudiéramos probar si un real es un entero (por supuesto, el real se realiza mediante una secuencia rápida de Cauchy). La idea, que le permitirá probar un teorema mucho más general si lo desea, es construir una secuencia de Cauchy rápida de no enteros que converja a un entero. Esto es fácil, solo toma x n = 2 - n . A continuación, resuelva el problema de detención de la siguiente manera. Dada una máquina Turing T , defina una nueva secuencia ( y n ) n por y n = { x n si (xn)nxn=2nT(yn)n Es decir, las nuevas miradas de secuencia como la secuencia(xn)n, siempre y cuandoTcarreras, pero luego se queda "atrapado" enxmsiT sedetiene en el pasom. Muy importante, la nueva secuencia también es una secuencia rápida de Cauchy (y podemos probar esto sin saber siT sedetiene). Por lo tanto, podemos calcular su límitez=limnyn

yn={xnif T has not stopped within n stepsxmif T stopped in step m and mn
(xn)nTxmTmTz=limnyn, porque nuestra representación de los reales es correcta. Comprueba si es un número entero. Si es así, debe ser 0 y esto solo sucede si T se ejecuta para siempre. De lo contrario, z no es un entero, por lo que T debe haberse detenido. QEDz0TzT

Ejercicio: adapte la prueba anterior para mostrar que no podemos probar números racionales. Luego, adáptelo para mostrar que no podemos probar nada no trivial (esto es un poco más difícil).

A veces las personas se confunden con todo este negocio de pruebas. Piensan que hemos demostrado que nunca podemos probar si un real es un número entero. Pero seguramente, 42 es real y podemos decir si es un número entero. De hecho, cualquier real particular que se nos ocurra, , 88 ln 89 , e π sin1188ln89 , etc., podemos decir perfectamente si son enteros. Precisamente,podemosdecirlo porquetenemosinformación adicional: estos reales no se nos dan como secuencias, sino como expresiones simbólicas a partir de las cuales podemos calcular el bit Tsuyoshi. Tan pronto como la única información que tenemos sobre lo real es una secuencia de aproximaciones racionales que convergen a la misma (y yonosignifica una expresión simbólica que describe la secuencia, pero un cuadro negro que da salida a laNtérmino -ésima en la entradaneπ163nn ) entonces será tan indefenso como las máquinas.

La moraleja de la historia

No tiene sentido hablar sobre la implementación de un conjunto a menos que sepamos qué tipo de operaciones queremos realizar en él.

Andrej Bauer
fuente
16
Si mis respuestas fueran esposas, solo podría responder una vez. O al menos tendría que eliminar la respuesta anterior antes de escribir la siguiente.
Andrej Bauer
55
@Max: los primeros teoremas de este tipo fueron dados por Kreisel, Lacombe y Shoenfield (consulte el teorema de KLS). Independientemente, Tsteitin dio un teorema que generalizaba KLS y tenía explícitamente la forma "cada mapa computable es computablemente continuo".
Andrej Bauer
66
Necesito escribir un libro de texto - (Google google google). De acuerdo, bien, tienes la tenencia. ¡Ve a por ello!
Jeff
10
@ Tsuyoshi: La pregunta utilizó la frase establecida "número real" sin una calificación. La estructura de los números reales es estándar. Usted es libre de considerar otras estructuras, pero no es libre de malinterpretar la terminología estándar.
Andrej Bauer
21
Técnicamente hablando, tienes razón, la palabra "real" no se usó. Pero estás equivocado acerca de la definición de números reales. O lo diría de esta manera: es una mala matemática pensar que los reales son un conjunto particular que viene primero, solo para ser seguido por alguna estructura. Al igual que definimos grupos, anillos, espacios topológicos, etc., en términos de su estructura, también deberíamos definir objetos especiales en términos de sus propiedades universales (los números naturales son el semisecado inicial, los números enteros el anillo inicial, el campo inicial racional, los reales el .....).
Andrej Bauer
10

Tiendo a pensar que esto es indecidible:

Sea un número irracional computable. Considere una MT M . Puede construir una función que ejecute M en ϵ , y en paralelo calcula x con precisión creciente. Si M se detiene, deja de calcular x , de lo contrario continúa.xMMϵxMx

Decidir si esta función calcula un número racional es equivalente al problema de detención.

Shaull
fuente
No entiendo tu respuesta, ¿podrías por favor elaborar más? No entiendo cómo lo relacionas con el problema de detención y, lo que es más importante, creo que no hay razón para que se detenga (incluso si x es un número entero). Mx
dbarbosa
Como Tsuyoshi ha señalado, la respuesta depende de la representación y el modelo de cálculo. Su respuesta dice correctamente que si consideramos que las entradas son números reales computables dados por un TM que las computa, entonces la igualdad no es decidible. Esto es correcto, sin embargo, no está cerca de ningún modelo que se use en la práctica.
Kaveh
2
De hecho, mi respuesta se refiere a las representaciones publicadas en la pregunta, sean prácticas o no. @dbarbosa: explicaré: dado un TM , siga la construcción en la respuesta. Luego, suponga por contradicción que puede decidir si la máquina de salida representa un racional o no. Si es racional, significa que en algún momento, M se detuvo y dejamos de calcular el número. Por otro lado, si es irracional, entonces M no se detiene. Por lo tanto, sabemos si M se detiene, resolviendo el problema de detención, que se sabe que es indecidible. MMMM
Shaull
10

Suponiendo que un real se da como una secuencia de aproximaciones racionales con el error delimitado por alguna función computable conocida que tiende a cero (todas esas aproximaciones son equivalentes y corresponden a la topología habitual en los reales).

Las funciones computables son continuas. IsRational e IsInteger no son continuos y, por lo tanto, no son computables.

EsEntero es semi -computable: existe un procedimiento que con el tiempo de salida "falso" si la entrada no es un entero, pero siempre se ejecutará si la entrada es un entero. Este procedimiento simplemente analiza cada aproximación y comprueba si hay un número entero dentro del límite de error. Esta función es continua cuando usamos la topología de Sierpiński en {verdadero, falso} (es decir, {falso} es un conjunto abierto pero {verdadero} no lo es).

Max
fuente
Gracias por la respuesta. No entiendo el no continuo => no computable, supongo que usaste un teorema (probablemente ampliamente conocido) que no conozco o que no recuerdo. ¿Podría por favor proporcionar más detalles sobre este paso?
dbarbosa
1
"computable => contundente" parece ser un teorema popular: no puedo encontrar una cita original. Brattka ( math.uni.wroc.pl/~pkowa/slides/brattka.pdf ) describe bastante bien la teoría de la computación en objetos infinitos y las conexiones con la topología (OMI) en estas diapositivas del curso . La Proposición 2 en las diapositivas establece que todas las funciones computables en secuencias de naturales son continuas; combinado con el Teorema 12 se obtiene el resultado para funciones de otros tipos.
Max
6

Es indecidible si un número computable dado es igual a cero .

(¿Entonces su oráculo de aproximación racional devuelve 0 por cada ε que ha intentado? Tal vez simplemente no le haya dado un ε lo suficientemente pequeño).

Por lo tanto, es indecidible si un número computable dado entre -½ y + ½ es un número entero.

Jeffε
fuente
2

Una función que es computable es más fuerte que la función que es continua, es decir, cualquier función computable debe ser continua en la topología de la información.

Desea ver si la función definida porF:R{Yes,No}

F(r)={YESrQNOo.w.

es computable

rk2nr[k2n,k+12n]n

Entonces su función no es continua y, por lo tanto, no es computable.

M0n[12n,12n]MMmM[12m,12m]MMNOYESM[12m,12m]MYESM

La prueba de que cualquier función computable debe ser continua es similar.

Kaveh
fuente