Содержание Введение Теоретическая часть §1 Основные определения §2 Простейшие свойства m – степеней §3 Минимальные элементы верхней полурешетки m-степеней 2. Практическая часть §1. Идеалы полурешетки m-степеней частично рекурсивных функций Литература
Введение

Сейчас много внимания уделяется вопросам сводимости функций. Данная работа посвящена одной из разновидностей сводимости частично рекурсивной функции, а именно m-сводимости.

Для дальнейшего рассмотрения этого вопроса будем пользоваться общепринятыми понятиями и теоретико-множественными обозначениями.

Символы логических операций: отрицания, конъюнкции, дизъюнкции, импликации, и эквивалентности будем обозначать: , соответственно.

Кванторы общности и существования обозначают  соответственно.

Совокупность всех целых неотрицательных чисел обозначим через N.

Под множеством будем понимать подмножество N.

Латинскими буквами A,B,C,… будем обозначать множества.

Объединение множества A и B обозначим через пересечения этих множеств -  а разность , дополнение - .

Пусть 1*2*…*n 1,2,…,n11, 22,…,nn-декартово произведение множеств 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:

Множество  - рекурсивно перечислимо (РП), в интуитивном смысле, если существует эффективная процедура, которая выписывает элементы этого множества. ............