The geodesic length of elements can be defined as the length of a minimal path from 1 to w in the Cayley graph of G. This length is dependent on the particular generating set X.
The Word Problem is decidable in G if and only if the geodesic length function is computable.
Sufficiency is obvious, but why is the necessity needed? Further, "computable" I interpret as the calculation terminates in a finite number of steps, with the correct answer, is this correct, or is it more nuanced?
The braid group has a quadratic Dehn function, i.e., there exist constants $C_n$, $C'_n$ such that, if w is an n-strand braid word of length $l$ that represents the unit braid, then the number of braid relations needed to transform $w$ into the empty word is at most $C_n l^{2}$ and, on the other hand, there exists for each $l$ at least one length $l$ word $w$ such that the minimal number of such braid relations is at least $C'_n l^2$. [This paragraph is copied from Combinatorial Distance between Braid Words, P. Dehornoy, which mentions it is a well-known result]
Because the first result is if and only if, this, together with the braid group having a quadratic Dehn function, (presumably) means that word problem in the braid group is decidable. Does this mean that the Dehn function can be used to calculate the geodesic length in the braid group?
Best Answer
Yes, computable means that there is an algorithm to solve the problem that is guaranteed to succeed on all inputs.
If the word problem in $G$ is solvable, then you can compute the geodesic length of $g \in G$ as follows.
For $n := 0, 1,2,3 \ldots$, write down all words of length $n$ and check whether any of them are equal in $G$ to $g$. When you find such an element, stop: the geodesic length of $g$ is $n$.