Минимальные нумерации

Настоящий параграф посвящен краткому обзору (без доказательств) результатов, связанных с изучением вопроса о существовании тех или иных вычислимых минимальных нумераций у различных классов рекурсивно перечислимых множеств.

Нумерация н: N > некоторого множества называется однозначной, если нn ? нm для n ? m N.

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

1. Всякая однозначная нумерация н минимальна, т.е. [н] - минимальный элемент в L°(S).

2. Если семейство S имеет хотя бы одну вычислимую однозначную нумерацию, то для любого R семейство {R} вычислимо (даже однозначно вычислимо, т.е. допускает однозначную вычислимую нумерацию).

Замечание: Отмеченное в 2 свойство является нетривиальным.

Справедливо следующее утверждение о семействе П.

Предложение 1. Семейство П обладает счетным семейством попарно неэквивалентных однозначных нумераций.?

Наиболее общими результатами о существовании однозначных вычислимых нумераций являются следующие две теоремы.

Теорема 1. Пусть вычислимое семейство содержит сильно перечислимое семейство конечных множеств такое, что

а) любое множество из S есть объединение возрастающей последовательности множеств из ;

б) любое множество из содержится в некотором собственном подмножестве из .

Тогда существует однозначная вычислимая нумерация семейства .?

Введем следующие определения. Множество М предельно для семейства множеств , если для любого конечного подмножества M в существует М такое, что М. Семейство предельно для семейства , если любое множество из предельно для семейства .

Теорема 2. Пусть вычислимое семейство содержит вычислимое подсемейство такое, что

а) если два множества из имеют непустое пересечение, то одно из них содержится в другом;

б) частично упорядоченное множество < , > не имеет максимальных элементов;

в) семейство предельно для семейства .

Тогда существует однозначная вычислимая нумерация семейства .?

Минимальными нумерациями являются также и позитивные (однозначные нумерации, в частности, также позитивны). Сразу следует отметить, что довольно многие семейства не имеют однозначных нумераций, но имеют позитивные нумерации. Укажем простейший пример.

Пусть А - рекурсивно перечислимое нерекурсивное множество, полагаем

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

Ясно, что - вычислимая нумерация семейства . Можно заключить, что любая другая вычислимая нумерация семейства эквивалентна . Заметим теперь, что - неразрешимая нумерация. Последнее следует из эквивалентности .

Замечание. Естественная нумерация слов конечного алфавита определяет некоторую нумерацию свободной полугруппы с образующими из этого алфавита. Эта нумерация слов определяет (порождает) и нумерацию любой конечно определенной полугруппы, причем последняя, всегда будет позитивной.

Существует довольно много достаточных условий существования (хотя бы одной) позитивной нумерации. Приведем для примера следующие предложения.

Предложение 2. Пусть вычислимое семейство содержит вычислимое семейство конечных множеств такое, что S предельно для , тогда имеет позитивную нумерацию.?

Предложение 3. Если вычислимое семейство содержит наибольшее по включению множество, имеет позитивную нумерацию.

Отметим, что семейство П имеет счетное множество попарно не эквивалентных позитивных нумераций, не эквивалентных однозначным нумерациям.

У П, а также и у других семейств может существовать и много минимальных непозитивных нумераций.