On a question of Slaman and Groszek

On a question of Slaman and Groszek
HTML articles powered by AMS MathViewer

by Andrew E. M. Lewis PDF

Proc. Amer. Math. Soc. 136 (2008), 3663-3668 Request permission

We answer a question of Slaman and Groszek by showing that any non-computable perfect tree computes one of its non-computable paths.

References

S. Barry Cooper, Computability theory, Chapman & Hall/CRC, Boca Raton, FL, 2004. MR 2017461
Harvey Friedman, One hundred and two problems in mathematical logic, J. Symbolic Logic 40 (1975), 113–129. MR 369018, DOI 10.2307/2271891
A. E. M. Lewis, $\Pi ^0_1$ classes, strong minimal covers and hyperimmune-free degrees, Bulletin of the London Mathematical Society, volume 39, number 6 (2007), 892–910.
Andrew E. M. Lewis, A random degree with strong minimal cover, Bull. Lond. Math. Soc. 39 (2007), no. 5, 848–856. MR 2365234, DOI 10.1112/blms/bdm074
—, Strong minimal covers and a question of Yates: the story so far, to appear in the proceedings of the ASL meeting 2006.
Marcia J. Groszek and Theodore A. Slaman, A basis theorem for perfect sets, Bull. Symbolic Logic 4 (1998), no. 2, 204–209. MR 1632148, DOI 10.2307/421023
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7