A decision problem $P$ over a relational vocabulary $L$ is in NL if and only if there are a number $k$ and a two-way $k$-head automaton over $L$ that accepts, for every nonempty finite $L$-structure $A$ and every linear order on $A$, exactly when $A$ is a yes-instance of $P$. The same holds for FO(TC) definability, a configuration of the automaton being a node of a transitive-closure specification and conversely. This relates the logically defined class to a machine model with logarithmic storage: $k$ heads on a structure of size $n$ hold $k \log n$ bits.