¿La inyección no es necesaria para algoritmos de unificación?

Question

Al aprender sobre un algoritmo de unificación general, aprendimos la regla descomponer , que los estados unifican

$$ G \ Cup \ {F (A_0, ... A_K)= F (b_0, ..., b_k) \} \ rudowarrow g \ Cup \ {A_0= b_0, ... a_k= b_k \}. $$

La pregunta de, "¿Qué pasa si $ f $ no es inyectivo?" Me destacó. Diga $ f $ no es inyectivo, y atravesamos esa rama del cálculo donde $ f (A_0, ... A_K)= F (b_0, ..., b_k) \ rudotrow \ {a_0= b_0, ..., a_k= b_k \} $ y conduce al fracaso. ¿Es posible que haya otra forma de asignar $ a_0, ..., a_k $ a $ b_0, ... b_k $ tal que es unifiable?

Estaba pensando que tal vez de un ejemplo para demostrar lo que quiero decir. Esto puede no ser un buen ejemplo, pero digamos que consideramos $ f (x, y)= x + y $ , y queremos unificar $ f (h (a), g (b))= f (g (c), h (d)) $ Luego fallaríamos al asignar $ \ {h (a)= g (c), g (b)= h (d) \} $ Al descomponer, pero tener éxito en la unificación si en su lugar, primero cambiamos los argumentos de $ f $ (válido desde $ f (a, b)= f (b, a) $ ), que producirá < Span Class="Math-contenedor"> $ \ {A \ MAPSTO D, B \ MAPSTO C \} $ .

Estaba leyendo un poco en este papel en la página 6, donde discuten la idea de su estrictismo en términos de descomponer, pero no lo entiendo, y sobre lo general, en general, cómo podemos realizar esta etapa de unificación de descomponerse en un general $ F $ Sin de alguna manera retrocediendo el fracaso.

Answer 1

aquí $ f $ no es una función matemática. Más bien, es una Símbolo de función . No piense en $ f (a, b) $ como resultado de evaluar la función en los parámetros $ a, b $ . Más bien, piense en ello como un término en una expresión simbólica: es un objeto sintáctico que no está destinado a interpretarse en la forma en que lo está interpretando.

Si lo desea, puede pensarlo como si cada símbolo de función en una expresión simbólica sea una función inyectiva; Pero eso no es realmente preciso, eso es solo una forma cruda de pensar en expresiones simbólicas.

No puede definir $ f (x)= x + y $ . $ f $ es un símbolo de función no interpretada. No se le permite definir una función particular. Más bien, $ f $ es un stand-in para una función que aún no está definida. Una forma de pensar en ello es que cualquier conclusión de que se extraiga de la unificación, son conclusiones que deben mantener todas las funciones $ f $ (no solo una sola). < / p>