Множество всех программ, останавливающихся хотя бы на одном входе является:

Множество всех самоприменимых программ:

Множество всех истинных арифметических формул без параметров:

Множество всех истинных арифметических формул без параметров:

Для перечисляемых образцов и вычислимой универсальной функции, множество номеров всех функций, продолжающих хоть один образец:

Арифметическое множество m-сводимо к множеству всех истинных арифметических формул без параметров:

Бесконечное множество, не содержащее бесконечных разрешимых подмножеств является:

Множество является примитивно рекурсивной, если его характеристическая функция:

Перечислимое множество, для которого прямой пересчет его дополнения неограничен сверху вычислимой функцией является:

Если программа на каждом входе зацикливается, то для неё:

Множество всех показателей n, для которых существует целое решение уравнения xⁿ+yⁿ=zⁿ всегда: