Сейчас много внимания уделяется вопросам сводимости функций. Данная работа посвящена одной из разновидностей сводимости частично рекурсивной функции, а именно m-сводимости.
Для дальнейшего рассмотрения этого вопроса будем пользоваться общепринятыми понятиями и теоретико-множественными обозначениями.
Символы логических операций: отрицания, конъюнкции, дизъюнкции, импликации, и эквивалентности будем обозначать: 
,
соответственно.
Кванторы общности и существования обозначают 
соответственно.
Совокупность всех целых неотрицательных чисел обозначим через N.
Возможно вы искали - Реферат: Понятие случайного процесса в математике
Под множеством будем понимать подмножество N.
Латинскими буквами A,B,C,… будем обозначать множества.
Объединение множества A и B обозначим через 
пересечения этих множеств - 
а разность 
, дополнение - 
.
Пусть 
1 *2 *…*n 
1 ,
2 ,…,n
1 
1 , 2 2 ,…,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: (оператор суперпозиции (подстановка)).
Говорят, что функция 
получена суперпозицией из функций 
и 
, если для всех значений 
выполняется равенство:
