Login



Other Articles by Authors

Katie Brodhead



Authors and WSEAS

Katie Brodhead


WSEAS Transactions on Mathematics


Print ISSN: 1109-2769
E-ISSN: 2224-2880

Volume 16, 2017

Notice: As of 2014 and for the forthcoming years, the publication frequency/periodicity of WSEAS Journals is adapted to the 'continuously updated' model. What this means is that instead of being separated into issues, new papers will be added on a continuous basis, allowing a more regular flow and shorter publication times. The papers will appear in reverse order, therefore the most recent one will be on top.


Volume 16, 2017



Decidable Effectively Closed Sets and Acceptably Equivalent Numberings

AUTHORS: Katie Brodhead

Download as PDF

ABSTRACT: A Π01 class is an effectively closed set of reals. One way to view it is as the set of infinite paths through a computable tree. We consider the notion of acceptably equivalent numberings of Π01 classes. We show that a permutation exists between any two acceptably equivalent numberings that preserves the computable content. Furthermore the most commonly used numberings of the Π01 classes are acceptably equivalent. We also consider decidable Π01 classes in enumerations. A decidable Π01 class may be represented by a unique computable tree without dead ends, but we show that this tree may not show up in an enumeration of uniformly computable trees which gives rise to all Π01 classes. In fact this is guaranteed to occur for some decidable Π01 class. These results are motivated by structural questions concerning the upper semi-lattice of enumerations of Π01 classes where notions such as acceptable equivalence arise

KEYWORDS: Effectively closed sets, Numberings

REFERENCES:

[1] D. Cenzer, Effectively Closed Sets, ASL Lecture Notes in Logic, to appear.

[2] D. Cenzer and J. Remmel, Index Sets for Π" # Classes, Annals of Pure and Applied Logic, Vol. 93, 1998, pp. 3-61.

[3] D. Cenzer and J. Remmel, Index Sets for Computable Real Functions, Proceed- -ings of CCA03, Cincinnati, Preprint, 2003, pp. 163-182.

[4] Y. Ershov, Theory of Numberings, Handbook of Computability Theory (Edward R. Griffor, ed.), North-Holl- -and, Amsterdam, 1999.

[5] R. Friedberg, Three Theorems on Recursive Enumeration, Journal of Symbolic Logic, Vol. 23, 1958, pp. 309- 316.

[6] S. Goncharov, S. Lempp, and R. Solomon, Friedburg Numberings of Families of n-Computably Enumerable Sets, Algebra and Logic, Vol. 41, 2002, pp. 81-86.

[7] P. Hinman, Recursion-Theoretic Hier- -archies, Springer-Verlag, 1978.

[8] C. Jockusch and R. Soare, Π" # Classes and Degrees of Theories, Transactions of the American Mathematical Society, Vol. 173, 1972, pp. 35-56.

[9] P. Odifreddi, Classical Recursion The- -ory, Vol. 1, North-Holland, Amster- -dam- New York, 1989.

[10] A. Raichev, Relative Randomness via RK-Reducibility, Ph.D. thesis, Uni- -versity of Wisconsin-Madison, 2006.

[11] H. Rogers, Gödel numberings of partial recursive functions, Journal of Symbolic Logic, Vol. 23, 1958, pp. 331-341.

[12] H. Rogers, Theory of recursive functions and effective computability, McGraw Hill, 1967.

[13] R. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987.

[14] Y. Suzuki, Enumerations of recursive sets, Journal of Symbolic Logic, Vol. 24, 1959, pp. 311.

WSEAS Transactions on Mathematics, ISSN / E-ISSN: 1109-2769 / 2224-2880, Volume 16, 2017, Art. #29, pp. 257-265


Copyright © 2017 Author(s) retain the copyright of this article. This article is published under the terms of the Creative Commons Attribution License 4.0

Bulletin Board

Currently:

The editorial board is accepting papers.


WSEAS Main Site