Recursive functions in group theory
finitely presented groupparametric equationpartial recursive functionrecursively presented groupword problem
Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Theory of numerations, effectively presented structures (03D45) Applications of computability and recursion theory (03D80) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
The following three results are proved, the first of which generalizes a result of W. W. Boone and G. Higman [see: \textit{W. W. Boone}, Lect. Notes Math. 372, 90-102 (1974; Zbl 0298.20027)]. Theorem 2: A subset S of a finitely generated, recursively presented group G is recursively enumerable if and only if there is a finitely presented group H containing G, and a parametric expression f(x) over H (that is, an element of \(H*<x>)\) such that, for all \(h\in H\), \(f(h)=1\) if and only if \(h\in S.\) Theorem 3: A partial function \(\phi\) :G\(\to G\) (G as in Theorem 2) is partial recursive if and only if there is a finitely presented group H containing G and a parametric expression \(f(x)\in H*<x>\) such that \(f(h)=\phi (h)\) whenever \(\phi\) (h) is defined, and f(h)\(\not\in G\) otherwise. Theorem 4: A finitely generated group G has solvable word problem if and only if there is a finitely presented group H containing G, and a universal parametric expression p(z,y)\(\in H*<z,y>\) such that every partial recursive function \(\phi\) :G\(\to G\) is represented by the parametric expression \(f(x)=p(g,x)\) for some \(g\in H\) (in the sense that the conditions of Theorem 3 are satisfied).
- Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I
- Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups
- Groups with a Recursively Enumerable Irreducible Word Problem
- Computability of finite quotients of finitely generated groups
- On subgroup distortion in finitely presented groups
This page was built for publication: Recursive functions in group theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1078177)
