From the book The Nature of Computation by Moore and Mertens, exercise 8.9:Consider the problem ACYCLIC GRAPH of telling whether a directed graph is acyclic. Show that the problem is in NL, and then show that the problem is NL-complete.I am mainly interested in the first part. It's quite easy to show that it's in coNL (just guess a walk, vertex by vertex, from a vertex $v$ that returns to $v$), and then we can use the Immerman-Szelepcsnyi Theorem to prove that it's in NL.But I was not able to construct a Turing machine directly, i.e. a machine that shows that the problem is in NL without the help of Immerman-Szelepcsnyi or the construction from their proof. My question thus is:How can I  show directly that ACYCLIC GRAPH is in NL?
Acyclic Graph in NL
complexity theory;graph theory;space complexity
It's easy to see that the problem is coNL-complete.If you could find a direct proof that ACYCLIC GRAPH is in NL, then it would be a direct proof of NL=coNL. However, as far as I know, nobody knows about a proof of this fact that does not use the inductive counting technique. See https://cstheory.stackexchange.com/questions/2145/alternate-proofs-of-immerman-szelepcsenyi-theorem and Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$.(By the way, I find it bit easier to think about the problem CYCLIC GRAPH as in graph that has a cycle; it's easy to show that's it's NL-complete.)