О генерической амплификации рекурсивно перечислимых множеств

Генерическая амплификация – это метод, который позволяет из алгоритмически неразрешимых проблем получать проблемы, неразрешимые для почти всех входов. Доказывается, что любое простое пренебрежимое множество является неразрешимым для почти всех входов, но не может быть получено с помощью амплификации из какого-либо неразрешимого множества. С другой стороны, показывается, что любое рекурсивно перечислимое множество с ненулевой асимптотической плотностью может быть получено с помощью амплификации из множества натуральных чисел.