Аннотация:
На Лекции мы обсудили в общих словах, что можно считать вычислением. Мы будем считать, что вычисление – это эволюция некоторой системы, при помощи которой можно решать задачи. Принимая тезис Чёрча, в качестве физических систем, описывающих классические вычисления, мы будем изучать битовые строки и некоторый набор (словарь) возможных операций (вентилей) над ними. Классическими булевыми схемами называют некоторую композицию базовых операций, и если словарь достаточно богат (универсален), то при помощи булевых схем можно выразить произвольную булеву функцию. Однако, в плохих случаях такое выражение может потребовать большое число операций.
