Первая часть лекции соответствовала этой статье: https://habr.com/ru/company/JetBrains-education/blog/217215/.

Во второй части лекции мы рассмотрели понятия разрешимых языков, и обсудили эквивалентные определения перечислимых языков: полуразрешимые языки и языки для которых есть системы доказательств. Доказали теорему Поста. Построили пример неразрешимого перечислимого языка.

Текущая версия конспекта.