Computable permutations and word problems (Q2314871): Difference between revisions

Summary: This is an expository paper whose goal is to explain some interesting interconnections between group theory and the theory of computability. Let \(\mathcal C\) denote the group of all computable permutations of \(\mathbb N\). A basic question is: What can one say about the finitely generated subgroups of \(\mathcal C\)? Partially answering this question involves ideas from the theory of computability such as Turing degrees and truth-table degrees. We want to make this paper accessible to both group theorists and computability theorists so we carefully explain all the needed concepts.