Capacity of a noisy function

This paper presents an extension of the memoryless channel coding theorem to noisy functions, i.e. unreliable computing devices without internal states. It is shown that the concepts of equivocation and capacity can be defined for noisy computations in the simple case of memoryless noisy functions. Capacity is the upper bound of input rates allowing reliable computation, i.e. decodability of noisy outputs into expected outputs. The proposed concepts are generalizations of these known for channels: the capacity of a noisy implementation of a bijective function has the same expression as the capacity of a communication channel. A lemma similar to Feinstein´s one is stated and demonstrated. A model of reliable computation of a function thanks to a noisy device is proposed. A coding theorem is stated and demonstrated.