¿Puede un grupo ser una máquina de Turing universal?

Question

Esta pregunta está inspirada en esto entrada del blog de Jordan Ellenberg.

Definir un "grupo computable" como un grupo a lo sumo contable $G$ cuyos elementos pueden ser representados por cadenas binarias finitas, con las propiedades que

• Existe un algoritmo (con lo que quiero decir "máquina de Turing") que, cuando se le da una cadena binaria, puede determinar si esa cadena vive en el grupo $G$ en un tiempo finito (es decir $G$ es un conjunto computable);
• Existe un algoritmo que, cuando se le dan cadenas binarias $x,y$ en $G$ puede calcular $x^{-1}$ y $xy$ en tiempo finito (es decir, las leyes de grupo en $G$ son funciones computables).

En la entrada del blog mencionada anteriormente, el grupo $SL_3({\bf Z})$ que es ciertamente un ejemplo de grupo computable, pero, por supuesto, se pueden idear muchos otros ejemplos de grupos computables. Pero nótese que esta condición es más fuerte que la de ser recursivamente presentado, ya que estoy requiriendo que el problema de palabras sea decidible.

Obsérvese que si $G$ es un grupo computable, entonces existe un algoritmo obvio que, cuando se dan dos elementos cualesquiera $x,y$ de $G$ como entrada, que se detendrá en un tiempo finito si y sólo si $x,y$ no generan un grupo libre, simplemente evaluando todas las palabras no triviales de $x,y$ a su vez y comprobar si alguno de ellos es la identidad.

Mi primera pregunta es si hay algún grupo computable $G$ que es "Turing completo" en el sentido de que el problema de detención de cualquier máquina de Turing puede convertirse en una pregunta de la forma anterior. En otras palabras, existiría un algoritmo que, dada una máquina de Turing $T$ , devolvería (en tiempo finito) un par $x_T, y_T$ de elementos de $G$ con la propiedad de que $x_T, y_T$ generan un grupo libre en $G$ si y sólo si $T$ no se detiene en un tiempo finito. O más informalmente: ¿puede un grupo ser una máquina de Turing universal?

Sospecho que la respuesta a esta pregunta es "sí", haciendo algo así como tomar G como el grupo de operaciones reversiblemente computables sobre una cadena infinita de bits, aunque no he podido precisar los detalles. También se podría modificar la pregunta tomando G como un semigrupo computable en lugar de un grupo computable, aunque creo que esto no debería suponer una diferencia demasiado sustancial.

Mi segunda (y más vaga) pregunta es si se puede tomar $G$ para ser un grupo "no artificial", que puede definirse sin referencia a la computabilidad o a las máquinas de Turing. (Por ejemplo, un grupo que se construya de alguna manera utilizando ecuaciones diofantinas cumpliría los requisitos).

Answer 1

Actualización. Esta es una construcción más directa. (Ver el historial de ediciones para la versión anterior).

Existe un grupo computable universal como el que pides. Sea $F$ sea el grupo libre sobre infinitos generadores $\langle a_p\rangle_p$ , indexado por los programas de la máquina de Turing $p$ . Sea $G$ sea el cociente de este grupo por todos los $k^{th}$ poderes $a_p^k$ siempre que el programa $p$ se detiene (con una entrada trivial) exactamente en $k$ pasos.

Representemos el grupo $G$ por palabras reducidas en los generadores $a_p$ y sus inversos, pero en el caso de que tomáramos el cociente por $a_p^k$ , entonces en estas palabras usamos exponentes en $a_p$ en el intervalo $(-k/2,k/2]$ . (La razón de utilizar este formato de exponente es que si utilizáramos sólo las potencias positivas de los generadores de orden finito, no podríamos calcular las inversiones en $G$ ya que no podemos calcular si $a_p$ tiene un orden finito o no). En primer lugar, podemos reconocer computacionalmente si una palabra en los generadores se ajusta a esta descripción, simplemente comprobando si es reducida y si alguno de los exponentes es demasiado grande. El sentido de esta última cuestión es que podemos saber si el exponente $a_p^r$ es demasiado grande comprobando si el programa $p$ se detiene en $2r$ pasos o no. Del mismo modo, podemos calcular fácilmente la inversa de una palabra a partir de la palabra, y podemos multiplicar computacionalmente las palabras. De nuevo siempre que tengamos una palabra con algunos nuevos exponentes en los generadores, tenemos que comprobar si se reducen debido a nuestro cociente, y esto es posible ejecutando el cómputo correspondiente durante un número suficiente de número de pasos para determinarlo.

