27 votos

Decidabilidad de la igualdad de expresiones construidas usando 1, +, -, *, /, ^

Considere la posibilidad de construir expresiones utilizando el número de $1$, operadores aritméticos $+, -, *, /$ y exponenciación ^ (en caso de varios valores, el principal valor es asumido, de la misma manera como se implementa en el Poder de la función en Mathematica). Es un decidable problema para comprobar si tal expresión es igual a cero? Si es así, ¿podría usted por favor me apunte a un algoritmo que pueda resolver este problema?

Actualización: he encontrado una referencia a Richardson del Teorema, que establece undecidablity de la igualdad en un conjunto más amplio de expresiones, en particular, incluyendo el logaritmo y funciones de valor absoluto.

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