Abstract
We prove that every recursively enumerable class of partial recursive functions with infinite domains must have a recursive witness array. The result gives a powerful method for proving properties of recursively enumerable classes. We
show for example that no finitely generated group of recursive permutations can contain all recursive involutions, and neither can it contain all cycle-free recursive permutations.
show for example that no finitely generated group of recursive permutations can contain all recursive involutions, and neither can it contain all cycle-free recursive permutations.
Original language | English |
---|---|
Place of Publication | Utrecht |
Publisher | UU BETA ICS Departement Informatica |
Number of pages | 11 |
Publication status | Published - Jan 2015 |
Publication series
Name | Technical Report Series |
---|---|
Publisher | UU Beta ICS Departement Informatica |
No. | UU-CS-2015-001 |
ISSN (Print) | 0924-3275 |
Keywords
- Recursively enumerable classes
- Rice-Shapiro theorem
- recursive witness arrays
- recursive permutations