# $\mathsf{NL}$ versus $\mathsf{NL}$

There is an equivalent definition for the class $\mathsf{NL}$ with verifier. Those verifiers are deterministic Turing machines that can read the witness tape only once in one way from left to right.

Given a function $f:\mathbb{N}\to\mathbb{N}$ we say that $\mathsf{NL}[f(n)]$ is the class obtained by the above definition but the verifier can read the witness $f(n)$ times for an input of size $n$ (i.e. when the verifier finished reading the witness the goes straight to the beginning of it).

We can see of course that $\mathsf{NL}=\mathsf{NL}$.

The question is whether $\mathsf{NL}=\mathsf{NL}$.

Clarification: Prove or Disprove that $\mathsf{NL}=\mathsf{NL}$.

It is clear that $\mathsf{NL}\subseteq \mathsf{NL}$. For the second part I tried to construct a verifier that can read the witness only once for $L\in \mathsf{NL}$. I said that the verifier expects a witness of the form $w\sharp w$ and runs the $\mathsf{NL}$ verifier for $L$ with $w$ and then when it finishes and wants to read it again with second copy of $w$. But the major problem with my approach is that maybe someone tricked me and put a non equal sub-witnesses and I won't be able to find out about this with $\log(n)$ space thus it does not work.

You can show that $\mathsf{NL} \subseteq \mathsf{NL}$ as follows. We are given an $\mathsf{NL}$ machine $M$, and we want to simulate it with an $\mathsf{NL}$ machine $M'$. The first that $M$ does is to guess the state $\sigma$ of $M'$ after it finishes reading the witness tape for the first time. It then simulates two copies of $M$, one starting at $M$'s initial state, and the other starting at $\sigma$. After going through the witness tape, it verifies that the first copy has reached $\sigma$, and that the second copy has reached an accepting state.
In this way you can show that $\mathsf{NL}[O(1)] = \mathsf{NL}$.