Teorema de Richardson

En matemáticas , el teorema de Richardson establece la indecidibilidad de la igualdad de los números reales definidos por expresiones que involucran enteros , π , ln 2 y funciones exponenciales y seno . Fue demostrado en 1968 por el matemático e informático Daniel Richardson de la Universidad de Bath .

Específicamente, la clase de expresiones para las que se cumple el teorema es la generada por los números racionales, el número π , el número ln 2 , la variable x , las operaciones de suma, resta, multiplicación, composición y las funciones seno , exponencial y absoluto .

Para algunas clases de expresiones generadas por primitivas distintas a las del teorema de Richardson, existen algoritmos que pueden determinar si una expresión es cero. ^{[ 1 ]}

El teorema de Richardson se puede enunciar de la siguiente manera: ^{[ 2 ]} Sea E un conjunto de expresiones que representan${\displaystyle \mathbb {R} \to \mathbb {R} }$funciones. Supongamos que E incluye estas expresiones:

• x (que representa la función identidad)
• e ^x (que representa las funciones exponenciales)
• sen x (que representa la función seno)
• todos los números racionales, ln  2 y π (que representan funciones constantes que ignoran su entrada y producen el número dado como salida).

Supongamos que E también es cerrado bajo algunas operaciones estándar. Específicamente, supongamos que si A y B están en E , entonces todos los siguientes también están en E :

• A + B (que representa la suma punto por punto de las funciones que representan A y B )
• A − B (que representa la resta punto por punto)
• AB (que representa la multiplicación punto por punto)
• A ∘ B (que representa la composición de las funciones representadas por A y B )

Entonces, los siguientes problemas de decisión son irresolubles:

• Decidir si una expresión A en E representa una función que es no negativa en todas partes.
• Si E incluye también la expresión | x | (que representa la función de valor absoluto), decidir si una expresión A en E representa una función que es cero en todas partes
• Si E incluye una expresión B que representa una función cuya antiderivada no tiene representante en E , decidir si una expresión A en E representa una función cuya antiderivada puede representarse en E. (Ejemplo:${\displaystyle e^{ax^{2}}}$tiene una antiderivada en las funciones elementales si y solo si a = 0 .

Después de que se resolviera el décimo problema de Hilbert en 1970, BF Caviness observó que se podía eliminar el uso de e ^{x y ln 2. [ 3 ]} Wang señaló más tarde que bajo los mismos supuestos bajo los cuales la pregunta de si existía x con A ( x ) < 0 era irresoluble, la pregunta de si existía x con A ( x ) = 0 también era irresoluble. ^{[ 4 ]}

Miklós Laczkovich también eliminó la necesidad de π y redujo el uso de la composición. ^{[ 5 ]} En particular, dada una expresión A ( x ) en el anillo generado por los enteros, x , sin x ⁿ , y sin( x  sin  x ⁿ ) (para n que abarca enteros positivos), tanto la cuestión de si A ( x ) > 0 para algún x como si A ( x ) = 0 para algún x son irresolubles.

Por el contrario, el teorema de Tarski-Seidenberg afirma que la teoría de primer orden del campo real es decidible, por lo que no es posible eliminar por completo la función seno.

• Problema constante : problema de decidir si una expresión es igual a cero. 
• Función elemental – Tipo de función matemática 
• Problema de álgebra de la escuela secundaria de Tarski - Problema matemático 

• Petkovšek, Marko ; Wilf, Herbert S .; Zeilberger, Doron (1996). A  =  B . AK Peters . pag.  212.ISBN​ 1-56881-063-6Archivado del original el 29 de enero de 2006.

• Weisstein, Eric W. "El teorema de Richardson" . MathWorld .