Lower Bound for the Redundancy of Self-correcting Arrangements of Unreliable Functional Elements

Arrangements of unreliable functional elements are considered. It is assumed that all the elements misfunction independently of one another with probability $\varepsilon$. The redundancy of a self-correction arrangement that realizes some function is understood to mean the ratio of the number of elements (complexity) of a self-correcting arrangement of unreliable elements to the complexity of the arrangement of reliable elements that realizes the same function. It is shown that, for some functions, the redundancy of the self-correcting arrangements that realize them increases no more slowly than the logarithm of the complexity of the reliable-element arrangement.