En matemáticas, el teorema de Richardson establece un límite en la medida en que un algoritmo puede decidir si ciertas expresiones matemáticas son iguales. Establece que para una cierta clase de expresiones bastante natural, es indecidible si una expresión particular E satisface la ecuación E = 0, y de manera similar indecidible si las funciones definidas por las expresiones E y F son iguales en todas partes (de hecho, E = F si y solo si E - F = 0). Fue probado en 1968 por el científico informático Daniel Richardson delUniversidad de Bath .
Específicamente, la clase de expresiones para las que se cumple el teorema es la generada por números racionales, el número π , el número ln 2 , la variable x , las operaciones de suma, resta, multiplicación, composición y sin , exp y abs. funciones.
Para algunas clases de expresiones (generadas por otras primitivas distintas del teorema de Richardson) existen algoritmos que pueden determinar si una expresión es cero. [1]
Declaración del teorema
El teorema de Richardson se puede enunciar de la siguiente manera: [2] Sea E un conjunto de expresiones que representan funciones ℝ → ℝ . Suponga que E incluye estas expresiones:
- x (que representa la función de identidad)
- e x (que representa las funciones exponenciales)
- sin x (que representa la función sin)
- todos los números racionales, ln 2 y π (que representan funciones constantes que ignoran su entrada y producen el número dado como salida)
Suponga que E también se cierra en algunas operaciones estándar. Específicamente, suponga 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 puntual de las funciones que representan A y B )
- A - B (que representa la resta puntual)
- AB (que representa la multiplicación puntual)
- A∘B (que representa la composición de las funciones representadas por A y B )
Entonces, los siguientes problemas de decisión no tienen solución :
- Decidir si una expresión A en E representa una función que no es 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 representa una función cuyo antiderivative tiene ningún representante en E , de decidir si una expresión A en E representa una función cuyo antiderivative puede ser representado en E . (Ejemplo:tiene una antiderivada en las funciones elementales si y solo si a = 0. )
Extensiones
Después de que se resolvió el décimo problema de Hilbert en 1970, BF Caviness observó que se podía eliminar el uso de e x e ln 2. [3] PS Wang señaló más tarde que bajo los mismos supuestos bajo los cuales la cuestión de si había x con A ( x ) <0 era insoluble, la cuestión de si había x con A ( x ) = 0 también era insoluble. [4]
Miklós Laczkovich eliminó también la necesidad de π y redujo el uso de composición. [5] En particular, dada una expresión A ( x ) en el anillo generado por los números enteros, x , sin x n y sin ( x sin x n ), la cuestión de si A ( x )> 0 para alguna x y si A ( x ) = 0 para algunos x son insolubles.
Por el contrario, el teorema de Tarski-Seidenberg dice que la teoría de primer orden del campo real es decidible, por lo que no es posible eliminar la función seno por completo.
Ver también
Referencias
- ^ Dan Richardson y John Fitch, 1994, " El problema de identidad para funciones elementales y constantes ", Actas del simposio internacional sobre computación simbólica y algebraica, págs. 85-290.
- ^ Richardson, Daniel (1968). "Algunos problemas indecidibles que involucran funciones elementales de una variable real". Revista de lógica simbólica . 33 (4): 514–520. JSTOR 2271358 . Zbl 0175.27404 .
- ^ Caviness, BF (1970). "Sobre formas canónicas y simplificación". Revista de la ACM . 17 (2): 385–396. doi : 10.1145 / 321574.321591 .
- ^ Wang, PS (1974). "La indecidibilidad de la existencia de ceros de funciones elementales reales". Revista de la Asociación de Maquinaria Informática . 21 (4): 586–589. doi : 10.1145 / 321850.321856 .
- ^ Laczkovich, Miklós (2003). "La eliminación de π de algunos problemas indecidibles que involucran funciones elementales" . Proc. Amer. Matemáticas. Soc . 131 (7): 2235–2240. doi : 10.1090 / S0002-9939-02-06753-9 .
Otras lecturas
- Petkovšek, Marko ; Wilf, Herbert S .; Zeilberger, Doron (1996). A = B . AK Peters . pag. 212. ISBN 1-56881-063-6. Archivado desde el original el 29 de enero de 2006.