Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-06T10:14:12.477Z Has data issue: false hasContentIssue false
  • English
  • Français

Hierarchies of Computable groups and the word problem1

Published online by Cambridge University Press:  12 March 2014

Frank B. Cannonito
Frank B. Cannonito*
Affiliation:
Hughes Aircraft Company, Fullerton, California
Get access Rights & Permissions [Opens in a new window]

Extract

The word problem for groups was first formulated by M. Dehn [1], who gave a solution for the fundamental groups of a closed orientable surface of genus g ≧ 2. In the following years solutions were given, for example, for groups with one defining relator [2], free groups, free products of groups with a solvable word problem and, in certain cases, free products of groups with amalgamated subgroups [3], [4], [5]. During the period 1953–1957, it was shown independently by Novikov and Boone that the word problem for groups is recursively undecidable [6], [7]; granting Church's Thesis [8], their work implies that the word problem for groups is effectively undecidable.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 31 , Issue 3 , 02 September 1966 , pp. 376 - 392
Copyright
Copyright © Association for Symbolic Logic 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

This work was supported by the Air Force Systems Command, Research and Technology Division, Rome Air Development Center, Griffiss Air Force Base, New York, 13442, under contract AF 30(602)-3339, and forms a portion of the author's doctoral dissertation at Adelphi University.

References

[I]Dehn, M., Über unendliche diskontinuerliche Gruppen, Mathematische Annalen, vol. 71 (1911), pp. 116–144.CrossRefGoogle Scholar
[2]Magnus, W., Das Identitätsproblem für Gruppen mit einer definierenden Relation, Mathematische Annalen, vol. 106 (1932), pp. 295–307.CrossRefGoogle Scholar
[3] J. Britton, L., Solution of the word problem for certain types of groups, I, Proceedings of the Glasgow Mathematical Association, vol. 3 (1956), pp. 45–54.CrossRefGoogle Scholar
[4]Greendlinger, M., Dehn's algorithm for the word problem, Communications on pure and applied mathematics, vol. XIII (1960), pp. 67–83.CrossRefGoogle Scholar
[5]Lipschutz, S., An extension of Greendlinger's results on the word problem, Proceedings of the American Mathematical Society, vol. 15 (1964), pp. 37–43.Google Scholar
[6]Novikov, P. S., On the algorithmic unsolvability of the word problem in group theory, Akademya Nauk S.S.S.R. Matematicheskii Institut Trudy, vol. 44 (1955).Google Scholar
[7]Boone, W. W., The word problem, Annals of mathematics, vol. 70 (1959), pp. 207–265.CrossRefGoogle Scholar
[8]Church, A., An unsolvable problem of elementary number theory, American journal of mathematics, vol. 58 (1936), pp. 345–363.CrossRefGoogle Scholar
[9]Rabin, M. O., Computable algebra, general theory and theory of computable fields, Transactions of the American Mathematical Society, vol. 95 (1960), pp. 341–360.Google Scholar
[10]Grzegorczyk, A., Some classes of recursive functions, Rozprawy Mathmetyczne, vol. 4 (1953), 46 pp.Google Scholar
[11]Kleene, S. C., Introduction to metamathematics, Van Nostrana (1952).Google Scholar
[12]Axt, P., Enumeration and the Grzegorczyk hierarchy, Zeitschrift für mathematischen Logik und Grundlagen der Mathematik, vol. 9 (1963), pp. 53–65.CrossRefGoogle Scholar
[13]Kleene, S. C., Recursive predicates and quantifiers, Transactions of the American Mathematical Society, vol. 53 (1943), pp. 41–73.CrossRefGoogle Scholar
[14]Boone, W. W., Partial results regarding word problems and recursively enumerable degrees of unsolvability, Bulletin of the American Mathematical Society, vol. 68 (1962), pp. 616–623.CrossRefGoogle Scholar
[15]Higman, G., Subgroups of finitely presented groups, Proceedings of the Royal Society, A, vol. 262 (1961), pp. 455–475.Google Scholar