Publications

Meer, Klaus; Ziegler, Martin: Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation. In: Proc. 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2007), LNCS, volume 4708 , S. 726-737, Jan 2007, Springer Verlag LNCS

Abstract

The word problem for discrete groups is well-known to be undecidable by a Turing Machine; more precisely, it is reducible both to and from and thus equivalent to the discrete Halting Problem. The present work introduces and studies a real extension of the word problem for a certain class of groups which are presented as quotient groups of a free group and a normal subgroup. As main difference with discrete groups, these groups may be generated by UNcountably many generators with index running over certain sets of real numbers. This includes a variety of groups which are not captured by the finite framework of the classical word problem.

Our contribution extends computational group theory from the discrete to the Blum-Shub-Smale (BSS) model of real number computation. It provides a step towards applying BSS theory, in addition to semi-algebraic geometry, also to further areas of mathematics.

The main result establishes the word problem for such groups to be not only semi-decidable (and thus reducible TO) but also reducible FROM the Halting Problem for such machines. It thus gives the first non-trivial example of a problem COMPLETE, that is, computationally universal for this model.

Bibtex

@inproceedings{hniid=3005,
author = {Meer, Klaus and Ziegler, Martin},
title = {Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation},
booktitle = {Proc. 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2007)},
volume = {4708},
series = {LNCS},
pages = {726-737},
publisher = {Springer Verlag LNCS},
month = jan,
year = {2007},
}