Семейство с единственной минимальной, но не наименьшей нумерацией
Семейство с единственной минимальной, но не наименьшей нумерацией
Сибирский математический журнал, 65, 2, 395-407 (2024)
Аннотация:
Доказывается существование семейства вычислимо перечислимых множеств, обладающего единственной с точностью до эквивалентности вычислимой минимальной, но не наименьшей нумерацией.
Литература:
- Badaev S. A., Goncharov S. S. On computable minimal enumerations // Algebra. Proc. third Int. Conf. Algebra, memory M. I. Kargopolov. Berlin; New York: Walter de Gruyter, 1995. P. 21–32.
- Badaev S. A., Goncharov S. S. Theory of numberings: open problems // Computability theory and its applications, P. Cholak (ed.) et al. Providence, RI: Am. Math. Soc., 2000. P. 23–38. (Contemp. Math. 257).
- Марченков С. С. О вычислимых нумерациях семейств общерекурсивных функций // Алгебра и логика. 1972. Т. 11, № 5. С. 588–607.
- Гончаров С. С. Вычислимые однозначные нумерации // Алгебра и логика. 1980. Т. 19, № 5. С. 507–551.
- Гончаров С. С. Позитивные вычислимые нумерации // Докл. АН СССР. 1993. Т. 332, № 2. С. 142–143.
- Гончаров С. С. Семейство с единственной однозначной, но не наименьшей нумерацией // Тр. Ин-та математики. 1988. Т. 8. С. 42–58.
- Гончаров С. С. Семейства с единственной позитивной нумерацией // Вычисл. системы. 1992. № 146. С. 96–104.
- Goncharov S. S., Harizanov V., Knight J., McCoy C., Miller R., Solomon R. Enumerations in computable structure theory // Ann. Pure Appl. Logic. 2005. V. 136, N 3. P. 219–246.
- Hirschfeldt D. R. Degree spectra of relations on computable structures // Bull. Symb. Logic. 2000. V. 6, N 2. P. 197–212.
- Ершов Ю. Л. Теория нумераций. М.: Наука, 1977.
- Ершов Ю. Л. Нумерации семейств общерекурсивных функций // Сиб. мат. журн. 1967. Т. 8, № 5. С. 1015–1025.
- Semukhin P. Prime models of finite computable dimension // J. Symb. Logic. 2009. V. 74, N 1. P. 336–348.
- Бадаев С. А. Минимальные нумерации // Тр. Ин-та математики СО РАН. 1993. Т. 25. С. 3–34.
- Бадаев С. А. Минимальные нумерации позитивно вычислимых семейств // Алгебра и логика. 1994. Т. 33, № 3. С. 233–254.
- Вьюгин В. В. О некоторых примерах верхних полурешеток вычислимых нумераций // Алгебра и логика. 1973. Т. 12, № 5. С. 512–529.
- Goncharov S. S., Yakhnis A., Yakhnis V. Some effectively infinite classes of enumerations // Ann. Pure Appl. Logic. 1993. V. 60, N 3. P. 207–235.
- Гончаров С. С., Сорби А. Обобщенно-вычислимые нумерации и нетривиальные полурешетки Роджерс // Алгебра и логика. 1997. Т. 36, № 6. С. 621–641.
- Бадаев С. А., Гончаров С. С. О полурешетках Роджерса семейств арифметических множеств // Алгебра и логика. 2001. Т. 40, № 5. С. 507–522.
- Badaev S. A., Lempp S. A decomposition of the Rogers semilattice of a family of d.c.e. sets // J. Symb. Logic. 2009. V. 74, N 2. P. 618–640.
- Файзрахманов М. Х. Минимальные обобщенно вычислимые нумерации и высокие степени // Сиб. мат. журн. 2017. Т. 58, № 3. С. 710–716.
- Faizrahmanov M. Kh. Extremal numberings and fixed point theorems // Math. Logic Quart. 2022. V. 68, N 4. P. 398–408.
- Файзрахманов М. Х. Две теоремы о минимальных обобщенно-вычислимых нумерациях // Вестн. Моск. ун-та. Сер. 1. Математика, механика. 2023. № 3. С. 28–35.
- Файзрахманов М. Х. О p-универсальных и p-минимальных нумерациях // Сиб. мат. журн. 2022. Т. 63, № 2. С. 440–449.
- Файзрахманов М. Х. Сводимость по перечислимости и позитивная сводимость нумераций семейств арифметических множеств // Сиб. мат. журн. 2023. Т. 64, № 1. С. 204–212.
- Ershov Yu. L. Theory of numberings // E. R. Griffor (ed.), Handbook of computability theory. Amsterdam: Elsevier, 1999. P. 473–503. (Stud. Logic Found. Math.; V. 140).
- 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.
- Soare R. I. Turing computability: theory and applications (theory and applications of computability). Berlin: Springer, 2016.
Работа поддержана грантом Российского научного фонда (проект № 23-21-00181) и выполнена в рамках реализации программы развития Научно-образовательного математического центра Приволжского федерального округа (соглашение № 075-02-2023-944).
Файзрахманов Марат Хайдарович (ORCID 0000-0002-4519-9696)
- Казанский (Приволжский) федеральный университет,
ул. Кремлевская, 18, Казань 420008
E-mail: marat.faizrahmanov@gmail.com
Статья поступила 27 апреля 2023 г.
После доработки — 1 октября 2023 г.
Принята к публикации 28 января 2024 г.