DagSemProc.06391.2.pdf
- Filesize: 200 kB
- 20 pages
Document
Real Computational Universality: The Word Problem for a class of groups with infinite presentation
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6391
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2007-01-31
Cite AsGet BibTex
Klaus Meer and Martin Ziegler. Real Computational Universality: The Word Problem for a class of groups with infinite presentation. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 6391, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.06391.2
https://doi.org/10.4230/DagSemProc.06391.2
Abstract
In this talk we introduce a class of groups represented as quotient groups
of some free groups generated by infinitely many elements and certain normal
subgroups. We show that the related word problem is universal in the Blum-Shub-Smale model
of computation, i.e. it has the same difficulty as the real Halting Problem.
This is the first natural example of a problem with this property.
The work has been done jointly with Martin Ziegler.
Keywords
- Computational group theory
- word problem
- Blum-Shub-Smale model
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads