Decidabilidade de igualdade e solidez de expressões envolvendo aritmética e exponenciais elementares

Question

Vamos ter expressões compostas de elementos de $ \ mathbb n $ e um conjunto limitado de operações binárias { $ +, \ vezes, - / $ } e funções { $ \ exp, \ ln $ }. As expressões são sempre bem formadas e formam árvores finitas, com números como nós foliares e operadores como nós internos, operações binárias com duas subfrições filho e as funções uma. Um valor dessa expressão é interpretado para significar algum número na $ \ mathbb R $ .

Existem duas limitações na estrutura das expressões: o divisor (a sub-expressão à direita) da $ / $ não pode ser 0 e argumento de $ \ ln $ deve ser positivo.

Eu tenho duas perguntas sobre esse tipo de expressões:

• É possível garantir "solidez" de tal expressão, no sentido de que as duas limitações podem ser verificadas em tempo finito?

• é uma verificação de igualdade entre duas expressões decidíveis?

Essas perguntas parecem estar conectadas no sentido de que, se você é capaz de verificar a igualdade da sub-expressão relevante para zero, você pode decidir se uma expressão pai da divisão é som, e não parece difícil verificar Se uma sub-expressão de $ \ ln $ é positivo ou negativo se é conhecido não ser zero.

Eu sei que a igualdade na $ \ mathbb R $ geralmente não é decidível, enquanto a igualdade em números algébricos é. No entanto, eu me pergunto como a inclusão de { $ \ exp, \ ln $ } altera o resultado. Eu suspeito que, se existir "casos patológicos", onde duas expressões com estrutura drasticamente diferente resultarem para o mesmo número real, a verificação da igualdade entre eles pode ser indecável, como a $ \ exp $ < / span> e $ \ ln $ pode dificultar a normalização de tais expressões.

(uma nota lateral: postei uma versão anterior de uma pergunta com intenção semelhante aqui , mas acabou por ter um pouco de pensamento por trás dele e tinha desnecessário (= não relacionado à carne da pergunta) complicações com logaritmos complexos.)

Answer 1

Eu não sei, mas suspeito que seja uma pergunta aberta.

Se o teoria dos reais com função exponencial é decidível, então seu problema é decidível também. Sabe-se que se a conjectura de Shanuel detenha, então o primeiro é decidível, então o seu problema é também.

Se eu entender corretamente, o papel a seguir aborda seu problema:

O problema de identidade para funções e constantes elementares . Dan Richardson, John Fitch. Issac '94.

Parece que eles mostram um procedimento que sempre termina se a conjectura de Shanuel detém; E se não terminar para uma expressão particular, poderemos extrair dessa expressão uma contra-exemplo para a conjectura de Shanuel. Eles então argumentam que parece improvável que encontraremos um contraexemplo em breve, então parece improvável encontraremos entradas em que esse procedimento não termina em breve.

ver também https://mathoverflow.net/q118972/37212 e https://mathoverflow.net/q/129563/37212 e https://mathoverflow.net/q/145299/37212 .