Илья Мещерин: Проблема равенства слов (часть 1)

В Кочерге продолжается цикл семинаров по теории алгоритмов — науке, которая является свзующим звеном между программированием и абстрактной математикой. Это область с огромным числом нерешенных вопросов, в числе которых одна из проблем тысячелетия — проблема «P=NP?».

За прошедшие три встречи мы обсудили формальное определение алгоритма как машины Тьюринга; доказали из соображений теории множеств, что не все функции вычислимы; сформулировали классическую неразрешимую задачу — проблему остановки — и доказали ее неразрешимость.

Более подробный список рассказанного, а также задачи по темам лекций и ссылки на литературу есть на странице http://mesyarik.ru/18/kocherga_algorithms.html

В этот раз продолжим говорить о неразрешимых проблемах. А именно, рассмотрим интересную (и на первый взгляд не связанную с проблемой остановки) проблему "равенства слов в полугруппах". Следствием из её неразрешимости оказывается теорема Чёрча о том, что для формул с кванторами невозможно алгоритмически проверить их общезначимость (т.е. тождественную истинность). Всё это постепенно подводит нас к знаменитой теореме Гёделя о неполноте.

Ведущий — Илья Мещерин, студент 6 курса кафедры дискретной математики МФТИ, студент Школы анализа данных Яндекса.

kocherga.timepad.ru/event/629505
kocherga_math?w=wall-103194586_76

Видео Илья Мещерин: Проблема равенства слов (часть 1) канала Кочерга