Abstract:
We discussed in general terms what can be considered computation. We will assume that computation is the evolution of some system that can be used to solve problems. Following Church's thesis, we will study bit strings and some set (dictionary) of possible operations (gates) on them, taking them as physical systems describing classical computation. Classical Boolean circuits are compositions of basic operations, and if the dictionary is rich enough (universal), one can express any Boolean function as a Boolean circuit. However, in bad cases such an expression may require a large number of operations.
