Контрольная работа: Полурешетки m-степеней

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

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

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

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

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

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

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

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

Пусть ₁ *₂ *…*_{n 1} ,₂ ,…,_{n 1 1} , _{2 2} ,…,_nn -декартово произведение множеств ₁ ,₂ ,…,_n .

Определение: Функции называется арифметической, если ее аргументы пробегают натуральный ряд N, и сама функция принимает лишь натуральные значения.

Под n-местной частичной арифметической функцией будем понимать функцию, отображающую некоторое множество в N ,где -n-ая декартовая степень множества N.

Греческими строчными буквами будем обозначать частично рекурсивные функции (ЧРФ) : .

Всякий раз, когда число аргументов явно не указывается, речь идет об одноместных функциях. Обозначим через множество всех одноместных ЧРФ.

Запись означает, что функция для этой n-ки не определена, а запись означает, что функция для этой n-ки определена.

Множество называют областью значений функции , а множество область определения функции .

Определение: Частичную n-местную функцию назовем всюду определенной, если .

Всюду определенная функция будет обозначаться латинскими буквами: f,g,h,… . [5,6]

Теоретическая часть

§1 Основные определения

Определение 1: (интуитивное).

Арифметическая функция называется частично рекурсивной, если существует алгоритм для нахождения ее значений.

Определение 2:

Под начальными функциями будем понимать следующие функции:

1.функция следования S;

2.функции выбора

,

3.

4.нулевая функция .

Определение 3: (оператор суперпозиции (подстановка)).

Говорят, что функция получена суперпозицией из функций и , если для всех значений выполняется равенство:

--> ЧИТАТЬ ПОЛНОСТЬЮ <--