No CrossRef data available.
Article contents
PERMUTATIONS OF THE INTEGERS INDUCE ONLY THE TRIVIAL AUTOMORPHISM OF THE TURING DEGREES
Published online by Cambridge University Press: 07 August 2018
Abstract
Is there a nontrivial automorphism of the Turing degrees? It is a major open problem of computability theory. Past results have limited how nontrivial automorphisms could possibly be. Here we consider instead how an automorphism might be induced by a function on reals, or even by a function on integers. We show that a permutation of ω cannot induce any nontrivial automorphism of the Turing degrees of members of 2ω, and in fact any permutation that induces the trivial automorphism must be computable.
A main idea of the proof is to consider the members of 2ω to be probabilities, and use statistics: from random outcomes from a distribution we can compute that distribution, but not much more.
Keywords
- Type
- Articles
- Information
- Copyright
- Copyright © The Association for Symbolic Logic 2018
References
REFERENCES
Anderson, B. A., Automorphisms of the truth-table degrees are fixed on a cone. Journal of Symbolic Logic, vol. 74 (2009), no. 2, pp. 679–688.CrossRefGoogle Scholar
Bienvenu, L., Hoyrup, M., and Shen, A., Layerwise computability and image randomness. Theory of Computing Systems, vol. 61 (2017), no. 4, pp. 1353–1375.CrossRefGoogle Scholar
Bienvenu, L. and Porter, C., Strong reductions in effective randomness. Theoretical Computer Science, vol. 459 (2012), pp. 55–68.CrossRefGoogle Scholar
Cai, M., Ganchev, H. A., Lempp, S., Miller, J. S., and Soskova, M. I., Defining totality in the enumeration degrees. Journal of the American Mathematical Society, vol. 29 (2016), no. 4, pp. 1051–1067.CrossRefGoogle Scholar
Cooper, S. B., The Turing Universe is not Rigid, University of Leeds, Pure Mathematics, Preprint Series 16, 1997 (revised February 1998).Google Scholar
de Leeuw, K., Moore, E. F., Shannon, C. E., and Shapiro, N., Computability by probabilistic machines, Automata Studies (Shannon, C. E. and McCarthy, J., editors), Annals of Mathematics Studies, vol. 34, Princeton University Press, Princeton, NJ, 1956, pp. 183–212.Google Scholar
Ershov, J. L., The upper semilattice of numerations of a finite set. Algebra i Logika, vol. 14 (1975), no. 3, pp. 258–284, 368.CrossRefGoogle Scholar
Federer, H., Geometric Measure Theory, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag, New York, 1969.Google Scholar
Haught, C. A. and Slaman, T. A., Automorphisms in the PTIME-Turing degrees of recursive sets. Annals of Pure and Applied Logic, vol. 84 (1997), no. 1, pp. 139–152, Fifth Asian Logic Conference (Singapore, 1993).Google Scholar
Hoyrup, M. and Rojas, C., Applications of effective probability theory to Martin-Löf randomness, Automata, Languages and Programming. Part I, Lecture Notes in Computer Science, vol. 5555, Springer, Berlin, 2009, pp. 549–561.CrossRefGoogle Scholar
Jockusch, C. G. Jr. and Solovay, R. M., Fixed points of jump preserving automorphisms of degrees. Israel Journal of Mathematics, vol. 26 (1977), no. 1, pp. 91–94.CrossRefGoogle Scholar
Kent, C. F., Constructive analogues of the group of permutations of the natural numbers. Transactions of the American Mathematical Society, vol. 104 (1962), pp. 347–362.CrossRefGoogle Scholar
Kent, C. F., Algebraic structure of some groups of recursive permutations, Ph.D. thesis, Massachusetts Institute of Technology, ProQuest LLC, Ann Arbor, MI, 1961.Google Scholar
Kjos-Hanssen, B., The probability distribution as a computational resource for randomness testing. The Journal of Analysis, vol. 2 (2010), pp. 10–13.Google Scholar
Kjos-Hanssen, B., Permutations of the integers induce only the trivial automorphism of the Turing degrees, Computability and Complexity, Lecture Notes in Computer Science, vol. 10010, Springer, Cham, 2017, pp. 599–607.CrossRefGoogle Scholar
Kjos-Hanssen, B., A rigid cone in the truth-table degrees with jump, Computability and Complexity, Lecture Notes in Computer Science, vol. 10010, Springer, Cham, 2017, pp. 487–500.CrossRefGoogle Scholar
Miller, B., The existence of measures of a given cocycle. I. Atomless, ergodic σ-finite measures. Ergodic Theory and Dynamical Systems, vol. 28 (2008), no. 5, pp. 1599–1613.Google Scholar
Nerode, A. and Shore, R. A., Reducibility orderings: Theories, definability and automorphisms. Annals of Mathematical Logic, vol. 18 (1980), no. 1, pp. 61–89.CrossRefGoogle Scholar
Odifreddi, P., The structure of m-degrees, Recursion Theory Week (Oberwolfach, 1984), Lecture Notes in Mathematics, vol. 1141, Springer, Berlin, 1985, pp. 315–332.CrossRefGoogle Scholar
Palyutin, E. A., A supplement to Ju. L. Eršov’s article: “The upper semilattice of numerations of a finite set” (Algebra i Logika 14(1975), no. 3, 258–284). Algebra i Logika, vol. 14 (1975), no. 3, pp. 284–287, 368.CrossRefGoogle Scholar
Rogers, H. Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967.Google Scholar
Sacks, G. E., Degrees of Unsolvability, Princeton University Press, Princeton, NJ, 1963.Google Scholar
Shore, R. A., Rigidity and biinterpretability in the hyperdegrees, Computational Prospects of Infinity. Part II. Presented Talks, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, vol. 15, World Scientific Publishing, Hackensack, NJ, 2008, pp. 299–312.CrossRefGoogle Scholar
Simmons, D., Conditional measures and conditional expectation; Rohlin’s disintegration theorem. Discrete & Continuous Dynamical Systems, vol. 32 (2012), no. 7, pp. 2565–2582.CrossRefGoogle Scholar
Slaman, T. A., Global properties of the Turing degrees and the Turing jump, Computational Prospects of Infinity. Part I. Tutorials, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, vol. 14, World Scientific Publishing, Hackensack, NJ, 2008, pp. 83–101.CrossRefGoogle Scholar