Decidabilità dell'uguaglianza e solidità delle espressioni che coinvolgono elementari aritmetiche ed esponenziali

Question

Diamo espressioni che sono composte da elementi di $ \ mathbbn n $ e un set limitato di operazioni binarie { $ +, \ volte, -, / $ } e funzioni { $ \ exp, \ ln $ }. Le espressioni sono sempre ben formate e formano alberi finiti, con numeri come nodi fogliare e operatori come nodi interni, operazioni binarie con due sotto-espressioni infantile e le funzioni. Un valore di tale espressione è interpretato per significare un certo numero in $ \ MathBB R $ .

Ci sono due limitazioni sulla struttura delle espressioni: il divisore (la sotto-espressione della destra) di $ / $ non può essere 0 e il Argomento di $ \ ln $ deve essere positivo.

Ho due domande su questo tipo di espressioni:

.

• è possibile garantire "solidità" di tale espressione, nel senso che le due limitazioni possono essere controllate in tempo finito?

• è un controllo di uguaglianza tra due espressioni di questo tipo decidabile?

Queste domande sembrano essere connesse nel senso che se sei in grado di verificare l'uguaglianza della sotto-espressione pertinente a zero, è possibile decidere se un'espressione genitore di divisione è il suono, e non sembra difficile controllare Se una sotto-espressione di $ \ ln $ è positivo o negativo se è noto non essere zero.

So che l'uguaglianza in $ \ MathBB R $ generalmente non decidabile, mentre l'uguaglianza nei numeri algebri è. Tuttavia, mi chiedo come l'inclusione di { $ \ exp, \ ln $ } cambia il risultato. Sospetto che, se esistono "casi patologici" in cui due espressioni con una struttura drammaticamente diversa comportano lo stesso numero reale, controllando l'uguaglianza tra loro potrebbe essere indecidabile, come la $ \ exp $ < / span> e $ \ ln $ potrebbe ostacolare la normalizzazione di tali espressioni.

(una nota laterale: ho postato una versione precedente di una domanda con intenti simili qui , ma si è rivelato troppo poco pensò dietro di esso, e non aveva inutile (= non correlato alla carne della domanda) complicazioni con logaritmi complessi.)

Answer 1

Non lo so, ma sospetto che sia una domanda aperta.

Se teoria dei reali con funzione esponenziale è decidabile, quindi il tuo problema è decidabile anche. È noto che se la congettura di Shanuel tiene, allora il primo è decidabile, quindi è anche il tuo problema.

Se capisco correttamente, la seguente carta affronta il tuo problema:

Il problema dell'identità per le funzioni elementari e le costanti . Dan Richardson, John Fitch. ISSAC '94.

Sembra che mostrino una procedura che termina sempre se la congettura di Shanuel detiene; E se non termina per una particolare espressione, allora possiamo estrarre da quell'espressione un controesempio per la congettura di Shanuel. Hanno quindi sostenero che sembra improbabile che troveremo un controesempio in qualsiasi momento presto, quindi sembra improbabile troveremo gli input su cui questa procedura non riesce a terminare presto qualsiasi volta.

Vedi anche https://mathoverflow.net/Q/118972/37212 e Https://mathoverflow.net/q/129563/37212 e https://mathoverflow.net/Q/145299/37212 .