Содержание
Введение
Теоретическая часть
Основные определения
Простейшие свойства m – степеней
Минимальные элементы верхней полурешетки m-степеней
Практическая часть
Идеалы полурешетки 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]
Теоретическая часть
Основные определения
Определение 1: (интуитивное).
Арифметическая функция называется частично рекурсивной, если существует алгоритм для нахождения ее значений.
Определение 2:
Под начальными функциями будем понимать следующие функции:
1. функция следования S 
;
2. функции выбора
,
3.
4. нулевая функция 
.
Определение 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]
Простейшие свойства 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]