Así, tenemos una representación computable del grupo $G$ .

Por último, afirmo que es universal en el sentido que usted pide. Dado cualquier programa de la máquina de Turing $p$ , dejemos que $x_p=a_p$ y que $y_p=a_q$ para algún otro programa $q$ se sabe que no se detiene. Así, por diseño, el grupo generado por $x_p,y_p$ será el grupo libre en estos generadores si y sólo si $p$ no se detiene.

Una presentación esencialmente equivalente del grupo puede hacerse sin referencia a las máquinas de Turing o a los cálculos, sino sólo a las ecuaciones diofantinas, simplemente utilizando la representación diofantina de la máquina de Turing universal. Es decir, dado que todo conjunto c.e. es el conjunto solución de una ecuación diofantina, existe una ecuación diofantina fija $d(y,\vec x)=0$ , tal que el programa de la máquina de Turing $p$ se detiene en la entrada trivial si y sólo si $d(p,\vec x)=0$ tiene una solución en los enteros, viendo el programa como su código de Gödel. Así que podemos definir el grupo $G$ como arriba, con infinitos generadores $a_n$ pero tomando el cociente por $a_n^k$ , si $k$ es el tamaño de la solución entera más pequeña de $d(n,\vec x)=0$ . No estoy seguro de que esto haga que el grupo sea "natural" (y mi opinión es que esta palabra no tiene un significado matemático robusto y coherente), pero omite cualquier mención a las máquinas de Turing, utilizando en su lugar una ecuación diofantina fija.

Por último, permítanme observar que mi grupo no está generado finitamente, y puede ser interesante tener un ejemplo finitamente generado, o incluso un ejemplo finitamente presentado. Sospecho que se puede aplicar uno de los teoremas de incrustación para colocar este ejemplo en un grupo finitamente generado o incluso finitamente presentado.

Answer 2

Si he seguido correctamente este hilo, entonces todavía queda la duda de si se puede construir un ejemplo de presentación finita. Esto se deduce de los hechos estándar.

En concreto, dejemos que $G=G_0$ sea el grupo construido por Joel o Jason. Por el argumento estándar Higman--Neumann--Neumann, $G_0$ se incrusta en un grupo finitamente generado $G_1$ porque $G_0$ es contable. Es un hecho que $G_1$ es recursivamente presentable si $G_0$ era. Por el Teorema de Incrustación de Higman, $G_1$ puede incrustarse en un grupo finitamente presentable $G_2$ porque $G_1$ es recursivamente presentable.

La incrustación de $G_0$ en $G_1$ es computable, y la incrustación de $G_1$ en $G_2$ es obviamente computable (ya que ambos grupos son generados finitamente).

Por último, uno quisiera que todo esto se hiciera para que $G_2$ tiene un problema de palabras solucionable. Que la incrustación de Higman se puede hacer para preservar la solvencia del problema de la palabra se deduce de una resultado de Clapham .

(Estrictamente hablando, también hay que comprobar que $G_1$ puede tomarse como un problema de palabras resoluble, ya que creo que Clapham empieza con un grupo finitamente generado. Esto debe ser bien conocido, pero Bridson y yo escribimos los detalles en la sección 7 de este documento .)

---

ADEMÁS

Para explicar por qué $G_0\to G_1$ es computable, necesito describir la construcción. Daré una versión aquí, que creo que aclara la cuestión. Si no recuerdo mal, es muy similar al argumento original dado por Higman, Neuman y Neumann, aunque ellos lo hacen un poco mejor y obtienen una incrustación en un grupo de dos generadores. Me quedaré con tres generadores para simplificar.

Tomaré $G_0$ que viene dada por una presentación recursiva $\langle (a_m\mid m\in\mathbb{N})\mid (r_n\mid n\in\mathbb{N})\rangle$ .

En primer lugar, hay que tener en cuenta que al sustituir $G_0$ avec $G_0*\langle x\rangle$ y sustituyendo cada $a_m$ por $a_mx^{m+1}$ Puedo suponer que el $a_m$ son todos de orden infinito y distintos.

