9
$\begingroup$

E. Post proved that there are only countably many clones on a two-element set (classes of operations closed under superposition and containing all projections). All these clones are finitely generated. Also, each such clone is computable in the sense that we can computably decide does an n-ary function (given its value table) belong to the clone or not. Moreover, the procedure is uniform under arbitrary set of generators.
The situation is different for clones on a finite set of size greater than two: there are continuum many clones on a three-element set (J. I. Janov, A. A. Muchnik) and, therefore, not all of them are finitely generated. Of course, every finitely generated clone is computably enumerable. Are there any known examples of finitely generated clones which are not computable?

$\endgroup$
7
$\begingroup$

Every finitely generated clone on a finite set is computable.

Indeed, fix $k$. If we want to determine which $k$-ary functions belong to the clone $\mathcal C$, we can start generating functions by composition. There are only finitely many functions $f\in F_d$ with a given depth $d$ of the composition tree.

Eventually we find a $d$ such that no new $k$-ary functions were added in going from depth $d$ to $d+1$, i.e., $F_d=F_{d+1}$. Then we know that we have found all the $k$-ary functions in $\mathcal C$, by extensionality (i.e., the principle that if we anywhere substitute expressions representing the same function then we don't change the function represented).

$\endgroup$
  • $\begingroup$ Does it seem right? In any case, welcome to M.O.! $\endgroup$ – Bjørn Kjos-Hanssen Mar 29 '15 at 0:49
  • $\begingroup$ Yes, all is correct. This contasts with the fact that there are non-computable clones with computable set of generators. $\endgroup$ – Iskander Kalimullin Mar 29 '15 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.