Записки научных семинаров Тульской школы теории чисел. Вып. 2. 2023 г.

О вычислимости частично рекурсивных функций 5 1. Введение «Необходимо задействовать в системе вузовского педагогического образования мощный познавательный и развивающий потенциал, заложенный в фундаментальных свойствах рекур- сивности широкого класса объектов и процессов. Это должно способствовать формированию у будущих учителей информатики алгоритмической культуры, широты кругозора, практиче- ских знаний и умений, необходимых для последующей качественной подготовки школьников, свободно ориентирующихся в современном, насыщенном рекурсивными алгоритмами мире, способных обеспечить информационную независимость страны». Так в 2001 году отмечал в своем диссертационном исследовании заведующий кафедрой информатики и методики обуче- ния профессор Альберт Рубенович Есаян [4]. Именно достижению обозначенных целей служит изучение будущими учителями матема- тики, физики и информатики дисциплины «Математическая логика и теория алгоритмов». В части изучения теории алгоритмов точки опоры расставляются для уточнения понятия ал- горитма, исследования алгоритмов реализации машины Тьюринга и нормального алгоритма Маркова и их приложений для формирования профессиональных компетенций будущих учи- телей для знаний теоретических основ раздела и их применения для решения прикладных задач. 2. Рекурсивные функции Алгоритм, ассоциированный с машиной Тьюринга (1936 г.), является практически иде- альным абстрактным компьютером с потенциально бесконечной памятью, реализуемой в ви- де такой ленты и с применением языка высокого уровня преобразования символов ячеек. В результате уже тогда при помощи такого прообраза настоящих и, как оказалось, будущих реальных ЭВМ, были сформулированы такие важные понятия математической логики как «алгоритмическая разрешимость и неразрешимость задач», «вычислимая функция». Описать все алгоритмически вычислимые функции, согласно тезису Чёрча (1937 г.), поз- воляют частично рекурсивные функции, которые являются при этом моделью алгоритма, реализующего идеи аксиоматического подхода Д. Гильберта [1]. Эти идеи воплощаются и в конструкциях структурного программирования. Рассмотрим рекурсивные функции Чёрча, созвучно аксиоматическому методу Гильбер- та. Для этого выбираются три очевидно вычислимые исходные функции (аналоги аксиом): 1) нуль функция, 2) функция следования и 3) функция индивидуализации (проектор), то есть выделения переменной [4]. Имеются три аналога правил вывода: I . оператор суперпозиции (подстановки функций вместо переменных). II . оператор примитивной рекурсии (определения функции для нуля и каждого последу- ющего значения аргумента). III . — оператор (минимизации), который определяет значение функции при помощи наименьшего значения аргумента, удовлетворяющего её условию. В данной интерпретации функция является примитивно рекурсивной, если существует её вывод, в котором составляющие этот вывод функции являются либо исходными, либо полу- чаются из предыдущих при помощи правил I и II . Функция является частично рекурсивной, если существует её вывод, в котором составляющие этот вывод функции являются либо ис- ходными, либо получаются из предыдущих при помощи правил I , II , III . Таким образом, всякая примитивно рекурсивная функция является частично рекурсивной. Например, для функции сложения s(x,y) имеем: s(x,0) = х+0 = х