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.
Categories: cs.LO math.RA