command, we assume that the machine never reaches $\texttt{dec(c)}$ with $c=0$. That is, the counters never have negative values.

Undecidability {#sec:nondet}
==============

We show that both initial-value universality and bounded universality are undecidable by reduction from the undecidable halting problem of two-counter machines (2CM) [@Min67]. The idea underlying both reductions is that the initial counter value, or the bound on the allowed counter, prescribes a bound on the number of steps until the OCN must make a decision weather the input word, which encodes a prefix of the run of the 2CM, either halts or cheats. After this decision the OCN is reset and continues to read the remaining word within an adjusted bound. If the decision was correct then the bound remains the same and otherwise, it is strictly reduced. The existence of a halting run of the 2CM now implies that its length corresponds to a sufficient initial bound for this simulating OCN to be universal. Conversely, if the run of the machine does not halt then for every bound $n$, there exists a non-cheating, and non-terminating prefix of length $n$. Repeating this prefix $n$ times witnesses non-universality for the simulating OCN with initial counter $n$.

Initial-Value Universality 