Dejemos que

$G_{\frac{1}{2}}=G_0*\langle s\rangle$

y considerar los subgrupos

$H_M=\langle b_m=s^ma_{m-1}s^{-m}\mid m\geq M\rangle$

para $M\geq 1$ . Un argumento fácil con formas normales en productos libres demuestra:

Lema: $H_M$ es libre en el conjunto generador dado.

Por lo tanto, la asignación $b_m\mapsto b_{m+1}$ define un isomorfismo $\phi:H_1\to H_2$ . Por lo tanto, podemos definir $G_1$ para ser la extensión HNN

$G_1=G_{\frac{1}{2}}*_\phi$

que tiene presentación $\langle G_{\frac{1}{2}},t\mid tht^{-1}=\phi(h)~\forall h\in H_1 \rangle$ (en relación con $G_{\frac{1}{2}}$ ). Ahora apelamos al Lemma de Britton para demostrar que $G_1$ contiene una copia de $G_0$ .

El lema de Britton: El mapa natural $G_{\frac{1}{2}}\to G_{\frac{1}{2}}*_\phi$ es inyectiva.

Pero $G_1$ está generada finitamente; de hecho, está generada por $a_0,s,t$ .

El mapa $G_0\to G_1$ viene dada recursivamente por las ecuaciones

$a_m=s^{-m}b_ms^m$ y $b_m=tb_{m-1}t^{-1}$ .

(Por supuesto, $a_0\mapsto a_0$ .) En particular, es ciertamente computable.

Para demostrar que el problema de palabras es resoluble en $G_1$ , tiene que argumentar que puede resolver los problemas de afiliación para $H_0$ y $H_1$ en $G_\frac{1}{2}$ .

Answer 3

Creo que la respuesta es sí, existe ese grupo universal. Dejemos que $G$ sea el grupo de la suma directa $\bigoplus_{n \in \mathbb{N}} G_n$ , donde $G_n$ es $\mathbb{Z}$ si el $n$ La máquina de Turing no se detiene, y $G_n$ es cíclico en caso contrario. Sólo hay que construir cada $G_n$ añadiendo $0$ , $1$ , $-1$ ... hasta que el $n$ La máquina de Turing se detiene. Entonces haz $G_n$ el grupo cíclico más pequeño que pueda ser. La clave es que se puede ejecutar todo en paralelo y no tiene que definir la adición (ya que estoy pensando en un grupo abeliano) cuando se define el elemento (por ejemplo, $5$ puede no estar creado todavía cuando $2$ y $3$ son). Sólo hay que llegar a hacerlo.

Es fácil ver que se pueden enumerar los elementos de este grupo, y enumerar la tabla de multiplicación. Esta enumeración se puede convertir en el código de cada elemento del grupo.

Actualización: En mi construcción anterior, sólo hay un generador asociado a cada máquina de Turning, a saber, el elemento del grupo con 1 en el $n$ coordenada, donde $n$ es el índice de la máquina de Turing. Para tener dos generadores (como se pidió), la modificación más fácil sería tener $G_n$ parece el grupo libre sobre dos elementos $a$ y $b$ . Si la máquina de Turing asociada se detiene, entonces haz $a$ y $b$ tienen un orden finito, dejando el resto libre. De nuevo, creo que esto es similar a la nueva construcción de Joel.

(Me especializo más en el análisis computable que en el álgebra, pero imagino que hay una serie de grupos estándar que representan el problema de halting).

No estoy seguro de que exista un grupo "natural" de este tipo.

Actualización: También debo añadir que, normalmente, cuando se tiene una propiedad como esa -es decir, se sabe cuándo se mantiene, pero no siempre se sabe cuándo no se mantiene-, entonces se puede hacer que codifique una máquina de Turing universal. Tales sentencias se llaman $\Sigma^0_1$ sentencias.*

Answer 4

Esta pregunta aparece constantemente cuando visito el sitio, y no estoy seguro de que la segunda pregunta haya sido respondida, parece que las respuestas existentes no dan grupos muy naturales ya que se mencionan las propiedades de detención de las máquinas de Turing cuando se construye el grupo, así que daré esta respuesta algo tardía.

