School Seminars and Colloquia

The non-existence of certain search algorithms and their applications to group theory

Set Theory Seminar

by Maurice Chiodo


Institution: Mathematics and Statistics, The University of Melbourne
Date: Thu 23rd April 2009
Time: 4:15 PM
Location: Room 107, Richard Berry Building, The University of Melbourne

Abstract: In this talk I will give a proof of the non-existence of some well
defined search algorithms, using the tools of recursion theory. More
specifically, I shall look at the problem of finding an element
outside the halting set of Turing machine. This will be used to give a
partial result in group theory that leads towards my (still unproved)
conjecture "There exists no general algorithm that, on input of of a
finite group presentation that describes a non trivial group, outputs
a word on the generators that represents a non trivial element".

For More Information: for further information please contact Greg Hjorth on email g.hjorth@ms.unimelb.edu.au