Некоторые свойства вычислимых нумераций семейств всюду определенных функций в арифметической иерархии. Some properties of computable numberings of the families of total functions in the arithmetical hierarchy

Abstract

Используя обобщенное понятие ∑0¦(n|+2) -вычислимой нумерации для семейств функций в арифметической иерархии и на основе диагональных методов было доказано, что существуют семейство F всюду определенных функций и ∑0¦(n|+2) -вычислимая нумерация α семейства F такие, что никакая нумерация Фридберга семейства F не сводится к α . А также, что если семейство F всюду определенных функций содержит по крайней мере две функций, то F не имеет∑0¦(n|+2) -вычислимую главную нумерацию. Using a generalized notion of ∑0¦(n|+2) -computable numbering for the families of functions in the arithmetical hierarchy and on the basis of diagonal methods, it has been proved that there are a family F of total functions and ∑0¦(n|+2) -computable numbering α of the family F such that no Friedberg numbering of F is reducible to α . And also it has been proved that if the family F of total functions contains at least two functions, then F has no principal ∑0¦(n|+2) -computable numbering.