We study implementation of circuits of unreliable elements in the case of arbitrary limited-deterministic (l.-d.) functions. For circuits in bases consisting of logic gates and a delay element, the following statements are proved, which are valid even with the error probabilities of elements tending to zero: 1) for almost all l.-d. functions, there are input sequences on which it is impossible to implement a b.-d. function with an error probability less than 1/2 – δ under arbitrarily small δ > 0; 2) almost all l.-d. functions on almost all input sequences can be implemented only with a positive probability of error. We also consider implementation of l.-d. functions in the 'broad sense', i.e. with minimal restrictions. In addition, we obtain asymptotic behavior of the reliability functional of implementation of autonomous l.-d. functions.

circuit reliability, limited-deterministic function, logic gate, delay element

Mathematical problems and theory of numerical methods