/>СодержаниеВведениеТеоретическая часть§1 Основные определения§2 Простейшие свойства m – степеней§3 Минимальные элементы верхней полурешетки m-степеней2. Практическая часть§1. Идеалы полурешетки 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 Основные определения
Определение 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]§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 элемент. Тогда />Ø),где сØ – нигде неопределенная функция.
Следовательно, />Ø и />(сØ).
Возьмем всюдуопределенную функцию h.Ясно, что сØ≤mh.
С одной стороны, />(сØ)– наименьший элемент, то есть сØ≤mh; с другой стороны сØ≤mh.
Получили противоречие, тоесть в L наименьшего элемента нет. Ч.т.д.
Утверждение 3.2: m-степень, содержащая универсальнуюфункцию, является наибольшей в L.
Доказательство:
Пусть Ψ –универсальная функция, а α – произвольная ЧРФ. Так как α – ЧРФ, тонайдется такое число х0, что α=φ0.
Покажем, что />. В качествесводящей возмем функцию f(x0,y).Тогда из определения Ψ вытекает, что />, где />, то есть />.
Таким образом, /> - наибольшая вL. Ч.т.д.
Введем обозначение: />.
Ясно, что />.
Утверждение 3.3: сØи множество всех функций вида cn(x) и только они образуют множествоминимальных в L элементов.
Доказательство.
Из утверждения 3.1.следует, что сØ – минимальный в L элемент.
Возьмем произвольнуюфункцию cn(x).
Пусть />.
Ясно, что />{/>}, кроме того α –всюду определенная функция, так как иначе />, следовательно, />.
Пусть теперь /> минимальный в L элемент, отличный от сØи от всех сn, тогда /> определена внекоторой точке х0; пусть />, имеем />, где />, то есть, />. Получили противоречие.Ч.т.д. [1,2]
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. Пусть />. Поопределению 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.