В Кочерге продолжается цикл семинаров по теории алгоритмов — науке, которая является свзующим звеном между программированием и абстрактной математикой. Это область с огромным числом нерешенных вопросов, в числе которых одна из проблем тысячелетия — проблема «P=NP?». За прошедшие встречи мы уже успели обсудить основы теории множеств и логики предикатов, машины Тьюринга и проблему остановки, а также доказали (впрочем, не до конца) неразрешимость проблемы равенства слов в полугруппах. Более подробный список рассказанного, а также задачи по темам лекций и ссылки на литературу есть на странице
На этой встрече мы закончим тему, начатую в прошлый раз, и докажем теорему Чёрча о том, что для формул с кванторами невозможно алгоритмически проверить их общезначимость (то есть в некотором смысле тождественную истинность). После чего приступим, если успеем, к точной формулировке и доказательству знаменитой теоремы Гёделя о неполноте. Ведущий — Илья Мещерин, студент 6 курса кафедры дискретной математики МФТИ, студент Школы анализа данных Яндекса. kocherga.timepad.ru/event/633440 vk.com/kocherga_math?w=wall-103194586_77
