Илья Мещерин: Проблема равенства слов (часть 1)
В Кочерге продолжается цикл семинаров по теории алгоритмов — науке, которая является свзующим звеном между программированием и абстрактной математикой. Это область с огромным числом нерешенных вопросов, в числе которых одна из проблем тысячелетия — проблема «P=NP?».
За прошедшие три встречи мы обсудили формальное определение алгоритма как машины Тьюринга; доказали из соображений теории множеств, что не все функции вычислимы; сформулировали классическую неразрешимую задачу — проблему остановки — и доказали ее неразрешимость.
Более подробный список рассказанного, а также задачи по темам лекций и ссылки на литературу есть на странице http://mesyarik.ru/18/kocherga_algori...
В этот раз продолжим говорить о неразрешимых проблемах. А именно, рассмотрим интересную (и на первый взгляд не связанную с проблемой остановки) проблему "равенства слов в полугруппах". Следствием из её неразрешимости оказывается теорема Чёрча о том, что для формул с кванторами невозможно алгоритмически проверить их общезначимость (т.е. тождественную истинность). Всё это постепенно подводит нас к знаменитой теореме Гёделя о неполноте.
Ведущий — Илья Мещерин, студент 6 курса кафедры дискретной математики МФТИ, студент Школы анализа данных Яндекса.
kocherga.timepad.ru/event/629505
kocherga_math?w=wall-103194586_76
Watch video Илья Мещерин: Проблема равенства слов (часть 1) online without registration, duration hours minute second in high quality. This video was added by user Кочерга 23 December 2017, don't forget to share it with your friends and acquaintances, it has been viewed on our site 895 once and liked it 19 people.