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