Logo

Mathematical Sciences Research Institute

Home » DDC - Computability Theory: The word problem for groups

Seminar

DDC - Computability Theory: The word problem for groups September 10, 2020 (09:00 AM PDT - 10:00 AM PDT)
Parent Program:
Location: MSRI: Online/Virtual
Speaker(s) Meng-Che Ho (Purdue University)
Description

Hilbert’s Tenth Problem was the only decision problem among his twenty-three problems. Precise mathematical theory of (in)computability and its interaction with number theory led to the negative solution of the problem. The seminar will focus on modern topics on computability-theoretic phenomena in number-theoretic and other algebraic and model-theoretic structures.

To participate in this seminar, please register here: https://www.msri.org/seminars/25206

Video

The Word Problem For Groups

Abstract/Media

To participate in this seminar, please register here: https://www.msri.org/seminars/25206

In 1911, Max Dehn proposed the word problem for groups, which asks if there is an algorithm deciding whether two words represent the same element in a given group. This was answered in the negative by Novikov and Boone independently. Still, “most” groups have a decidable word problem, and we will discuss the complexities of these word problems in the context of formal language theory. Surprisingly, there is a very nice correspondence between the language-theoretic Chomsky hierarchy and the classes of groups. We will discuss some past and recent results in this direction.

No Notes/Supplements Uploaded

The Word Problem For Groups

H.264 Video 25191_28689_8491_The_Word_Problem_for_Groups.mp4