lo.logic - How bad can the recursive properties of finitely presented groups be?

Your question is very interesting. I don't have a complete
answer.

First, let me note that in a finitely presented group, the
Cayley graph itself may not be a decidable graph, since to
know whether or not a node in the graph, which is a word in
the presentation, is trivial or not amounts exactly to the
word problem for that presentation. And since there are
finitely presented groups having an undecidable word
problem, there are finitely presented groups having an
undecidable Cayley graph.

This suggests an interesting sub-case of your problem, the
case when the Cayley graph is decidable. And in this case,
one can at least find a non-intersecting infinite path that
is low.

Let me explain. For any group presentation, one may form
the tree T of all finite non-intersecting paths. This is
the tree of attempts to build an infinite non-intersecting
path. Your question is equivalent to asking, when the group
is infinite, whether or not this tree has a computable
infinite branch. If the Cayley graph is decidable, then
this tree will be decidable. Thus, by the Low Basis
Theorem,
it follows that there is a branch b through the tree which
is low, meaning that the halting problem relative to b is
Turing equivalent to the ordinary halting problem. In
particular, this branch b is strictly below the halting
problem in the Turing degrees. This shows that any
computably-presented group with a decidable Cayley graph
admits a low non-intersecting path. Such a path is close to
being computable, but perhaps not quite computable. (Even in
this very special case when the Cayley graph is decidable,
I'm not sure whether there must be a computable
non-intersecting path.)

In the general case, the argument shows that for any group presentation of an infinite group, we can find an infinite non-intersecting path s, which has low degree relative to the Turing degree of the Cayley graph (low in the technical sense). I suspect that this is the best that one can say.

There is another classical theorem in computability that
seems relevant to your question, namely, the fact that
there are computable infinite binary branching trees T,
subtrees of 2^ω, having no computable
infinite branches. These trees therefore constitute
violations of the computable analogue of Konig's lemma.
This problem is very like yours, isn't it? I am intrigued
by the possibility of using that classical construction to
build an example of the kind of group you seek.

There is a natural generalization of your question beyond
the finitely presented groups, to the class of
finitely-generated but computably presented groups. That
is, consider a group presentation with finitely many
generators and a computable list of relations. It may be
easier to find a instance of the kind of group you seek
having this more general form, since one can imagine a
priority argument, where one gradually adds relations as
the construction proceeds in order to meet various
requirements that diagonalize against the computable paths.

---

Here are some resources to general decidability questions in
finite group presentations: the undecidability of the word
problem,
the conjugacy
problem,
and the group isomorphism
problem.