Неполнота эффективно вычислимых функций. Катасонов В.Г.

Тематика: Автоматическая проверка доказательств Аннотация: Продолжая предыдущий семинар, мы закончим определение эффективно вычислимых функций. Оказывается, при помощи довольно простого приёма можно свести некоторые довольно важные задачи изучаемой нами теории к задачам из теории чисел. Это позволяет нам попробовать использовать изучаемую теорию для решения её же задач. И действительно, есть много интересных задач, которые таким образом решаются. Однако, мы рассмотрим одну довольно простую с виду задачу, которая доказуемо неразрешима.