RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Izv. RAN. Ser. Mat.: Year: Volume: Issue: Page: Find

 Izv. Akad. Nauk SSSR Ser. Mat., 1991, Volume 55, Issue 2, Pages 227–253 (Mi izv1008)

On ways of characterizing complete sets

V. K. Bulitko

Abstract: The traditional method for constructing criteria for completeness with respect to reducibility is by describing the property of (in general, weakened) productiveness satisfied by the complement of a set which is complete with respect to the given reducibility. Originally this property was tied to the reducibility of a creative set to the complete set. Such a method appeals directly to the universality of the creative set in the class of all recursively enumerable sets.
However, for several reducibilities it is possible to determine the completeness of a recursively enumerable set from the fact that a certain set of degree below the degree of the creative sets is reducible to the given set. This second, “test” set is, of course, not recursively enumerable. In addition, in place of the property of effective nonrecursive enumerability which productive sets have, it is possible to substitute variants of the property of diagonal nonrecursiveness, although not for all reducibilities.
In this paper we examine the connection between these two approaches – specifically, between different weakenings of the property of productiveness on the one hand, and diagonal nonrecursiveness on the other – and we present results obtained by these methods for Turing and truth-table reducibilities.

Full text: PDF file (1581 kB)
References: PDF file   HTML file

English version:
Mathematics of the USSR-Izvestiya, 1992, 38:2, 225–249

Bibliographic databases:

UDC: 517.11+518.5
MSC: 03D25

Citation: V. K. Bulitko, “On ways of characterizing complete sets”, Izv. Akad. Nauk SSSR Ser. Mat., 55:2 (1991), 227–253; Math. USSR-Izv., 38:2 (1992), 225–249

Citation in format AMSBIB
\Bibitem{Bul91} \by V.~K.~Bulitko \paper On ways of characterizing complete sets \jour Izv. Akad. Nauk SSSR Ser. Mat. \yr 1991 \vol 55 \issue 2 \pages 227--253 \mathnet{http://mi.mathnet.ru/izv1008} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=1133297} \zmath{https://zbmath.org/?q=an:0743.03032} \adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?1992IzMat..38..225B} \transl \jour Math. USSR-Izv. \yr 1992 \vol 38 \issue 2 \pages 225--249 \crossref{https://doi.org/10.1070/IM1992v038n02ABEH002197} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=A1992HR86300001} 

• http://mi.mathnet.ru/eng/izv1008
• http://mi.mathnet.ru/eng/izv/v55/i2/p227

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles
Erratum

This publication is cited in the following articles:
1. V. K. Bulitko, “Letter to the editor”, Russian Acad. Sci. Izv. Math., 41:1 (1993), 185–185
2. R. Sh. Omanadze, “Complexity properties of recursively enumerable sets and $sQ$-completeness”, Math. Notes, 62:3 (1997), 356–359
3. R. Sh. Omanadze, “Complexity properties of recursively enumerable sets and $bsQ$-completeness”, Math. Notes, 68:4 (2000), 476–480
•  Number of views: This page: 149 Full text: 60 References: 26 First page: 1