Перестановки и неявная определимость

Устанавливается связь между элементарными свойствами групп всех перестановок множества натуральных чисел, степень которых не превосходит некоторой фиксированной тьюринговой степени, и неявной определимостью. Вычислена алгоритмическая сложность таких групп. Выяснено, что многие из них могут быть охарактеризованы в классе всех таких групп с помощью единственной формулы.