Finite generability of some groups of recursive permutations

S. A. Volkov

Diskretnaya Matematika, Tome 20 (2008) no. 4, pp. 61-78

Résumé

Let a class $\mathcal Q$ of functions of natural argument be closed with respect to a superposition and contain the identity function. The set of permutations $f$ such that $f,f^{-1}\in\mathcal Q$ forms a group (with respect to the operation of composition) which we denote by $Gr(\mathcal Q)$. We prove the finite generability of $Gr(\mathcal Q)$ for a large family of classes $\mathcal Q$ satisfying some conditions. As an example, we consider the class $\mathrm{FP}$ of functions which are computable in polynomial time by a Turing machine. The obtained result is generalised to the classes $\mathscr E^n$ of the Grzegorczyk system, $n\ge2$. It is proved that for the considered classes $\mathcal Q$ the minimum number of permutations generating the group $Gr(\mathcal Q)$ is equal to two. More exactly, there exist two permutations of the given group such that any permutation of this group can be obtained by compositions of these permutations.