Контрольная работа: Полурешетки m-степеней

👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

Сейчас много внимания уделяется вопросам сводимости функций. Данная работа посвящена одной из разновидностей сводимости частично рекурсивной функции, а именно m-сводимости.
Для дальнейшего рассмотрения этого вопроса будем пользоваться общепринятыми понятиями и теоретико-множественными обозначениями.
Символы логических операций: отрицания, конъюнкции, дизъюнкции, импликации, и эквивалентности будем обозначать: , соответственно.
Кванторы общности и существования обозначают соответственно.
Совокупность всех целых неотрицательных чисел обозначим через N.
Под множеством будем понимать подмножество N.
Латинскими буквами A,B,C,… будем обозначать множества.
Объединение множества A и B обозначим через пересечения этих множеств - а разность , дополнение - .
Пусть 1
* 2
*…* n
1
, 2
,…, n
1

1
, 2

2
,…, n n
-декартово произведение множеств 1
, 2
,…, n
.
Определение: Функции называется арифметической, если ее аргументы пробегают натуральный ряд N, и сама функция принимает лишь натуральные значения.
Под n-местной частичной арифметической функцией будем понимать функцию, отображающую некоторое множество в N ,где -n-ая декартовая степень множества N.
Греческими строчными буквами будем обозначать частично рекурсивные функции (ЧРФ) : .
Всякий раз, когда число аргументов явно не указывается, речь идет об одноместных функциях. Обозначим через множество всех одноместных ЧРФ.
Запись означает, что функция для этой n-ки не определена, а запись означает, что функция для этой n-ки определена.
Множество называют областью значений функции , а множество область определения функции .
Определение: Частичную n-местную функцию назовем всюду определенной, если .
Всюду определенная функция будет обозначаться латинскими буквами: f,g,h,… . [5,6]
Арифметическая функция называется частично рекурсивной, если существует алгоритм для нахождения ее значений.
Под начальными функциями будем понимать следующие функции:
Определение 3: (оператор суперпозиции (подстановка)).
Говорят, что функция получена суперпозицией из функций и , если для всех значений выполняется равенство:
Определение 4: (оператор примитивной рекурсии ).
Говорят, что функция получена из двух функций и с помощью оператора примитивной рекурсии, если имеют место следующие равенства:
Это определение применимо и при n=0. Говорят, что функция получена из одноместной функции константы равной и функции , если при всех :
Определение 5: ( -оператор или оператор минимизации).
Определим -оператор сначала для одноместных функций.
Будем говорить, что функция получена из частичной функции с помощью оператора, если,
В этом случае -оператор называется оператором обращения и -наименьшее .
Теперь определим -оператор в общем виде:
Функция называется частично рекурсивной функцией (ЧРФ) ,если она может быть получена из начальных функций с помощью конечного числа применений трех операторов: суперпозиции, примитивной рекурсии, -оператора.
Если - ЧРФ и всюду определена, то она называется рекурсивной функцией.
Множество - рекурсивно перечислимо (РП), в интуитивном смысле, если существует эффективная процедура, которая выписывает элементы этого множества. Каждый элемент на некотором шаге будет выписан.
Характеристической функцией множества называется функция
Множество называется рекурсивным, если характеристическая функция является рекурсивной.
Функция m-сводима к функции ( ), в точности тогда, когда существует рекурсивная функция , такая, что
Функция называется сводящей функцией.
Введем отношение m-эквивалентности на множестве .
Введем понятие m-сводимости множеств.
Множество m-сводимо к множеству (обозначение ), если существует рекурсивная функция такая, что В этом случае говорят, что m-сводимо к посредством .
Аналогично вводится понятие m-степени множества .
Частичная характеристическая функция для множества -функция
ЧРФ – универсальная для множества , если ( -рекурсивная функция ) где - ЧРФ с геделевым номером .
Если на множестве определено бинарное отношение , удовлетворяющее условиям:
то множество называется частично упорядоченным, а отношение называется частичным порядком на . Отношение , удовлетворяющее только свойствам 1,3, называется предпорядком на . Если частичный порядок на удовлетворяет условию
4. то называется линейным порядком (или просто порядком), а -линейно упорядоченным множеством или цепью.
Верхней (нижней) гранью подмножества называется такой элемент что ( ) для любого . Элемент называется max (min) элементом , если ( ) для всех
Если же ( ) для любых ? ,то элемент называется наибольшим (наименьшим).
Наименьшая (наибольшая) из верхних (нижних) граней множества называется точной верхней (нижней) гранью этого множества.
Полурешеткой (точнее, верхней полурешеткой) назовем пару где - непустое множество, а -бинарная операция на , удовлетворяющая условиям: для любого
Если - полурешетка, то зададим на частичный порядок следующим соотношением: для
Проверка того, что это частичный порядок, очевидна. Операция является для этого порядка операцией взятия точной верхней грани.
Множество называется продуктивным, если существует рекурсивная функция , называемая продуктивной функцией для , такая, что
Ясно, что продуктивное множество не может быть р.п. Если бы то Ø, что невозможно.
Множество называется креативным, если оно р.п. и продуктивно.
Заметим, что креативные множества по теореме Поста не могут быть рекурсивными. Примером креативного множества будет
откуда рекурсивная функция является продуктивной функцией для .
Имеет место следующее утверждение: если В - р.п. множество, А -креативно, то - креативно.[1,5]
Ведем отношение частного порядка на множестве m – степеней:
Обозначим через L частично упорядоченное множество m – степеней.
Утверждение 2.1: множество L является верхней полурешеткой.
Докажем, что эта функция является точной верхней гранью для произвольных ЧРФ α и β.
Таким образом, равенство справедливо.
Следовательно, функция является точной верхней гранью для произвольных ЧРФ α и β, ч.т.д.
: Пусть , тогда посредством рекурсивной функции f, которая множество А m – сводит к В.
Следствие: существует изоморфное вложение полурешетки m-степеней рекурсивно перечисляемых множеств в полурешетку m-степеней частичных характеристических функций: .
Если Ø, то утверждение справедливо.
Пусть Ø. Возьмем , откуда для некоторого ; а так как для некоторой рекурсивной функции f, то и .
Следствие: функции, принадлежащие одной и той же m-степени, имеют одинаковую область значений.
Утверждение 2.4: Пусть f, g – рекурсивные функции, тогда .
Строим таким образом: допустим , начинаем последовательно вычислять g(0), g(1), …, пока не получим, что g(n)=i, а такое n обязательно появится, так как .
Полагаем, что , тогда очевидно, что .
Аналогично строим функцию , такую, что . Отсюда получим, что .
Таким образом, так как и , ч.т.д. [1]
Утверждение 3.1: Наименьшего элемента в L нет.
Допустим противное, то есть пусть - наименьший в L элемент. Тогда Ø
), где с Ø
– нигде неопределенная функция.
Возьмем всюду определенную функцию h. Ясно, что с Ø
≤ m
h.
С одной стороны, (с Ø
) – наименьший элемент, то есть с Ø
≤ m
h; с другой стороны с Ø
≤ m
h.
Получили противоречие, то есть в L наименьшего элемента нет. Ч.т.д.
Утверждение 3.2: m-степень, содержащая универсальную функцию, является наибольшей в L.
Пусть Ψ – универсальная функция, а α – произвольная ЧРФ. Так как α – ЧРФ, то найдется такое число х 0
, что α=φ 0
.
Покажем, что . В качестве сводящей возмем функцию f(x 0
,y). Тогда из определения Ψ вытекает, что , где , то есть .
Таким образом, - наибольшая в L. Ч.т.д.
Утверждение 3.3: с Ø
и множество всех функций вида c n
(x) и только они образуют множество минимальных в L элементов.
Из утверждения 3.1. следует, что с Ø
– минимальный в L элемент.
Возьмем произвольную функцию c n
(x).
Ясно, что { }, кроме того α – всюду определенная функция, так как иначе , следовательно, .
Пусть теперь минимальный в L элемент, отличный от с Ø
и от всех с n
, тогда определена в некоторой точке х 0
; пусть , имеем , где , то есть, . Получили противоречие. Ч.т.д. [1,2]
Идеалом полурешетки L назовем всякое подмножество I отличное от Ø, удовлетворяющее следующим условиям:
Идеал называется главным, если он содержит наибольший элемент.
Рассмотрим множество всех m-степеней частичных характеристических функций, то есть:
Множество Н является главным идеалом полурешетки L.
1. Берем две степени для некоторых р.п. множеств А и В. точной верхней гранью будет степень, содержащая функцию .
Будем пользоваться определением 15 для доказательства данного равенства.
Следовательно, равенство справедливо во всех четырех случаях, т.к. обе его части равносильны в рассмотренных случаях.
2. Пусть . По определению m-сводимости из следует, что существует рекурсивная функция f такая, что: , откуда . Из утверждения 2.2 и того, что всякое р.п. множество m-сводимо к креативному следует, что: - наибольший элемент в Н, где k – креативно.
Тогда Н – главный идеал полурешетки L. Ч.т.д.
Рассмотрим множество всех m-степеней рекурсивных функций, то есть:
Предположение 4.2: Данное множество М является главным идеалом полурешетки L.
1. Берем две степени рекурсивных функций, их точной верхней гранью будет , где также рекурсивная функция.
2. Если , откуда существует рекурсивная функция h, такая, что , где также рекурсивная функция. Далее, посредством f(x) для любой рекурсивной функции f(x), отсюда - наибольший элемент в М.
М – главный идеал полурешетки L. Ч.т.д.
1. Дегтев А.Н. Сводимость частично-рекурсивных функций. – Сибирский математический журнал, 1975 т. 16, №5, с. 970-988.
2. Ершов Ю.Л. Теория нумераций. – М.: Наука, 1977.
3. Кагленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М.: Мир, 1983.
4. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965.
5. Поляков Е.А., Розинас М.Г. Теория алгоритмов. – Иваново: ИвГУ, 1976.
6. Поляков Е.А., Маринина Н.В. Теория алгоритмов. – Шуя: ШГПУ, 2004.
7. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М.: Мир, 1972.

