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.
- Constructive Analogues of the Group of Permutations of the Natural Numbers
- Generic-case complexity, decision problems in group theory, and random walks.
- scientific article; zbMATH DE number 1534357 (Why is no real title available?)
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Recursive Predicates and Quantifiers
- Recursively enumerable sets of positive integers and their decision problems
- Relationships Between Reducibilities
- Turing computability. Theory and applications
- Über die Permutationsgruppe der natürlichen Zahlenfolge
This page was built for publication: Computable permutations and word problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2314871)
