D’una banda si hom disposa d’un alfabet finit OOO = {a1,...,an} i, per concatenació, construeix els mots M = ζ1ζr, on cada símbol ζi és una de les lletres aj ∈ OOO d’aquest alfabet i r ∈ ℕ; si, d’altra banda, hom disposa d’un cert diccionari que estableix l’equivalència de certes parelles de mots i, finalment, hom accepta el fet que, en substituir en un mot M = M1mM2 un cert sumbmot m per un altre mot m´ equivalent, obté un mot equivalent M´ = M1m'M2. Cal plantejar la pregunta següent: donats dos mots arbitraris M i N, hi ha algun algorisme que permeti de decidir si són equivalents d’acord amb el diccionari donat? La resposta negativa fou establerta independentment pels matemàtics P.S. Novikov (1955), J. Britton (1958), W. Boone (1958) i G. Higman (1961).
m
Matemàtiques