Один подход к классификации минимальных нумераций семейств арифметических множеств

Один подход к классификации минимальных нумераций семейств арифметических множеств

Файзрахманов М. Х.
Сибирский математический журнал, 66, 2, 330-338 (2025)
Скачать статью

УДК 510.5 
DOI: 10.33048/smzh.2025.66.214

Аннотация:

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

Литература:
  1. Ершов Ю. Л. Теория нумераций. М.: Наука, 1977.
     
  2. Soare R I. Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Perspectives in mathematical logic. Berlin; Heidelberg; New York, etc.: Springer-Verl., 1987.
     
  3. Гончаров С. С., Сорби А. Обобщенно-вычислимые нумерации и нетривиальные полурешетки Роджерса // Алгебра и логика. 1997. Т. 36, № 6. С. 621–641.
     
  4. Бадаев С. А., Гончаров С. С. О полурешетках Роджерса семейств арифметических множеств // Алгебра и логика. 2001. Т. 40, № 5. С. 507–522.
     
  5. Бадаев С. А. Минимальные нумерации // Тр. Ин-та математики СО РАН. 1993. Т. 25. С. 3–34.
     
  6. Бадаев С. А., Гончаров С. С. Обобщенно вычислимые универсальные нумерации // Алгебра и логика. 2014. Т. 53, № 5. С. 555–569.
     
  7. Badaev S. A., Goncharov S. S. Computability and numberings / Cooper S. B., Löwe B., Sorbi A. (eds). New Computational Paradigms. New York, NY: Springer, 2008.

Работа поддержана грантом Российского научного фонда (проект № 24-11-00227) и выполнена в рамках реализации программы развития Научно-образовательного математического центра Приволжского федерального округа (соглашение № 075-02-2024-1438).

Файзрахманов Марат Хайдарович (ORCID 0000-0002-4519-9696)
  1. Казанский (Приволжский) федеральный университет,
    ул. Кремлевская, 18, Казань 420008

E-mail: marat.faizrahmanov@gmail.com

Статья поступила 17 июня 2024 г.
После доработки — 17 июня 2024 г.
Принята к публикации 25 февраля 2025 г.