Classifying word problems

Abstract: The study of word problems dates back to the work of Dehn in 1911. Given a recursively presented algebra A, the word problem of A is to decide if two words in the generators of A refer to the same element. Nowadays, much is known about the complexity of word problems for algebraic structures: e.g., the Novikov-Boone theorem – one of the most spectacular applications of computability to general mathematics – states that the word problem for finitely presented groups is unsolvable. Yet, the computability theoretic tools commonly employed to measure the complexity of word problems (e.g., Turing or m-reducibility) are defined for sets, while it is generally acknowledged that many computational facets of word problems emerge only if one interprets them as equivalence relations. In this work, we revisit the world of word problems through the lens of the theory of equivalence relations, which has grown immensely in recent decades. To do so, we employ computable reducibility, a natural effectivization of Borel reducibility. This is joint work with Valentino Delle Rose and Andrea Sorbi.

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.