Series: Penn State Logic Seminar

Date: Tuesday, May 17, 2005

Time: 2:30 - 3:45 PM

Place: 123 Pond Laboratory

Speaker: Stephen G. Simpson, Penn State, Mathematics

Title: 

  A Slick Proof of the Unsolvability of the Word Problem for Groups

Abstract:

  A famous theorem of P. Novikov 1955 and W. W. Boone 1959 asserts the
  existence of a finitely presented group with unsolvable word
  problem.  In my Spring 2005 topics course (MATH 574, Topics in
  Mathematical Logic), I presented Boone's proof, as simplified by
  J. L. Britton, 1963.  In this seminar I shall present a truly slick,
  streamlined proof, due to S. Aanderaa and D. E. Cohen, 1980.
  Instead of Turing machines or register machines, the Aanderaa/Cohen
  proof uses another kind of machines, called modular machines, which
  I shall discuss in detail.  In addition, the Aanderaa/Cohen proof
  uses Britton's Lemma.  I shall omit the proof of Britton's Lemma,
  which can be found in my course notes at
  http://www.personal.psu.edu/t20/notes/.