Илья Мещерин: Мощности Множеств

В Кочерге продолжается цикл семинаров по теории алгоритмов — науке, которая является связующим звеном между программированием и абстрактной математикой. На ближайшей лекции мы дадим формальное определение алгоритма как машины Тьюринга, обсудим эту вычислительную модель и докажем, что некоторые функции алгоритмически невычислимы (то есть существуют алгоритмически неразрешимые проблемы). Данная лекция будет являться повтором лекции, которая состоялась в начале нашего курса, но не была записана. Для понимания требуется лишь знание основ логики и теории множеств. Так что если вы хотели присоединиться и войти в курс дел — сейчас самое время. Ведущий — Илья Мещерин, студент 6 курса кафедры дискретной математики МФТИ.