Полурешетки m-степеней (85933)

Посмотреть архив целиком

Содержани



Введение

Теоретическая часть

§1 Основные определения

§2 Простейшие свойства m – степеней

§3 Минимальные элементы верхней полурешетки m-степеней

2. Практическая часть

§1. Идеалы полурешетки m-степеней частично рекурсивных функций

Литература


Введение


Сейчас много внимания уделяется вопросам сводимости функций. Данная работа посвящена одной из разновидностей сводимости частично рекурсивной функции, а именно m-сводимости.

Для дальнейшего рассмотрения этого вопроса будем пользоваться общепринятыми понятиями и теоретико-множественными обозначениями.

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

Кванторы общности и существования обозначают соответственно.

Совокупность всех целых неотрицательных чисел обозначим через N.

Под множеством будем понимать подмножество N.

Латинскими буквами A,B,C,… будем обозначать множества.

Объединение множества A и B обозначим через пересечения этих множеств - а разность , дополнение - .

Пусть 1*2*…*n 1,2,…,n11, 22,…,nn-декартово произведение множеств 1,2,…,n.

Определение: Функции называется арифметической, если ее аргументы пробегают натуральный ряд N, и сама функция принимает лишь натуральные значения.

Под n-местной частичной арифметической функцией будем понимать функцию, отображающую некоторое множество в N ,где -n-ая декартовая степень множества N.

Греческими строчными буквами будем обозначать частично рекурсивные функции (ЧРФ) : .

Всякий раз, когда число аргументов явно не указывается, речь идет об одноместных функциях. Обозначим через множество всех одноместных ЧРФ.

Запись означает, что функция для этой n-ки не определена, а запись означает, что функция для этой n-ки определена.

Множество называют областью значений функции , а множество область определения функции .

Определение: Частичную n-местную функцию назовем всюду определенной, если .

Всюду определенная функция будет обозначаться латинскими буквами: f,g,h,… . [5,6]


Теоретическая часть


§1 Основные определения


Определение 1: (интуитивное).

Арифметическая функция называется частично рекурсивной, если существует алгоритм для нахождения ее значений.

Определение 2:

Под начальными функциями будем понимать следующие функции:

  1. функция следования S ;

  2. функции выбора


,

  1. нулевая функция .

Определение 3: (оператор суперпозиции (подстановка)).

Говорят, что функция получена суперпозицией из функций и , если для всех значений выполняется равенство:



Определение 4: (оператор примитивной рекурсии ).

Говорят, что функция получена из двух функций и с помощью оператора примитивной рекурсии, если имеют место следующие равенства:


.


Это определение применимо и при n=0. Говорят, что функция получена из одноместной функции константы равной и функции , если при всех :



Определение 5: (-оператор или оператор минимизации).

Определим -оператор сначала для одноместных функций.

Будем говорить, что функция получена из частичной функции с помощью оператора, если,


.


В этом случае -оператор называется оператором обращения и -наименьшее .

Теперь определим -оператор в общем виде:



Определение 6:

Функция называется частично рекурсивной функцией (ЧРФ) ,если она может быть получена из начальных функций с помощью конечного числа применений трех операторов: суперпозиции, примитивной рекурсии, -оператора.

Определение 7:

Если - ЧРФ и всюду определена, то она называется рекурсивной функцией.

Определение 8:

Множество - рекурсивно перечислимо (РП), в интуитивном смысле, если существует эффективная процедура, которая выписывает элементы этого множества. Каждый элемент на некотором шаге будет выписан.

Определение 9:

Характеристической функцией множества называется функция



Определение 10:

Множество называется рекурсивным, если характеристическая функция является рекурсивной.

Определение 11:

Функция m-сводима к функции (), в точности тогда, когда существует рекурсивная функция , такая, что



Функция называется сводящей функцией.

Введем отношение m-эквивалентности на множестве .

Определение 12:



Введем понятие m-степени функции .

Определение 13:


Введем понятие m-сводимости множеств.

Определение 14:

