Degrees of Autostability Relative to Strong Constructivizations of Graphs


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

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.

About the authors

N. A. Bazhenov

Sobolev Institute of Mathematics

Author for correspondence.
Email: bazhenov@math.nsc.ru
Russian Federation, Novosibirsk

M. I. Marchuk

Sobolev Institute of Mathematics

Email: bazhenov@math.nsc.ru
Russian Federation, Novosibirsk

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2018 Pleiades Publishing, Ltd.