Computable permutations and word problems
Andrey Morozov
Sobolev Institute of Mathematics, Novosibirsk, Russian FederationPaul Schupp
University of Illinois at Urbana-Champaign, USA
Abstract
This is an expository paper whose goal is to explain some interesting interconnections between group theory and the theory of computability. Let denote the group of all computable permutations of . A basic question is: What can one say about the finitely generated subgroups of ? 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.
Cite this article
Andrey Morozov, Paul Schupp, Computable permutations and word problems. Enseign. Math. 64 (2018), no. 1/2, pp. 143–160
DOI 10.4171/LEM/64-1/2-6