лекция 3 | Вычислимость и логика | Дмитрий Ицыксон | CSC | Лекториум

Вычислимость и логика, лекция 3, Курс: Вычислимость и логика, Лектор: Дмитрий Ицыксон, Организаторы: -Computer Science Center Смотрите это видео на Лекториуме: Теорема о неподвижной точки (окончание). Машины Тьюринга. Главные универсальные функции. Вывод теоремы Успенского-Райса из теоремы Клини. Машины Тьюринга. Неразрешимость проблемы равенства слов в полугруппе (выводимости в одностороннем и двустороннем ассоциативном исчислении). Определение примитивно рекурсивных фу