Recursive functions in group theory
type: Item
instance of: scholarly article
title: Recursive functions in group theory
zbMATH Open document ID: 0596.03052
author: Vardeman G. Moore
published in: Illinois Journal of Mathematics
publication date: 1986-01-01T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 03D80
Mathematics Subject Classification ID: 20F10
Mathematics Subject Classification ID: 03D20
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D45
Mathematics Subject Classification ID: 20F05
Mathematics Subject Classification ID: 20E06
zbMATH DE Number: 3959414
zbMATH Keywords: partial recursive function
zbMATH Keywords: parametric equation
zbMATH Keywords: recursively presented group
zbMATH Keywords: finitely presented group
zbMATH Keywords: word problem
MaRDI profile type: MaRDI publication profile
description: scientific article; zbMATH DE number 3959414