The Computational Power of Infinite Time Blum–Shub–Smale Machines

P. Koepke; A. S. Morozov

doi:10.1007/s10469-017-9425-x

The Computational Power of Infinite Time Blum–Shub–Smale Machines

P. Koepke, A. S. Morozov

Кафедра дискретной математики и информатики ММФ и СУНЦ

Результат исследования: Научные публикации в периодических изданиях › статья › рецензирование

3 Цитирования (Scopus)

Аннотация

Functions that are computable on infinite time Blum–Shub–Smale machines (ITBM) are characterized via iterated Turing jumps, and we propose a normal form for these functions. It is also proved that the set of ITBM computable reals coincides with ℝ∩L_ωω.

Язык оригинала	английский
Страницы (с-по)	37-62
Число страниц	26
Журнал	Algebra and Logic
Том	56
Номер выпуска	1
DOI	https://doi.org/10.1007/s10469-017-9425-x
Состояние	Опубликовано - 1 мар 2017

Доступ к документу

10.1007/s10469-017-9425-x

Link to publication in Scopus

Цитировать

@article{71708e64c2b249178cdcfdd5c0316f79,

title = "The Computational Power of Infinite Time Blum–Shub–Smale Machines",

abstract = "Functions that are computable on infinite time Blum–Shub–Smale machines (ITBM) are characterized via iterated Turing jumps, and we propose a normal form for these functions. It is also proved that the set of ITBM computable reals coincides with ℝ∩Lωω.",

keywords = "BSS machines, computable reals, infinite computations, infinite time Blum–Shub–Smale machines, ITBM, iterated jump, infinite time Blum-Shub-Smale machines",

author = "P. Koepke and Morozov, {A. S.}",

year = "2017",

month = mar,

day = "1",

doi = "10.1007/s10469-017-9425-x",

language = "English",

volume = "56",

pages = "37--62",

journal = "Algebra and Logic",

issn = "0002-5232",

publisher = "Springer US",

number = "1",

}

TY - JOUR

T1 - The Computational Power of Infinite Time Blum–Shub–Smale Machines

AU - Koepke, P.

AU - Morozov, A. S.

PY - 2017/3/1

Y1 - 2017/3/1

N2 - Functions that are computable on infinite time Blum–Shub–Smale machines (ITBM) are characterized via iterated Turing jumps, and we propose a normal form for these functions. It is also proved that the set of ITBM computable reals coincides with ℝ∩Lωω.

AB - Functions that are computable on infinite time Blum–Shub–Smale machines (ITBM) are characterized via iterated Turing jumps, and we propose a normal form for these functions. It is also proved that the set of ITBM computable reals coincides with ℝ∩Lωω.

KW - BSS machines

KW - computable reals

KW - infinite computations

KW - infinite time Blum–Shub–Smale machines

KW - ITBM

KW - iterated jump

KW - infinite time Blum-Shub-Smale machines

UR - http://www.scopus.com/inward/record.url?scp=85018758553&partnerID=8YFLogxK

U2 - 10.1007/s10469-017-9425-x

DO - 10.1007/s10469-017-9425-x

M3 - Article

AN - SCOPUS:85018758553

VL - 56

SP - 37

EP - 62

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 1

ER -

The Computational Power of Infinite Time Blum–Shub–Smale Machines

Аннотация

Доступ к документу

Fingerprint

Цитировать