New solution for post problem

About the author:

Alexander N. Degtev, Dr. Physic. and Math. Sci., Professor, Department of Algebra and Mathematical Logic, Institute of Mathematics, Humanities and Information Technologies, Tyumen State University

Abstract:

The article demonstrates the construction of semirecursive recursively enumerable set B, Turing degree of which is between 0 and 1, with the consideration of the fact that for recursively enumerable sets A.

References:

1. Post, E.L. Recursively enumerable sets of positive integers and their decision problem. Bull. Amer. Math. Soc. 1944. Vol. 50. № 5. Pp. 284–318.

2. Muchnik, A.A. Unsolvability of the problem of reducibility for the theory of algorithms. DAN SSSR — DAN USSR. 1956, Vol.108, Pp. 194–197. (in Russian).

3. Friedberg, R.M. Two recursively enumerable sets of incomparable degrees of insolvability. Proc. Natl. Acad. Sci. USA. 1957. Vol.43, Pp. 236–238.

4. Rodzhers, H. Teorija rekursivnyh funkcij i jeffektivnaja vychislimost' [Theory of recursive functions and effective computability], М.: Mir, 1972. (in Russian).

5. Jockusch, C.J. Semirecursive sets and positive reducibility. Trans. Amer. Math. Soc. 1968. Vol. 131. № 2. Pp. 420–436.