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?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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).
answered Mar 28, 2015 at 23:36
-
$\begingroup$ Does it seem right? In any case, welcome to M.O.! $\endgroup$ Commented Mar 29, 2015 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$ Commented Mar 29, 2015 at 22:05