Finite degree clones are undecidable

11/13/2018

∙

by   Matthew Moore, et al.

∙

0

∙

share

A clone of functions on a finite domain determines and is determined by its system of invariant relations (=predicates). When a clone is determined by a finite number of relations, we say that the clone is of finite degree. For each Minsky Machine M we associate a finitely generated clone C such that C has finite degree if and only if M halts, thus proving that deciding whether a given clone has finite degree is impossible.