Название: Полурешетки m-степеней
Раздел: Рефераты по математике
Тип: контрольная работа
Добавлен 07:58:48 04 мая 2009 Похожие работы
Просмотров: 41
Комментариев: 15
Оценило: 3 человек
Средний балл: 5
Оценка: неизвестно   Скачать

Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Контрольная работа: Полурешетки m-степеней
Курсовая работа по теме Проектирование хозяйственной деятельности предприятия
Реферат по теме Технология внедрения CASE-средств
Контрольная Работа На Тему Гражданские Правоотношения
Реферат по теме Нидерланды
Реферат: Структура инвестиций
Курсовая работа по теме Организация и проведение соревнований по легкой атлетике (эстафеты, пробеги)
Травмы Позвоночника И Спинного Мозга Реферат
Реферат: Интраскопия Лазерные методы диагностики и термографии
Кубинская Революция И Ее Результаты Эссе
Доклад по теме Рогозин Виктор Олегович
Контрольная работа: Медико-статичтические показатели оценки здоровья
Сочинение Мое Любимое Растение
Становление Гринева Сочинение
Дипломная работа по теме Особенности кинорецензии в медиапространстве
Сочинение Значение Принятия Христианства На Руси
Напишите Сочинение Об Экологических Проблемах Вашего Края
Правовое Регулирование Охраны Атмосферного Воздуха Курсовая
Курсовая работа по теме Освітня діяльність і педагогічні погляди Григорія Сковороди
Функции Судебной Власти Реферат По Гму
Сочинение Иван Царевич И Квакушка
Доклад: Ламия
Реферат: Анатомо-фізіологічні особливості дихальної та травної систем в дітей
Курсовая работа: Афганистан – "Неизвестные страницы необъявленной войны"