Описание:Курс состоит из трех частей: "Конечные автоматы-распознаватели" (конечно-автоматные множества, првоинвариантное отношения эквивалентности, недетерминированные автоматы, регулярные множества), "Машины Тьюринга и вычислимые функции" (машины Тьюринга и функции, вычислимые на машинах Тьюринга; операции над машинами Тьюринга и моделирование машин Тьюринга; операции примитивной рекурсии и минимизации; классы примитивно-рекурсивных и частично рекурсивных функций; совпадение классов частично рекурсивных и вычислимых функций; универсальная машина Тьюринга; P-сводимость и NP-полнота; Теорема Кука), "Конечные автоматы преобразователи" (задание конечно-автоматных функций с помощью деревьев, диаграмм Мура, канонических уравнений и схем из автоматных элементов; замкнутость класса конечно-автоматных функций относительно операций суперпозиции и обратной связи; конечная порождаемость класса конечно-автоматных функций относительно операций суперпозиции и обратной связи; невозможность сведения операции обратной связи к операции суперпозиции).