Полурешетки m-степеней
Содержание
Введение
Теоретическая часть
§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:
Под начальными функциями будем понимать следующие функции:
функция
следования
S
;
функции выбора
,
нулевая
функция
.
Определение 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,
тогда
и