states $q_3$ and $q_4$.

\[thm:Undecidable1\] The initial-value universality problem for one-counter nets is undecidable.

We show that a given two-counter machine $\M$ halts if and only if the corresponding one-counter net $\A$, as constructed in \[sec:NondetInitial\], is initial-value universal.

$\Rightarrow:$ *If $\M$ halts*, its (legal) run has some length $n-1$. We claim that $\A$ is universal with the initial value $n$.

Consider some word $w$ over the alphabet of $\A$. We shall describe an accepting run $\rho$ of $\A$ on $w$. Until the first occurrence of $\#$, the run $\rho$ is deterministically in $q_0$, which is accepting. We show that for every segment between two consecutive $\#$’s, as well as the segment after the last $\#$, the run $\rho$ may either reach $heaven$ or reach $q_0$ with counter value at least $n$ (and remains there until the next $\#$ or the end of the word), from which it follows that $\rho$ is accepting.

If the segment is shorter than $n$, $q_0$ can choose to go to $q_1$ over $\#$, and from there it will reach heaven. If the segment is longer than $n$, it cannot describe the legal run of $\M$. Then, it must cheat within up to $n$ steps. 