Controlla se due elementi sono uguali dopo la sostituzione

Question

Diciamo che un articolo è un numero naturale o un elenco di elementi. Esempi di articoli sono:

• 1
• [2]
• [4, [3, 1], 3, 4]

Una regola afferma che due elementi sono uguali. Per esempio:

• 1 = 2
• 3 = [3, 1]
• [4, 3] = [1, 5]

Quando si utilizzano queste regole di esempio, possiamo trasformare [4, [3, 2]] in [4, [3, 1]] in [4, 3] in [1, 5] e possiamo dire che [4, [3 [3 , 2]] uguali [1, 5].

Voglio trovare un algoritmo che, dato oggetti $ a $ e $ b $ e un insieme finito di regole, determina se $ a = b $.

Ho già pensato a un algoritmo che funziona in alcuni casi. Ma spero di trovare un algoritmo efficiente che funzioni in tutti i casi. Sarebbe anche bello se l'algoritmo potesse rilevare $ a not = b $ Invece di cercare infinitamente modi per lasciarsi $ a = b $. È un problema noto? Qualsiasi aiuto è apprezzato.

Nota: possiamo semplificare il problema consentendo solo il numero 1 anziché ogni numero naturale. Ciò è equivalente, perché possiamo trasformare 1 in [1], 2 in [1, 1], 3 in [1, 1, 1], eccetera.