примитивно рекурсивные и разрешимые множества

[Профессор Снэйп]

Xaositect в сообщении #281402 писал(а):

Чаще всего называют рекурсивно-перечислимыми.

Кстати, это уже устаревшая терминология.

Сейчас предпочитают говорить "вычислимое множество", "вычислимая функция", "вычислимо перечислимое множество". Термин "примитивно рекурсивный", естественно, остаётся.

По поводу первой задачи. Проекция примитивно рекурсивного множества не то что должна быть примитивно рекурсивной, а может оказаться даже не вычислимой (но, естественно, будет вычислимо перечислимой). Самый простой пример такой. Пусть $M = \{ \langle t,n \rangle :$ машина Тьюринга с номером $n$ заканчивает вычисления на пустом входе не более чем за $t$ шагов работы$\}$. Тогда множество $M$ примитивно рекурсивно, а его проекция на вторую координату даёт множество проблемы остановки, которое, естественно, не вычислимо.

(Оффтоп)

Эта проекция является креативным множеством, то есть наиболее сложным среди вычислимо перечислимых множеств относительно всех известных типов сводимости.