Computable permutations and word problems

  • Andrey Morozov

    Sobolev Institute of Mathematics, Novosibirsk, Russian Federation
  • Paul 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