Контрольная работа на тему Полурешетки m степеней
Работа добавлена на сайт bukvasha.net: 2014-11-15Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
от 25%
договор
Содержание
Введение
Теоретическая часть
§1 Основные определения
§2 Простейшие свойства m – степеней
§3 Минимальные элементы верхней полурешетки m-степеней
2. Практическая часть
§1. Идеалы полурешетки m-степеней частично рекурсивных функций
Литература
Введение
Сейчас много внимания уделяется вопросам сводимости функций. Данная работа посвящена одной из разновидностей сводимости частично рекурсивной функции, а именно m-сводимости.Для дальнейшего рассмотрения этого вопроса будем пользоваться общепринятыми понятиями и теоретико-множественными обозначениями.
Символы логических операций: отрицания, конъюнкции, дизъюнкции, импликации, и эквивалентности будем обозначать:
Кванторы общности и существования обозначают
Совокупность всех целых неотрицательных чисел обозначим через N.
Под множеством будем понимать подмножество N.
Латинскими буквами A,B,C,… будем обозначать множества.
Объединение множества A и B обозначим через
Пусть
Определение: Функции
Под n-местной
Греческими строчными буквами будем обозначать частично рекурсивные функции (ЧРФ) :
Всякий раз, когда число аргументов явно не указывается, речь идет об одноместных функциях. Обозначим через
Запись
Множество
Определение: Частичную n-местную функцию
Всюду определенная функция будет обозначаться латинскими буквами: f,g,h,… . [5,6]
Теоретическая часть
§1 Основные определения
Определение 1: (интуитивное).Арифметическая функция называется частично рекурсивной, если существует алгоритм для нахождения ее значений.
Определение 2:
Под начальными функциями будем понимать следующие функции:
1. функция следования S
2. функции выбора
3.
4. нулевая функция
Определение 3: (оператор суперпозиции (подстановка)).
Говорят, что функция
Определение 4: (оператор примитивной рекурсии ).
Говорят, что функция
Это определение применимо и при n=0. Говорят, что функция
Определение 5: (
Определим
Будем говорить, что функция
В этом случае
Теперь определим
Определение 6:
Функция
Определение 7:
Если
Определение 8:
Множество
Определение 9:
Характеристической функцией множества
Определение 10:
Множество
Определение 11:
Функция
Функция
Введем отношение m-эквивалентности на множестве
Определение 12:
Введем понятие m-степени функции
Определение 13:
Введем понятие m-сводимости множеств.
Определение 14:
Множество
Аналогично вводится понятие m-степени множества
Определение 15:
Частичная характеристическая функция для множества
Определение 16:
ЧРФ – универсальная для множества
Определение 17:
Если на множестве
1.
2.
3.
то множество
4.
Определение 18:
Верхней (нижней) гранью подмножества
Если же
Определение 19.
Наименьшая (наибольшая) из верхних (нижних) граней множества
Определение 20.
Полурешеткой (точнее, верхней полурешеткой) назовем пару
1.
2.
3.
Если
Проверка того, что это частичный порядок, очевидна. Операция
Определение 21:
Множество
Ясно, что продуктивное множество
Определение 22:
Множество
Заметим, что креативные множества по теореме Поста не могут быть рекурсивными. Примером креативного множества будет
Действительно
откуда рекурсивная функция
Имеет место следующее утверждение: если
§2 Простейшие свойства m – степеней
Ведем отношение частного порядка на множестве m – степеней:Обозначим через L частично упорядоченное множество m – степеней.
Утверждение 2.1: множество L является верхней полурешеткой.
Доказательство:
Рассмотрим
Докажем, что эта функция является точной верхней гранью для произвольных ЧРФ α и β.
Рассмотрим γ’:
Определим функцию
Проверим следующие равенства:
Пусть x=2t, тогда
Пусть x=2t+1, тогда
Таким образом, равенство
Следовательно, функция
Утверждение 2.2:
Доказательство:
Следствие: существует изоморфное вложение полурешетки m-степеней рекурсивно перечисляемых множеств в полурешетку m-степеней частичных характеристических функций:
Утверждение 2.3:
Доказательство:
Если
Пусть
Таким образом,
Следствие: функции, принадлежащие одной и той же m-степени, имеют одинаковую область значений.
Утверждение 2.4: Пусть f, g – рекурсивные функции, тогда
Доказательство:
Строим
Полагаем, что
Аналогично строим функцию
Таким образом, так как
§3 Минимальные элементы верхней полурешетки m-степеней
Утверждение 3.1: Наименьшего элемента в L нет.
Доказательство:
Допустим противное, то есть пусть
Следовательно,
Возьмем всюду определенную функцию h. Ясно, что сШ≤mh.
С одной стороны,
Получили противоречие, то есть в L наименьшего элемента нет. Ч.т.д.
Утверждение 3.2: m-степень, содержащая универсальную функцию, является наибольшей в L.
Доказательство:
Пусть Ψ – универсальная функция, а α – произвольная ЧРФ. Так как α – ЧРФ, то найдется такое число х0, что α=φ0.
Покажем, что
Таким образом,
Введем обозначение:
Ясно, что
Утверждение 3.3: сШ и множество всех функций вида cn(x) и только они образуют множество минимальных в L элементов.
Доказательство.
Из утверждения 3.1. следует, что сШ – минимальный в L элемент.
Возьмем произвольную функцию cn(x).
Пусть
Ясно, что
Пусть теперь
2. Практическая часть.
§1. Идеалы полурешетки m-степеней частично рекурсивных функций
Определение:Идеалом полурешетки L назовем всякое подмножество I отличное от Ш, удовлетворяющее следующим условиям:
1.
2.
Идеал называется главным, если он содержит наибольший элемент.
Рассмотрим множество всех m-степеней частичных характеристических функций, то есть:
Н={
Предположение 4.1:
Множество Н является главным идеалом полурешетки L.
Доказательство:
1. Берем две степени
Определим множество А
Докажем, что
Будем пользоваться определением 15 для доказательства данного равенства.
Рассмотрим 4 случая.
1) если x=2t,
И если x=2t,
2) Если x=2t,
И если x=2t,
3) Если x=2t+1,
И если x=2t+1,
4) Если x=2t+1,
И если x=2t+1,
Следовательно, равенство
2. Пусть
Тогда Н – главный идеал полурешетки L. Ч.т.д.
Рассмотрим множество всех m-степеней рекурсивных функций, то есть:
М={
Предположение 4.2: Данное множество М является главным идеалом полурешетки L.
Доказательство:
1. Берем две степени рекурсивных функций, их точной верхней гранью будет
2. Если
М – главный идеал полурешетки L. Ч.т.д.
Литература
1. Дегтев А.Н. Сводимость частично-рекурсивных функций. – Сибирский математический журнал, 1975 т. 16, №5, с. 970-988.2. Ершов Ю.Л. Теория нумераций. – М.: Наука, 1977.
3. Кагленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М.: Мир, 1983.
4. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965.
5. Поляков Е.А., Розинас М.Г. Теория алгоритмов. – Иваново: ИвГУ, 1976.
6. Поляков Е.А., Маринина Н.В. Теория алгоритмов. – Шуя: ШГПУ, 2004.
7. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М.: Мир, 1972.