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

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