zbMATH — the first resource for mathematics

The undecidability of the semi-unification problem. (English) Zbl 0769.68059
Summary: The Semi-Unification Problem (SUP) is a natural generalization of both first-order unification and matching. The problem arises in various branches of computer science and logic. Although several special cases of SUP are known to be decidable, the problem in general has been open for several years. We show that SUP in general is undecidable, by reducing what we call the “boundedness problem” of Turing machines to SUP. The undecidability of this boundedness problem is established by a technique developed in the mid-1960s to prove related results about Turing machines.

68Q42 Grammars and rewriting systems
68W30 Symbolic computation and algebraic computation
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
03D35 Undecidability and degrees of sets of sentences
Full Text: DOI