Строго говоря, «цифровая» модель работает не во времени, а в относительном порядке срабатывания частей (проводов и лог. элементов); если считать это «задержкой», то задержка учитывается все равно. Ограничение, видимо, можно понимать как таковое на величину задержки.
Там вот что оказывается:
Definition: An arbiter is called delay-bounded iff each of its initialized histories is finite. An arbiter is called stable iff in each of its initialized histories the value of one external output remains unchanged. An arbiter is called glitch-free iff it is both delay-bounded and stable; otherwise it is called glitch-prone...
The feedback restriction is actually not needed to prove the nonexistence of stable arbiters... The proof that delay-bounded arbiters do not exist is another matter. In fact, as we now show, if the feedback restriction is removed from our definition of a circuit, then a delay-bounded arbiter exists.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
(no subject)
2011-05-04 10:25 (UTC)Там вот что оказывается:
Definition: An arbiter is called delay-bounded iff each of its initialized histories is finite. An arbiter is called stable iff in each of its initialized histories the value of one external output remains unchanged. An arbiter is called glitch-free iff it is both delay-bounded and stable; otherwise it is called glitch-prone...
The feedback restriction is actually not needed to prove the nonexistence of stable arbiters... The proof that delay-bounded arbiters do not exist is another matter. In fact, as we now show, if the feedback restriction is removed from our definition of a circuit, then a delay-bounded arbiter exists.