Si consideramos que "natural" significa simplemente que el grupo surge de una acción natural sobre algunos objetos naturales, y que no fue definido sólo con el propósito de un problema de decidibilidad, entonces hay muchos ejemplos. En primer lugar, no me sorprendería que este problema fuera indecidible incluso en algo tan natural como los grupos de Artin de ángulo recto o los grupos lineales, por ejemplo, para $F_2 \times F_2$ recuerda a la PCP (aunque no estoy seguro de que sea lo mismo que se llama PCP en los grupos). Sería interesante que los expertos comentaran, no conozco un nombre oficial para este problema (sugiero uno abajo) por lo que es difícil buscarlo. ( editar : Acabo de notar ¿Es decidible si una colección de matrices enteras genera o no un grupo libre? en los comentarios. Así que supongo que esto está abierto).

Mientras tanto, presentaré una solución de autómatas celulares, basada principalmente en mi propia investigación, ya que es lo que mejor conozco.

Escoge $A$ sea un alfabeto de cualquier cardinalidad compuesta excepto $|A| \neq 4$ y elegir una descomposición del producto cartesiano $A = B \times C$ . En $A^{\mathbb{Z}}$ definimos el siguiente conjunto finito de homeomorfismos:

• Para todos $\pi \in \mathrm{Sym}(A)$ , dejemos que $f_{\pi} : A^{\mathbb{Z}} \to A^{\mathbb{Z}}$ aplicar $\pi$ celda, lo que significa $f_{\pi}(x)_i = \pi(x_i)$ . Sea $F \cong \mathrm{Sym}(A)$ sea el grupo de tales $f_{\pi}$ .

• $\sigma_1 : A^{\mathbb{Z}} \to A^{\mathbb{Z}}$ se define identificando $x \in A^{\mathbb{Z}}$ avec $(y, z) \in B^{\mathbb{Z}} \times C^{\mathbb{Z}}$ de manera obvia, y definiendo $\sigma_1(y, z) = (\sigma(y), z)$ donde $\sigma(y)_i = y_{i+1}$ es el desplazamiento a la izquierda.

Definición. Sea $G = \langle F, \sigma_1 \rangle$ sea el grupo que generan los mapas anteriores.

En otras palabras, $G$ es el grupo de homeomorfismos sobre secuencias infinitas de símbolos de $B \times C$ que se generan desplazando la primera pista, y permutando los símbolos individuales (por cualquier permutación del conjunto $B \times C$ ). El grupo $G$ es un subgrupo de los autómatas celulares reversibles, es decir, los autohomogeneizadores de turno de $\mathrm{Aut}(A^{\mathbb{Z}})$ y, por tanto, es un grupo computable. La cadena de bits puede tomarse como la regla local mínima del AC.

Creo que la terminología "es una máquina de Turing universal" no es muy descriptiva, creo que esta propiedad se puede enunciar en términos estándar, si tomamos el "problema del grupo libre" para un grupo como el problema de, dados dos elementos, decidir si generan un grupo libre no abeliano (equivalentemente, generan uno libremente).

Teorema. El grupo $G$ tiene $\Pi^0_1$ -de grupo libre completo bajo reducciones de muchos. Por lo tanto, es una máquina de Turing universal en el sentido de la pregunta.

Prueba. Se sabe lo siguiente:

• Dada una máquina de Turing, se puede construir un autómata celular reversible en $\mathrm{Aut}(D^{\mathbb{Z}})$ para algunos $D$ , de manera que esta última es periódica si y sólo si la máquina de Turing se detiene. Esto se demuestra en [1].

• Hay una incrustación efectiva $\phi : \mathrm{Aut}(D^{\mathbb{Z}}) * \mathrm{Aut}(D^{\mathbb{Z}}) \to \mathrm{Aut}(D^{\mathbb{Z}})$ . Esto se demuestra en [2].

• Dejemos que $f_1, ..., f_k \in \mathrm{Aut}(D^{\mathbb{Z}})$ para cualquier alfabeto finito $D$ . Entonces se puede construir (efectivamente) una incrustación $\psi : \langle f_1,...,f_k \rangle \to G$ . Esto se demuestra en el preprint [3].

