Finite degree clones are undecidable

Abstract

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 $\mathcal{M}$ we associate a finitely generated clone $\mathcal{C}$ such that $\mathcal{C}$ has finite degree if and only if $\mathcal{M}$ halts, thus proving that deciding whether a given clone has finite degree is impossible.