Илья Мещерин: Проблема равенства слов (часть 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, duration hours minute second in high quality that is uploaded to the channel Кочерга 23 December 2017. Share the link to the video on social media so that your subscribers and friends will also watch this video. This video clip has been viewed 895 times and liked it 19 visitors.
