Undecidability of the Horn-clause implication problem
Jerzy Marcinkowski, Leszek Pacholski · 1992
The authors prove that the problem 'given two Horn clauses H/sub 1/=( alpha /sub 1/ V-product alpha /sub 2/ to beta ) and H/sub 2/=( gamma /sub 1/ V-product . . . V-product gamma /sub k/ to delta ), where alpha /sub i/, beta , gamma /sub i/, delta are atomic formulas, decide if H/sub 2/, is a consequence of H/sub 1/' is not recursive. This solves one of the last open decidability problems concerning formulas in pure predicate logic (i.e. without equality symbol). The proof depends on a thorough analysis of derivation trees of one rule of inference with two premisses and one conclusion, and it may have further applications.>