Abstract:
In the introductory lecture, after discussing organizational issues, we asked ourselves about what computation is in general. One possible approach is to treat a computation as a certain evolution of a physical system. In classical digital computers, it is customary to encode computations within Boolean strings, while the evolution processes of Boolean strings are described using Boolean circuits – directed acyclic graphs composed of operations from a dictionary. We discussed upper and lower bounds on the number of elementary operations from a universal dictionary required to implement arbitrary Boolean functions.
