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