Введение
Сейчас много внимания уделяется вопросам сводимости функций. Данная работа посвящена одной из разновидностей сводимости частично рекурсивной функции, а именно 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]