Алексей Львович Семенов Качественная теория алгоритмов А.Л. Семенов планирует прочесть 1 лекцию.

«Качественная» теория алгоритмов (не касающаяся понятия сложности вычислений) может быть построена на интуитивном представлении о том, что такое алгоритм. Такого представления, при некотором его уточнении, оказывается достаточно для того, чтобы доказать первые базовые теоремы теории алгоритмов. В лекции будет приведено указанное уточнение, определено понятие вычислимости и понятие породимости («выводимости в формальной системе»), доказано несколько теорем, другие теоремы - предложены в качестве задач. Будут приведены и примеры т. н. «уточнения понятия алгоритма». Для понимания лекции желательно умение читать по-русски, знание латинского алфавита и представление о натуральном ряде.