21 votos

Es un ser racional decidable?

Dado un número real único, definido por un sistema finito de ecuaciones y desigualdades con coeficientes racionales implican el estándar de funciones elementales sólo. Es decidable si este número es racional?

Edit: El sistema de ecuaciones y desigualdades pueden tener $n$ reales-valores de las variables, y el número real a definirse es $\xi$. Por descomposición uso de variables intermedias, podemos suponer que cada ecuación es de la forma $x_i\,\omega\, c$ donde $\omega\in\{<,>,\le,\ge\}$ e $c$ es un número entero, y cada ecuación es de la forma $x_i=\xi$ o $x_i=c$ donde $c$ es un número entero, o $x_i=x_j\circ x_k$ con $\circ\in\{+,-,*,/\}$ o $x_i=\phi(x_k)$ donde $\phi\in E$ con un conjunto especificado $E$ de funciones elementales, tales como $E=\{\exp,\log\}$. La respuesta a la pregunta puede depender de la elección de $E$.

Supongo que $\xi$ está determinada únicamente (define, pues, por este sistema de ecuaciones y desigualdades. Uno puede incluso asumir que uno tiene una prueba de esto, si esto ayuda.

El algoritmo puede ser definido de acuerdo a cualquiera de los diversos modelos tradicionales, la especificación de un razonable conjunto de primitivas de operaciones (incluyendo las operaciones racionales (por ejemplo, en bits o en reales] y la ramificación de una expresión). Estoy más interesado en las técnicas son aplicables a la que en una respuesta para un modelo en particular.

Tenga en cuenta que el artículo de Wikipedia sobre el problema constante reclamaciones (por referencia a D. H. Bailey, las Matemáticas de la Computación 50 (1988), 275-281) un resultado a partir de la cual decidability iba a seguir, pero esta afirmación es espuria.

11voto

thedeeno Puntos 12553

Como Timoteo Chow señalado, el OP pregunta es, naturalmente, la mayoría de los formulado como una promesa problema: dado un sistema finito de ecuaciones y desigualdades en un número finito de variables y la promesa de que se tiene una solución y, además, de que todas las soluciones tienen el mismo valor para la variable $\xi$, determinar ya sea o no que el valor de $\xi$ es racional.

Permítanme mostrarles aquí en diversas formas en que si dejamos caer el promesa-problema de aspecto del problema, no es decidable.

Teorema. No es computable procedimiento para determinar si un finito dado el sistema de ecuaciones y desigualdades, permitiendo que el las operaciones de $+,\cdot,0,1,\sin$, tiene una solución en los reales.

Prueba. Vamos a utilizar las variables $\xi,x_1,\ldots,x_n$ y otra variable $p$. Insistiendo en que $\sin(p)=0$ e $p>0$, se puede asegurarse de que $p$ es un número entero múltiplo de $\pi$. Por insistiendo en que $\sin(x_i\cdot p)=0$, podemos asegurar que cada una de las $x_i$ es un número entero.

De esta manera, podemos transformar cualquier ecuación de diophantine $q(\vec x)=0$, where $p$ es polinomio en varias variables a lo largo de la enteros, en un sistema a través de los reales, tal que $q(\vec x)=0$ tiene una solución a través de los enteros si y sólo si el nuevo sistema ha una solución con respecto a los reales.

Pero es bien conocido consecuencia del teorema de MRDP que no podemos computably decidir si un determinado diophantine la ecuación tiene una solución a través de los números enteros (y este fue el solución de Hilbert 10 de problema). QED

Teorema. No es computable procedimiento para determinar si un finito dado el sistema de ecuaciones y desigualdades en el variables $x_1,\ldots,x_n,\xi$, permitiendo que las operaciones $+,\cdot,0,1,\sin$, tiene al menos un valor racional $\xi$ que es parte de una solución. Además, este sigue siendo indecidible incluso dada la promesa de que hay más de un valor de $\xi$ que es parte de una solución, y que no irracional $\xi$ son soluciones.

Prueba. Para cualquier ecuación de diophantine $q(\vec x)=0$, considere la posibilidad de el sistema modificado sobre los reales, el uso de la variable adicional $p$, donde insistimos en que $q(\vec x)=0$ también $\sin(p)=0$, $p>0$, e $\sin(x_i\cdot p)=0$, que se aseguran de que $p$ es un positivo múltiplo entero de $\pi$ y que todas las $x_i$'s son los números enteros. Por último, agregar la ecuación de $\xi=0$.

El original diophantine ecuación tiene una solución a través de los números enteros sólo en caso de que el nuevo sistema tiene una solución con respecto a los reales, y en cualquier solución, $\xi$ será racional, porque va a ser $0$. Por lo que el sistema original tiene una solución a través de los números enteros y si sólo si el nuevo sistema tiene al menos una solución para que $\xi$ es racional. Así que esto no es decidable. QED

Teorema. No es computable procedimiento para determinar si un finito dado el sistema de ecuaciones y desigualdades en el variables $x_1,\ldots,x_n,\xi$, permitiendo que las operaciones $+,\cdot,0,1,\sin$, tiene más de una racional $\xi$ que es parte de una solución. Además, este es indecidible en virtud de la la promesa que hay en la mayoría de los dos valores de $\xi$ que resolver el sistema, tanto racional.

Prueba. Utilizamos la misma idea, sino que se sustituye la ecuación de $\xi=0$ con la ecuación de $\xi(\xi-1)=0$. Por lo que este sistema no tiene soluciones o $\xi=0$ e $\xi=1$ son ambas soluciones. QED

Estos teoremas no parecen responder a la pregunta: dado un sistema finito de ecuaciones y desigualdades, y dada la promesa de que no es exactamente un valor de $\xi$ que es parte de una solución, determinar si este valor de $\xi$ es racional o no.

8voto

Dean Hill Puntos 2006

Este es un comentario largo en lugar de una respuesta.

El problema es lo que se conoce como una "promesa problema". La entrada viene equipado con una promesa, es decir, que no existe una única solución real. Es de suponer que, si la promesa es violado, entonces el algoritmo es "off the hook" y puede hacer lo que le gusta, incluida la omisión de detener.

No soy consciente de ninguna investigación sobre la decidability de la promesa de problemas. (Hay algunos trabajos sobre la complejidad computacional de decidable promesa de problemas.) La dificultad esencial de su problema parece residir en su naturaleza como una promesa problema, más que en algo acerca de los números racionales. Para ver esto, consideremos la cuestión: Es ser un entero decidable? Esto sólo se ve tan difícil como la de su pregunta.

En la complejidad computacional reino, a menudo es posible para pasar entre la promesa de problemas y la existencia-de-una-solución de problemas. Es decir, las preguntas "no existe una solución única; ¿qué es?" y "¿existe una solución?" están estrechamente relacionados, y a menudo se puede reducir una a la otra. De hecho, para tu problema, si tenemos un algoritmo para responder a "¿existe una solución racional?", podemos resolver su problema. Sin embargo, no veo cómo crear una reducción en la dirección opuesta, porque no veo cómo crear adecuado promesa de problemas a partir de un sistema arbitrario. Si pudiéramos, entonces tal vez el hecho de que Hilbert del décimo problema de más de $\mathbb Q$ todavía está abierta podría ser utilizado para demostrar que el problema sigue abierto.

4voto

Josh Puntos 193

He encontrado un artículo de Babai, Justo, y Meyer auf der Heide, que responde a una estrechamente relacionadas con la cuestión.

Prueban, entre otros (véase la discusión en la página.101) de que no hay anlytic cálculo de árboles (Actos) que aceptan el complemento de los racionales en los reales, y por lo tanto la prueba de la irracionalidad de un número.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X