Комбарро Э. Ф.
Классификация подмножеств натуральных чисел при помощи вычислимых перестановок

Вводятся различные определения для понятия вычислимого автоморфизма множества натуральных чисел.
Изучаются соотношения между ними и соотношения между классами традиционно изучаемых в теории вычислимости множеств и их группами автоморфизмов.
Показана нетривиальность классификации множеств посредством групп их автоморфизмов.

Combarro E. F.
On classifying subsets of natural numbers by their computable permutations

We introduce some alternative definitions of the concept of computable automorphism of a set of natural numbers. We study their relationships and investigate whether some classes of sets having isomorphic groups of automorphisms coincide with other classes of sets usual in computability. Finally, we show that the classification of sets by these groups of automorphisms is nontrivial.

Полный текст статьи / Full texts:

• PDF file (455 KB)
• PostScript file (865 KB)