Главные универсальные функции. Вывод теоремы Успенского-Райса из теоремы Клини. Машины Тьюринга. Неразрешимость проблемы равенства слов в полугруппе (выводимости в одностороннем и двустороннем ассоциативном исчислении). Определение примитивно рекурсивных функций.