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

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

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

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

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

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

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

Иммунное множество - это множество:

Среди перечислимых множеств множество, к которому m-сводится любое перечислимое множество X:

m-полное множество относительно m-сводимости - это множество:

Если преобразователь программ вычислимо зависит от некоторого параметра, то: