Рекурсивные функцииПростейшие функцииОперация суперпозиции

Алгоритмический процесс можно рассматривать как процесс вычисления значений некоторой функции f
Такие функции называются вычислимыми

Интуитивное понятие вычислимой функции заменим на точное понятие частично рекурсивной функции

Рассмотрим некоторый набор простейших функций, вычислимость которых очевидна
Простейшие функции
Простейшими функциями называются следующие арифметические функции:
1) Нулевая функция
Оn(x1, x2, … , xn) = 0
O(x) = 0
2) Функция следования
λ(x) = x + 1, x ∈ N
3) Функция проецирования (выбора)
Im n(x1, x2, … , xn) = xm
Вспомните понятие арифметической функции

Замечание
Вычислимость функции проецирования обеспечивается нашей способностью найти в строке
(x1, x2, … , xn)
место с номером m и указать число на этом месте

Пусть заданы арифметические функции:
f1(x1, x2, … , xn), f2(x1, x2, … , xn), …, fm(x1, x2, … , xn),
ϕ(y1, y2, … , ym)
Операция подстановки (суперпозиции)
Говорят, что функция ψ(x1, x2, … , xn) получена из функций ϕ и f1, f2, …, fm операцией подстановки (суперпозиции), если:
Обозначение:

Пример 1
Операция подстановки (суперпозиции)

Пример 1
Операция подстановки (суперпозиции)

Правильное применение суперпозиции:
необходимо соблюдать требования к набору аргументов каждой функции
Операция подстановки (суперпозиции)

Пример 1
Операция подстановки (суперпозиции)
Преобразуем функции f1 и f2 так, чтобы они удовлетворяли требованиям к аргументам для применения суперпозиции
Корректно

Замечание
Такое применение функции проецирования предложил К.Гёдель (1934)
Все функции fi, i = 1,…m зависят от n переменных, а функция ϕ имеет m переменных (по количеству функций fi)
Результат подстановки, функция ψ зависит от n переменных

Добиться выполнение условия на количество аргументов у функций можно введением фиктивных переменных и применения функции проецирования
Im n

Пример 2
Записать корректно подстановку
Решение

Пример 3
Вычислить функцию-константу:
Решение

Литература
Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, 2006. - 149 с.
Теория алгоритмов / Электронный учебник
http://ric.uni-altai.ru/Fundamental/teor-alg/
Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. - СПб.: Лань, 2009. - 288 с.