Degrees of Autostability Relative to Strong Constructivizations of Graphs

Standard

Degrees of Autostability Relative to Strong Constructivizations of Graphs. / Bazhenov, N. A.; Marchuk, M. I.

In: Siberian Mathematical Journal, Vol. 59, No. 4, 01.07.2018, p. 565-577.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{c06868847ffb4d49aa557c27b81c2d28,

title = "Degrees of Autostability Relative to Strong Constructivizations of Graphs",

abstract = "We show that each computably enumerable Turing degree is a degree of autostability relative to strong constructivizations for a decidable directed graph. We construct a decidable undirected graph whose autostability spectrum relative to strong constructivizations is equal to the set of all PA-degrees.",

keywords = "autostability, autostability relative to strong constructivizations, autostability spectrum relative to strong constructivizations, computable model, computably enumerable degree, degree of autostability relative to strong constructivizations, graph, PA-degree, strongly constructivizable model",

author = "Bazhenov, {N. A.} and Marchuk, {M. I.}",

note = "Publisher Copyright: {\textcopyright} 2018, Pleiades Publishing, Ltd.",

year = "2018",

month = jul,

day = "1",

doi = "10.1134/S0037446618040018",

language = "English",

volume = "59",

pages = "565--577",

journal = "Siberian Mathematical Journal",

issn = "0037-4466",

publisher = "MAIK NAUKA/INTERPERIODICA/SPRINGER",

number = "4",

}

RIS

TY - JOUR

T1 - Degrees of Autostability Relative to Strong Constructivizations of Graphs

AU - Bazhenov, N. A.

AU - Marchuk, M. I.

PY - 2018/7/1

Y1 - 2018/7/1

N2 - We show that each computably enumerable Turing degree is a degree of autostability relative to strong constructivizations for a decidable directed graph. We construct a decidable undirected graph whose autostability spectrum relative to strong constructivizations is equal to the set of all PA-degrees.

AB - We show that each computably enumerable Turing degree is a degree of autostability relative to strong constructivizations for a decidable directed graph. We construct a decidable undirected graph whose autostability spectrum relative to strong constructivizations is equal to the set of all PA-degrees.

KW - autostability

KW - autostability relative to strong constructivizations

KW - autostability spectrum relative to strong constructivizations

KW - computable model

KW - computably enumerable degree

KW - degree of autostability relative to strong constructivizations

KW - graph

KW - PA-degree

KW - strongly constructivizable model

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

U2 - 10.1134/S0037446618040018

DO - 10.1134/S0037446618040018

M3 - Article

AN - SCOPUS:85053012158

VL - 59

SP - 565

EP - 577

JO - Siberian Mathematical Journal

JF - Siberian Mathematical Journal

SN - 0037-4466

IS - 4

ER -

ID: 16485549