Множество m-сводимо к множеству (обозначение ), если существует рекурсивная функция такая, что В этом случае говорят, что m-сводимо к посредством .

Аналогично вводится понятие m-степени множества .

Определение 15:

Частичная характеристическая функция для множества -функция



Определение 16:

ЧРФ – универсальная для множества , если (-рекурсивная функция ) где - ЧРФ с геделевым номером .

Определение 17:

Если на множестве определено бинарное отношение , удовлетворяющее условиям:


1. (рефлексивность);

2. (антисимметричность);

3. (транзитивность),


то множество называется частично упорядоченным, а отношение называется частичным порядком на . Отношение , удовлетворяющее только свойствам 1,3, называется предпорядком на . Если частичный порядок на удовлетворяет условию

4. то называется линейным порядком (или просто порядком), а -линейно упорядоченным множеством или цепью.

Определение 18:

Верхней (нижней) гранью подмножества называется такой элемент что () для любого . Элемент называется max (min) элементом , если () для всех

Если же () для любых ? ,то элемент называется наибольшим (наименьшим).

Определение 19.

Наименьшая (наибольшая) из верхних (нижних) граней множества называется точной верхней (нижней) гранью этого множества.

Определение 20.

Полурешеткой (точнее, верхней полурешеткой) назовем пару где - непустое множество, а -бинарная операция на , удовлетворяющая условиям: для любого


1.

2.

3.


Если - полурешетка, то зададим на частичный порядок следующим соотношением: для



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

Определение 21:

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



Ясно, что продуктивное множество не может быть р.п. Если бы то Ø, что невозможно.

Определение 22:

Множество называется креативным, если оно р.п. и продуктивно.

Заметим, что креативные множества по теореме Поста не могут быть рекурсивными. Примером креативного множества будет



Действительно



откуда рекурсивная функция является продуктивной функцией для .

Имеет место следующее утверждение: если В - р.п. множество, А -креативно, то - креативно. [1,5]


§2 Простейшие свойства m – степеней


Ведем отношение частного порядка на множестве m – степеней:



Обозначим через L частично упорядоченное множество m – степеней.

Утверждение 2.1: множество L является верхней полурешеткой.

Доказательство:

Рассмотрим , где


.


Докажем, что эта функция является точной верхней гранью для произвольных ЧРФ α и β.

Рассмотрим γ:


для рекурсивных функций g, f.


Определим функцию .

Проверим следующие равенства: .

Пусть x=2t, тогда и .

Пусть x=2t+1, тогда и .

Таким образом, равенство справедливо.

Следовательно, функция является точной верхней гранью для произвольных ЧРФ α и β, ч.т.д.

Утверждение 2.2: .

Доказательство:

: Пусть , тогда посредством рекурсивной функции f, которая множество А m – сводит к В.

: Аналогично , ч.т.д.

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

Утверждение 2.3: .

Доказательство:

Если Ø, то утверждение справедливо.

Пусть Ø. Возьмем , откуда для некоторого ; а так как для некоторой рекурсивной функции f, то и .

Таким образом, , ч.т.д.

Следствие: функции, принадлежащие одной и той же m-степени, имеют одинаковую область значений.

Утверждение 2.4: Пусть f, g – рекурсивные функции, тогда .

Доказательство:

: Следует из следствия к 2.3.

: Пусть : покажем, что , то есть .

Строим таким образом: допустим , начинаем последовательно вычислять g(0), g(1), …, пока не получим, что g(n)=i, а такое n обязательно появится, так как .

Полагаем, что , тогда очевидно, что .

Аналогично строим функцию , такую, что . Отсюда получим, что .

Таким образом, так как и , ч.т.д. [1]


§3 Минимальные элементы верхней полурешетки m-степеней


Утверждение 3.1: Наименьшего элемента в L нет.

Доказательство:

Допустим противное, то есть пусть - наименьший в L элемент. Тогда Ø), где сØ – нигде неопределенная функция.


Случайные файлы

Файл
20711-1.rtf
123613.rtf
71846.rtf
185791.doc
179790.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.