Department of Mathematics and Statistics Bar-Ilan University Mathematics Colloquium Note change in time: 11 am Prof. Stuart Margolis Bar Ilan University Note change in time: 11 am Some Surprising Undecidable Problems for Finite Groups and Semigroups Sunday, 10 november 2002 11:00 am Light refreshments served at 10:45 am Abstract: The following talk was given at the algebra seminar. This version of the talk will not assume any backgound in algebra, logic or computability theory. The formal notion of algorithm introduced by Turing, Godel, Church and other mathematicians in the 1930's and their complexity theoretic counterparts introduced by Cook, Karp and other computer scientists in the 1970's has had profound impact on almost all of mathematics and science. Still, many mathematicians feel that undecidable problems are an unnatural collection of problems. The purpose of this talk is to present a number of very natural problems about finite groups and semigroups that turn out to be undecidable. We list two problems here as examples: Problem 1: SUBGRAPHS OF FINITE CAYLEY GRAPHS Given a finite graph G with edges labelled by a finite alphabet X, is G embeddable into the Cayley graph of some finite group? The problem is undecidable- that is the collection of subgraphs of Cayley graphs of finite groups is not decidable. There are relative versions of this problem: It IS decidable if a finite graph is embeddable into the Cayley graph of a finite commutative group, but NOT decidable if a finite graph is embeddable into the Cayley graph of a finite nilpotent group. Problem 2: SUBCATEGORIES OF FINITE GROUPOIDS A groupoid is a (small) category such that each morphism is an isomorphism. Thus a groupoid with one object is a group. One of the first easy theorems we learn in an algebra course is that a subsemigroup of a finite group is itself a group. Clearly one can test if the multiplication table of a finite semigroup is a group. However the generalization to groupoids is undecidable: The class of subcategories of finite groupoids is undecidable.That is there is no algorithm to decide if a given finite category is a subcategory of a finite groupoid. Again, there are relativized versions whose decidability depends on the maximal subgroups of the groupoids in question. All of the problems are clever reductions of other known undecidable problems. The talk follows from work of Hall, Kublanovsky, Margolis, Sapir, B. Steinberg, Trotter among others. --------------------------------------------------------- TechnionMathNet2 TECHMATH2 Editor:Michael Cwikel Announcement from: Mikhail Katz