Combinando estos, dada la máquina de Turing $T$ utilizando el primer punto anterior construye un autómata celular reversible $f_T$ que es periódica si $T$ se detiene. Entonces, utilizando el segundo punto anterior construye $\phi(f_T, \mathrm{id})$ y $\phi(\mathrm{id}, f_T)$ . Entonces el grupo $H = \langle \psi(\phi(f_T, \mathrm{id})), \psi(\phi(\mathrm{id}, f_T)) \rangle \leq G$ es libre si $T$ nunca se detiene, mientras que si $T$ se detiene, $H$ ni siquiera está libre de torsión. Fin de la prueba.

En general, si $G * G \to H$ por una construcción eficaz y $G$ tiene un problema de torsión indecidible, entonces el problema del grupo libre es indecidible para $H$ .

Sobre otros grupos:

• Para cualquier desplazamiento sofico incontable $X \subset A^{\mathbb{Z}}$ , el grupo de automorfismo tiene un problema de grupo libre indecidible. Esto se deduce fácilmente de lo anterior y de [2]. (Para sofics contables, este problema es decidible).

• Para el grupo completo topológico del turno completo $A^{\mathbb{Z}}$ He pensado bastante en este problema y no sé si es decidible. No debería ser difícil demostrar (usando los resultados de [4]) que al menos para el grupo completo topológico de $A^{\mathbb{Z}^d}$ avec $d \geq 3$ Este problema es indecidible. No estoy seguro de la dimensión $2$ .

• Para los grupos de autómatas (y el grupo mayor de todos los transductores reversibles [5]), este problema es indecidible. En concreto, existe un grupo de autómatas $G$ donde el problema de torsión es indecidible [6, 7], y $G * G \to H$ para algún otro grupo de autómatas $H$ [8], por lo que este problema será indecidible para $H$ .

• Para el grupo de máquinas de Turing reversibles en el sentido de [4], no sé si el producto libre del grupo consigo mismo se incrusta en él, pero creo que no debería ser difícil demostrar que esto es indecidible usando la indecidibilidad del problema de torsión. Sin embargo, no lo he probado.

Esta idea no funcionará en grupos en los que el problema de orden es decidible, lo que limita la naturalidad del ejemplo que se puede encontrar de esta manera.

Referencias

[1] Kari, Jarkko; Ollinger, Nicolas , Periodicidad e inmortalidad en la computación reversible , Ochmański, Edward (ed.) et al., Mathematical foundations of computer science 2008. 33rd international symposium, MFCS 2008, Toruń Poland, August 25-29, 2008. Actas. Berlín: Springer (ISBN 978-3-540-85237-7/pbk). Lecture Notes in Computer Science 5162, 419-430 (2008). ZBL1173.68521 .

[2] Salo, Ville , Una nota sobre subgrupos de grupos de automorfismo de turnos completos , Ergodic Theory Dyn. Syst. 38, nº 4, 1588-1600 (2018). ZBL1390.37021 .

[3] Salo, Ville Grupos universales de autómatas celulares, https://arxiv.org/abs/1808.08697

[4] Barbieri, Sebastián; Kari, Jarkko; Salo, Ville , El grupo de máquinas de Turing reversibles Cook, Matthew (ed.) et al., Cellular automata and discrete complex systems. 22nd IFIP WG 1.5 international workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016. Actas. Cham: Springer (ISBN 978-3-319-39299-8/pbk; 978-3-319-39300-1/ebook). Lecture Notes in Computer Science 9664, 49-62 (2016). ZBL1350.68101 .

[5] Grigorchuk, R. I.; Nekrashevich, V. V.; Sushchanskii, V. I. Automata, dynamical systems, and groups, Grigorchuk, R.I. (ed.), Dynamical systems, automata, and infinite groups. Traducido del ruso. Moscú: MAIK Nauka/Interperiodica Publishing. Proc. Steklov Inst. Math. 231, 128-203 (2000); traducción de Tr. Mat. Inst. Steklova 231, 134-214 (2000). ZBL1155.37311 .

[6] Gillibert, Pierre , Un grupo de autómatas con orden indecidible y problemas de Engel , ZBL06824269 .

[7] Bartholdi, Laurent ; Mitrofanov, Ivan , https://arxiv.org/abs/1710.10109

[8] Fedorova, Mariia; Oliynyk, Andriy , Finite automaton actions of free products of groups, Algebra Discrete Math. 23, No. 2, 230-236 (2017). ZBL1375.20028 .