El problema de la trivialidad (entrada: una presentación de grupo finito de un grupo $G$ salida: sí/no en función de si $G$ es un grupo trivial) no es resoluble mediante un algoritmo. De hecho basta con aplicar el Teorema de Adian-Rabin a la propiedad "ser trivial".
Ahora deducimos el caso general de su pregunta de la siguiente manera:
Supongamos por contradicción que se tiene un algoritmo $A$ cuya entrada es una presentación finita de un grupo $G$ y la salida es sí/no en función de si $G$ es isomorfo al grupo finitamente presentado dado $G_0$ .
Entonces $A$ resuelve el problema de la trivialidad. A saber, la entrada $G$ y aplicar $A$ a la concatenación de presentaciones de $G$ y $G_0$ que es una presentación del producto libre $G\ast G_0$ . Así que la respuesta es sí/no en función de si $G\ast G_0$ es isomorfo a $G_0$ . Y por el teorema de Grushko (véase el párrafo siguiente), esto último se cumple si y sólo si $G$ es un grupo trivial. Así que tenemos una contradicción.
Teorema de Grushko dice que el rango generador (número mínimo de generadores) de un producto libre $B\ast C$ es igual a la suma de los rangos generadores de $B$ y $C$ . (Esto es falso para los productos directos: si $B$ y $C$ son cíclicos de orden $2$ y $3$ entonces el rango generador de $B$ , $C$ , $B\times C$ son todos iguales a $1$ .) En particular, para cada grupo finitamente generado $B$ y cada grupo $C$ el producto libre $B\ast C$ es isomorfo a $B$ sólo si $C$ es un grupo trivial.
