Recursive functions in group theory
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).
scientific article; zbMATH DE number 3959414