П. Кёпке, А. С. Морозов, “О вычислительных возможностях машин Блюм–Шуба–Смэйла, работающих в бесконечном времени”, Алгебра и логика, 2017, том 56, номер 1,страницы 55

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

О вычислительных возможностях машин Блюм–Шуба–Смэйла, работающих в бесконечном времени

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

^a Math. Inst., Rheinische Friedrich-Wilhelms-Univ. Bonn, Endenicher Allee 60, 53115 Bonn, Germany
^b Ин-т матем. им. С. Л. Соболева СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, РОССИЯ
^c Новосибирский гос. ун-т, ул. Пирогова, 2, г. Новосибирск, 630090, РОССИЯ

Аннотация: С помощью итерированных тьюринговых скачков даётся характеризация и предлагается нормальная форма для функций, вычислимых на машинах Блюм–Шуба–Смэйла (ITBM), работающих в бесконечном времени. Также доказывается, что множество ITBM-вычислимых вещественных чисел совпадает с $\mathbb R\cap L_{\omega^\omega}$.

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

УДК: 510.5

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

DOI: 10.17377/alglog.2017.56.103