Теория нумераций

реферат

Главные нумерации

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

Нумерацию назовем главной, если любая нумерация сводится к .

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

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

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

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

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

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

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

Семейство назовем -подмножеством , если существует частично рекурсивная функция g такая что выполнены условия:

1. если то ;

2. если , то и

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

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

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

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

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

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

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

Следствие

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

Делись добром ;)