Арифметические функции с неопределенными значениями аргументов. Вычислимость и λ -определимость

МАТЕМАТИКА

Abstract

Рассматриваются арифметические функции с неопределенными значениями аргументов. Эти функции определены на частично-упорядоченном множестве M=N ꓴ {ꓕ}, где N – множество натуральных чисел, ꓕ – элемент, соответствующий неопределенному значению. Каждый элемент множества M сравним только с самим собой и с элементом ꓕ, который является наименьшим элементом множества M. Понятие монотонной функции определяется традиционным образом. Функция называется естественно расширенной, если при неопределенном значении какоголибо из аргументов ее значение равно ꓕ. Всякая естественно расширенная функция монотонна. Далее для арифметических функций с неопределенными значениями аргументов вводятся понятия вычислимости, сильной вычислимости, λ - определимости. Доказывается, что всякая λ -определимая арифметическая функция с неопределенными значениями аргументов монотонна и вычислима. Определяется класс частично рекурсивных функций с неопределенными значениями аргументов. Такие функции будут естественно расширенными. Доказывается λ -определимость частично рекурсивных функций с неопределенными значениями аргументов. Доказывается существование монотонных, не естественно расширенных, сильно вычислимых арифметических функций с неопределенными значениями аргументов, которые не λ -определимы. Доказывается также существование монотонных, не естественно расширенных, сильно вычислимых арифметических функций с неопределенными значениями аргументов, которые λ -определимы.