Computable permutations and word problems

Abstract

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.