Пусть

– семейство рекурсивно перечислимых подмножеств N. Нумерацию

этого семейства назовем
вычислимой, если множество

рекурсивно перечислимо (т.е.

).
Распространим введенное определение на нумерации семейств

.
Нумерация

семейства

, называется вычислимой, если множество

рекурсивно перечислимо (

).
Предложение 1:
Нумерация

,

,
вычислима тогда и только тогда, когда нумерация
свертки семейства 
,
определенная так
, является вычислимой. Нумерация 
,
является вычислимой тогда и только тогда, когда нумерация
n‑развертки семейства
определенная так
является вычислимой.Обозначим через

, n

, семейство всех n ‑местных частично рекурсивных функций, через

– отображение, сопоставляющее функции ее график.
Пусть

– семейство n‑местных частично рекурсивных функций. Нумерацию

семейства

назовем вычислимой, если нумерация

семейства графиков функций из

, определенная так

является вычислимой.
Предложение 2
Нумерация

семейства n‑местных частично-рекурсивных функций вычислимая тогда и только тогда когда частичная ( n +1) – местная функция

определенная соотношением

является частично-рекурсивной.
Функция
, связанная с нумерацией 
некоторого семейства

частично- рекурсивных функций является универсальной функцией для

, т.е. для любого

функция

принадлежит

и наоборот, для всякой функции

существует

такое что

.
Всякая универсальная функция F для семейства

определяет некоторую нумерацию

семейства

так:

. Эта нумерация вычислима тогда и только тогда, когда F частично рекурсивна.
Семейство

называется вычислимым если существует по крайней мере одна вычислимая нумерация семейства

.
Пусть

– две нумерации одного и того же множества S. Говорят что нумерация

сводится к нумерации

, если существует

такая что

. Если

сводится к

, то символически изображаем это так

.
Отношение

, определенное на множестве H( S ) всех нумераций множества S является транзитивным. Следовательно, отношение

на H( S ) является предпорядком.
Если

и

для

, то эти нумерации эквивалентны и обозначаются

. Класс нумераций эквивалентных нумерации

обозначим через [

]. Множество классов эквивалентных нумераций обозначим через L ( S ).
На множестве H( S ) можно задать операцию прямой суммы нумераций

. Пусть нумерации

, определим нумерацию

следующим образом:

Основное свойство операции следующее:
Предложение 3
Пусть

тогда

сводится к

тогда и только тогда когда

сводится к

и

сводится к

.
Обозначим через

семейство всех вычислимых нумераций

и через

семейство классов эквивалентных вычислимых нумераций

.
Главные нумерации
Рассмотрим понятие главной нумерации для семейства рекурсивно перечислимых множеств. Это понятие позволяет ответить (в случае семейства рекурсивно перечислимых множеств) на вопрос: «какую нумерацию данного множества следует считать наиболее естественной?»
Нумерацию

назовем главной, если любая нумерация

сводится к

.