Il Problema della Parola

Come è ben noto, ogni gruppo $G$ è quoziente di un gruppo libero $F = F(S)$, pertanto è possibile darne una descrizione in termini di generatori e relazioni, in simboli $$G =\langle S \;| \; R \rangle.$$ Gli elementi di $G$ sono parole nei generatori $S$, soggette alle relazioni imposte dall'insieme $R$. Questa è detta una "presentazione" di $G$, e il gruppo si dice "finitamente presentato" se esiste almeno una presentazione tale che $S$ e $R$ hanno entrambi cardinalità finita.

Chiaramente, ogni gruppo finito è finitamente presentato. Ad esempio, il gruppo ciclico di ordine $n$ e il gruppo diedrale di ordine $2n$ hanno rispettive presentazioni $$C_n = \langle x \;| \; x^n=1 \rangle, \quad D_{2n} = \langle x, \, y \;| \; x^n=y^2=(xy)^2=1 \rangle.$$

Lo studio dei gruppi tramite le loro presentazioni costituisce quella che si chiama teoria combinatoria dei gruppi, e uno dei problemi più importanti in tale area è il famoso

Problema della parola. Dato un gruppo finitamente presentato, esiste un algoritmo che permetta di stabilire se due parole rappresentino lo stesso elemento (o, equivalentemente, se una parola rappresenta l'elemento neutro)?

Se gli elementi di $G$ ammettono una unica "forma normale", allora il problema della parola ha risposta affermativa, dato che per stabilire se due parole sono uguali basta confrontarne le rispettive forme normali. Ad esempio, ogni parola nel gruppo diedrale può essere ricondotta alla forma $x^ky^m$, con $k \in \{0, \ldots, n-1\}$ e $m \in \{0, \, 1\}$, e due parole $x^ky^m$,  $x^hy^n$ sono uguali se e solo se $k=h$ e $m=n$.

Il primo a rendersi conto che il problema della parola è importante di per sé, indipendentemente dal particolare gruppo a cui viene applicato, fu M. Dehn (già famoso per avere risolto in senso negativo il terzo problema di Hilbert sull'equiscomponibilità dei poliedri di egual volume) che, nel 1912, fornì anche un algoritmo (basato su tecniche di geometria iperbolica) per risolvere il problema della parola nel caso del gruppo fondamentale di una superficie chiusa, compatta e orientabile di genere almeno $2$.

Quasi quarant'anni dopo, nel 1955, P. Novikov dimostrò che, in generale, il problema della parola è indecidibile anche nel caso di gruppi finitamente presentati [5]; tre anni dopo, un'altra dimostrazione dello stesso fatto venne fornita da W.W. Boone [2]. Si trattava di un risultato sorprendente, in quanto esso forniva il primo esempio di indecidibilità che appariva non in Logica o in Informatica, ma in una branca centrale della matematica come l'Algebra. Successivamente, vari altri autori hanno esplorato i profondi legami che intercorrono fra la teoria combinatoria dei gruppi e quella della decidibilità algoritmica.

Un esempio esplicito di gruppo finitamente presentato avente problema della parola indecidibile si può trovare nella voce [1] linkata in fondo: esso ha $10$ generatori e $27$ relazioni (ma esistono anche esempi con sole $14$ o $12$ relazioni).

Si noti che il risultato di indecidibilità di Novikov non esclude che il problema della parola sia decidibile per particolari classi di gruppi finitamente presentati. Infatti,  si conoscono vari esempi per cui ciò accade: i gruppi finiti, i gruppi iperbolici, i gruppi di trecce, i gruppi euclidei, i gruppi liberi, i gruppi liberi abeliani, i gruppi con una sola relazione (questo è un risultato di Magnus che estende quello di Dehn) e i gruppi residualmente finiti.


Riferimenti.

[1] https://en.wikipedia.org/wiki/Word_problem_for_groups
[2] W. W. Boone (1958): The word problem, Proceedings of the National Academy of Sciences 44 (1958), 1061–1065
[3] W. W. Boone, F. B. Cannonito, and R. C. Lyndon: Word Problems: Decision Problem in Group Theory, North-Holland, 1973.
[4] R. C. Lyndon, P. E. Schupp: Combinatorial Group Theory, Springer, 2001.
[5] P. S. Novikov: On the algorithmic unsolvability of the word problem in group theory, Proceedings of the Steklov Institute of Mathematics (in Russian), 1955.