Полурешетки m-степеней
Пусть 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.
Доказательство:
Берем две
степени
для некоторых
р.п. множеств
А и В. точной
верхней гранью
будет степень,
содержащая
функцию
.
Определим
множество А
В:
{
}.
Докажем, что
.
Будем пользоваться определением 15 для доказательства данного равенства.
Рассмотрим 4 случая.
если x=2t,
![]()
И если x=2t,
![]()
Если x=2t,
![]()
И если x=2t,
![]()
Если x=2t+1,
![]()
И если x=2t+1,
![]()
Если x=2t+1,
![]()
И если x=2t+1,
![]()
Следовательно,
равенство
справедливо
во всех четырех
случаях, т.к.
обе его части
равносильны
в рассмотренных
случаях.
.
Пусть
.
По определению
m-сводимости
из
следует, что
существует
рекурсивная
функция f
такая, что:
,
откуда
.
Из утверждения
2.2 и того, что
всякое р.п.
множество
m-сводимо
к креативному
следует, что:
- наибольший
элемент в Н,
где k – креативно.
Тогда Н – главный идеал полурешетки L. Ч.т.д.
Рассмотрим множество всех m-степеней рекурсивных функций, то есть:
М={
}.
Предположение 4.2: Данное множество М является главным идеалом полурешетки L.
Доказательство:
Берем две
степени рекурсивных
функций, их
точной верхней
гранью будет
,
где
также рекурсивная
функция.
Если
,
откуда существует
рекурсивная
функция h,
такая, что
,
где
также рекурсивная
функция. Далее,
посредством
f(x) для
любой рекурсивной
функции f(x),
отсюда
- наибольший
элемент в М.
М – главный идеал полурешетки L. Ч.т.д.
Литература
Дегтев А.Н. Сводимость частично-рекурсивных функций. – Сибирский математический журнал, 1975 т. 16, №5, с. 970-988.
Ершов Ю.Л. Теория нумераций. – М.: Наука, 1977.
Кагленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М.: Мир, 1983.
Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965.
Поляков Е.А., Розинас М.Г. Теория алгоритмов. – Иваново: ИвГУ, 1976.
Поляков Е.А., Маринина Н.В. Теория алгоритмов. – Шуя: ШГПУ, 2004.
Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М.: Мир, 1972.