Теория нумераций (стр. 3 из 22)

Нумерацию

назовем минимальной, если следует что .

У семейства

может существовать не более одной с точностью до эквивалентности главной нумерации. Минимальных нумераций может существовать очень много.

Предложение 1

Семейства

обладают главными вычислимыми нумерациями.

Семейство

назовем главным подмножеством, если оно обладает главной вычислимой нумерацией.

Предложение 2

Главное подмножество

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

Семейство

назовем -подмножеством

, если существует частично рекурсивная функция g такая что выполнены условия:

1. если

то ;

2. если

, то и

Предложение 3

Всякое непустое

-подмножеством является главным.

Существуют естественные классы рекурсивно перечислимых множеств, которые не имеют главной вычислимой нумерации. Таковыми, например, являются любые семейства общерекурсивных функций.

Определим понятие предельной точки для семейства

.

Одноместная (всюду определенная) функция h называется предельной точкой для семейства S, если для любого n

N в S найдется функция g отличная от h такая что .

Предложение 4

Если вычислимое семейство

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

Следствие

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

Отделимые нумерации

Во многих вопросах, связанных с употреблением нумераций, важно знать, какие отношения между элементами нумерованного множества можно эффективно распознать по их номерам. Одним из самых первых вопросов является следующий: можно ли по номерам двух элементов эффективно узнать, являются ли они Равными или нет? Те нумерации, для которых этот вопрос решается положительно, называются разрешимыми.

Пусть

– нумерация множества S. Рассмотрим бинарное отношение на множестве N определенное так . Отношение является отношением эквивалентности и называется нумерационной эквивалентностью. Нумерация называется разрешимой, если отношение рекурсивно. Нумерацию называется позитивной (негативной) если ( ) рекурсивно перечислимо.

Отношение эквивалентности

( ) на множестве S называется разрешимым (позитивным, негативным), если S рекурсивно (рекурсивно перечислимо, представляет собой дополнение до рекурсивно перечислимого множества).

Таким образом, нумерация

разрешима (позитивна, негативна) тогда и только тогда когда таковой является ее нумерационная эквивалентность.

Предложение 1

Нумерация

бесконечного множества S является разрешимой тогда и только тогда когда она эквивалентна некоторой однозначной нумерации.

Предложение 2

Если

– позитивное (негативное) отношение эквивалентности, то - нумерационная эквивалентность подходящей вычислимой нумерации

Предложение 3

Если

- семейство попарно не пересекающихся непустых рекурсивно перечислимых множеств, а

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

позитивна

Предложение 4

Если

– семейство общерекурсивных функций, – вычислимая нумерация, то

- негативная нумерация.

Отметим некоторые свойства позитивных и негативных нумераций относительно сводимости.

Предложение 5

Если S – бесконечное множество,

– негативная нумерация S, то существует однозначная нумерация

множества Sтакая что

Предложение 6

Пусть S – бесконечное множество,

- позитивная нумерация множества S. Если существует однозначная нумерация множества S такая что , то – разрешимая нумерация.

Предложение 7

Пусть

– позитивная нумерация S и , тогда

Следствие

Позитивные нумерации множества определяют минимальные элементы в L(S)

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

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

Нумерация ν: N →

некоторого множества называется однозначной, если νn ≠ νm для n ≠ m N.

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

объясняется такими обстоятельствами:

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

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

семейство \ {R} вычислимо (даже однозначно вычислимо, т.е. допускает однозначную вычислимую нумерацию).

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

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

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

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

Теорема 1. Пусть вычислимое семейство

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