The least recursively closed clone
by
Alexander Semigrodskikh
Ural State University, Department of Mathematics and Mechanics, Lenin av. 51, 620083, Yekaterinburg, Russia

The least recursively closed clone is the least set of functions that contains the identity function on the set of all natural numbers with 0 and is closed under composition, primitive recursion, addition of fictitious variables, identification and permutation of variables. We will see that this set contains unexpectedly diverse functions. We say that a finitary function on the set of all natural numbers with 0 is max-bounded if, for arbitrary fixed values of its arguments, the value of this function is not greater than the maximum of the values of the arguments. The results of this talk allow to formulate a conjecture that the least recursively closed clone is exactly the set of all max-bounded primitive recursive functions.

Date received: May 18, 2004