Tu pregunta es muy interesante. No tengo completa
respuesta.
En primer lugar, permítanme señalar que en un finitely presentado el grupo, el
Cayley gráfico en sí no puede ser un decidable gráfico, ya que a
saber si es o no un nodo en el gráfico, que es una palabra en
la presentación, es trivial o no cantidades exactamente a la
la palabra problema para esa presentación. Y ya que no hay
finitely presentado los grupos que tienen un indecidible palabra
problema, hay finitely presentado los grupos que tienen un
indecidible grafo de Cayley.
Esto sugiere una interesante sub-caso de tu problema, el
cuando el grafo de Cayley es decidable. Y en este caso,
uno puede, al menos, encontrar un no-intersección de camino infinito que
es baja.
Me explico. Para cualquier presentación del grupo, uno se puede formar
el árbol T de todos finito no-caminos se cruzan. Este es
el árbol de intentos de construir una infinita no-intersección
ruta de acceso. Su pregunta es equivalente a la pregunta, cuando el grupo
es infinito, sea o no este árbol tiene una computable
infinito de la rama. Si el grafo de Cayley es decidable, entonces
este árbol será decidable. Por lo tanto, por la Baja Base
Teorema,
de ello se desprende que hay una rama b a través del árbol que
es baja, lo que significa que la detención problema relativo a b es
Turing equivalente a la ordinaria detener problema. En
en particular, esta rama b es estrictamente por debajo de la detención
problema en el Turing grados. Esto demuestra que cualquier
computably-presentado el grupo con un decidable grafo de Cayley
admite una baja no-intersección ruta. Una ruta de acceso es cerca de
siendo computables, pero tal vez no computables. (Incluso en
este caso muy especial cuando el grafo de Cayley es decidable,
No estoy seguro de si debe haber una computable
no-intersección ruta de acceso).
En el caso general, el argumento muestra que para cualquier presentación en grupo de un infinito de grupo, podemos encontrar una infinita no-intersección ruta s, que tiene un bajo grado en relación a los Turing grado del grafo de Cayley (baja en el sentido técnico). Sospecho que esto es lo mejor que uno puede decir.
Hay otro clásico teorema de la computabilidad que
parece pertinente a su pregunta, a saber, el hecho de que
hay computable infinito binario de las ramas de los árboles T,
subárboles de 2ω, no tener computable
infinitas ramas. Estos árboles constituyen, por tanto,
las violaciones de los computable analógica de Konig del lexema.
Este problema es muy similar a la tuya, ¿no? Estoy intrigado
por la posibilidad de utilizar que la clásica construcción de
construir un ejemplo de la clase de grupo que usted busca.
Hay una generalización natural de su pregunta, más allá de
el finitely presentado a los grupos, a la clase de
finitely generado pero computably presentan grupos. Que
es decir, considerar la posibilidad de una presentación a un grupo con un número finito de
generadores y una computable lista de relaciones. Puede ser
más fácil encontrar una instancia de la clase de grupo que usted busca
teniendo este más general, ya que uno puede imaginar un
prioridad argumento, donde se agrega poco a poco las relaciones de
la construcción se realice con el fin de satisfacer las diversas
los requisitos que diagonalize contra la computables caminos.
Aquí están algunos recursos para general decidability preguntas en
finito presentaciones de grupo: el undecidability de la palabra
problema,
el conjugacy
problema,
y el grupo de isomorfismo
problema.
