П. Кёпке, А. С. Морозов, “Характеризации ITBM-вычислимости. I”, Алгебра и логика, 2020, том 59, номер 6,страницы 627

Эта публикация цитируется в 4 статьях

Характеризации ITBM-вычислимости. I

П. Кёпке^a, А. С. Морозов^b

^a Math. Inst., Rheinische Friedrich-Wilhelms-Univ. Bonn, Bonn, GERMANY
^b Ин-т матем. им. С. Л. Соболева СО РАН, г. Новосибирск, РОССИЯ

Аннотация: Изучается выполнимость некоторых хорошо известных свойств частично рекурсивных функций для ITBM-вычислимых функций, т. е. функций, вычислимых на машинах Блюм–Шуба–Смейла и работающих в бесконечном времени. Показывается, что свойства графиков ITBM-вычислимых функций отличаются от обычных свойств графиков частично рекурсивных функций, даётся описание возможных областей значений ITBM-вычислимых функций, а также рассматривается вопрос о существовании ITBM-вычислимых биекций между ITBM-вычислимыми множествами одинаковой мощности.

Ключевые слова: машина Блюм–Шуба–Смейла, ITBM-вычислимые функции, частично рекурсивные функции, график функции.

УДК: 510.5

Поступило: 05.06.2020
Окончательный вариант: 05.03.2021

DOI: 10.33048/alglog.2020.59.602