Word Problems Are Hard
OTHER MATHEMATICS DEPARTMENT EVENTS: MATH TABLE
When: March 12, 2025
4:30 pm - 5:30 pm
Where: Science Center 507
Address:
1 Oxford Street, Cambridge, MA 02138, United States
Speaker: William Hu - Harvard University
Elementary schoolers think word problems are hard. In 1955, Pyotr Novikov showed that computers also think that (certain types of) word problems are hard. Namely, there exists a group whose word problem is uncomputable: it is impossible to write a computer program that takes as input any word inside that group and determines whether it is equal to the identity element. We will talk about why this result is true, its connections to the analogous problem on semigroups, and other related properties. No familiarity with the notion of computability (or even computers) is needed.
For more information, visit the Harvard Math Table website.