Главные вычислимые нумерации в иерархиях. Universal numberings in Hierarchies.
Keywords:
вычислимые нумерации, главные нумерации, иерархия Ершова, computable numbering, universal numbering, Ershov hierarchy.Abstract
В данной статье рассматриваются немонотонные равномерные вычисления. Показано, что коллекция конечного числа конечных расширений множества в данном классе иерархии Ершова образует главное подмножество этого класса. This article discusses the non-monotonic uniform enumerations. It is shown that the collection of a finitely many finite extensions of a set of the class in the Ershov hierarchy forms a universal subset of the class.References
[1] Абешев, К.Ш., Бадаев, С.A., Заметки об универсальных нумерациях, 5-я Конфереция по вычислимости в европе, CiE 2009, 23-27.
[2] Бадаев, С.A., Гончаров, С.С.: Теория нумерации: Открытые проблемы. В: Чолак, П.A., Лемпп, Ш., Лерман, М., Соар, Р.А. (и т.д.): Теория вычислимости и его приложения. Современные тенденции и открытые проблемы. Амер. Мат. Общ.,(2000) 23-38.
[3] Бадаев, С.А., Гончаров, С.С., Сорби, А.: Арифметические нумерации: полнота и универсальность. В: Купер, С.Б., Гончаров, С.С. : Вычислимость и модели Клювер / Пленум Publishers, Нью-Йорк (2003), 11–44.
[4] Ершов, Ю.Л.: Теория нумерации. Наука, Москва (1977)
[5] Ершов, Ю.Л.: Теория нумерации. В: Справочник по Теории вычислимости. Северная Голландия, Амстердам (1999), 473-–503.
[6] Гончаров, С.С., Сорби А.: Обобщенно вычислимые нумерации и нетривиальные полурешетки Роджерса. // Алгебра и Логика, 1997, vol. 36, no. 6, 621–641 (Russian); [Algebra and Logic, 1997, vol. 36, no. 6, 359–369 (English translation)].
[7] Мальцев, А.И.: К теории вычислимых семейств объектов. // Алгебра и Логика, 1963, том. 3, №4, 5–31.
[2] Бадаев, С.A., Гончаров, С.С.: Теория нумерации: Открытые проблемы. В: Чолак, П.A., Лемпп, Ш., Лерман, М., Соар, Р.А. (и т.д.): Теория вычислимости и его приложения. Современные тенденции и открытые проблемы. Амер. Мат. Общ.,(2000) 23-38.
[3] Бадаев, С.А., Гончаров, С.С., Сорби, А.: Арифметические нумерации: полнота и универсальность. В: Купер, С.Б., Гончаров, С.С. : Вычислимость и модели Клювер / Пленум Publishers, Нью-Йорк (2003), 11–44.
[4] Ершов, Ю.Л.: Теория нумерации. Наука, Москва (1977)
[5] Ершов, Ю.Л.: Теория нумерации. В: Справочник по Теории вычислимости. Северная Голландия, Амстердам (1999), 473-–503.
[6] Гончаров, С.С., Сорби А.: Обобщенно вычислимые нумерации и нетривиальные полурешетки Роджерса. // Алгебра и Логика, 1997, vol. 36, no. 6, 621–641 (Russian); [Algebra and Logic, 1997, vol. 36, no. 6, 359–369 (English translation)].
[7] Мальцев, А.И.: К теории вычислимых семейств объектов. // Алгебра и Логика, 1963, том. 3, №4, 5–31.
Downloads
Issue
Section
Mechanics, Mathematics, Computer Science
