  *by a standard (one-tape) Turing machine. It is well-known that the word
problem for hyperbolic groups, whence in particular for free groups, can be
solved in linear time. However, these algorithms run on machines more
complicated than a standard Turing machine. By contrast, in this note we show
that a standard Turing machine cannot solve the word problem for the free group
on two generators in less than quadratic time.
