its value when entering $q_3$ (and by the inductive assumption at least $n$). Then, $q_4$ goes to $q_0$ with weight $0$, guaranteeing that $\A$’s counter value is at least $n$. Notice that the counter might go below $n$ between getting to $q_4$ and returning to $q_0$. Yet, since the violation must occur within up to $n$ steps, and the value of the counter when entering $q_4$ is at least $n$, we are guaranteed to be able to properly continue with the run, as the counter need not go below $0$.

4-5.

:   Analogously, if it makes a positive or negative cheat over $y$, the choice of $q_0$ will be $q_5$ or $q_6$, respectively.

$\Leftarrow:$ *If $\M$ does not halt*, for every positive integer $n$, we build the word $w_n$ and show that it is not accepted by $\A$ with an initial counter value $n$.

The word $w_n$ consists of $n+1$ segments between $\#$’s, where each segment is the prefix of length $n+1$ of the (legal) run of $\M$. Consider the possible runs of $\A$ on $w_n$. It cannot go from $q_0$ to $q_1$, because it will stop after $n$ steps. It also cannot go to $q_2$, because there is no 