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

Сентябрь 12, 2022

Главная
Математика
Простейшие функции. Операция суперпозиции

Содержание

2. Алгоритмический процесс можно рассматривать как процесс вычисления значений некоторой функции f Такие функции называются вычислимыми
3. Интуитивное понятие вычислимой функции заменим на точное понятие частично рекурсивной функции
4. Рассмотрим некоторый набор простейших функций, вычислимость которых очевидна Простейшие функции Простейшими функциями называются следующие арифметические функции:
5. Замечание Вычислимость функции проецирования обеспечивается нашей способностью найти в строке (x1, x2, … , xn) место
6. Пусть заданы арифметические функции: f1(x1, x2, … , xn), f2(x1, x2, … , xn), …, fm(x1,
7. Пример 1 Операция подстановки (суперпозиции)
8. Пример 1 Операция подстановки (суперпозиции)
9. Правильное применение суперпозиции: необходимо соблюдать требования к набору аргументов каждой функции Операция подстановки (суперпозиции)
10. Пример 1 Операция подстановки (суперпозиции) Преобразуем функции f1 и f2 так, чтобы они удовлетворяли требованиям к
11. Замечание Такое применение функции проецирования предложил К.Гёдель (1934) Все функции fi, i = 1,…m зависят от
12. Добиться выполнение условия на количество аргументов у функций можно введением фиктивных переменных и применения функции проецирования
14. Скачать презентацию

Слайд 2

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

функции называются вычислимыми

Слайд 3

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

Слайд 4

Рассмотрим некоторый набор простейших функций, вычислимость которых очевидна
Простейшие функции
Простейшими функциями называются

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

Слайд 5

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

x2, … , xn)
место с номером m и указать число на этом месте

Слайд 6

Пусть заданы арифметические функции:
f1(x1, x2, … , xn), f2(x1, x2, …

, xn), …, fm(x1, x2, … , xn),
ϕ(y1, y2, … , ym)

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

Говорят, что функция ψ(x1, x2, … , xn) получена из функций ϕ и f1, f2, …, fm операцией подстановки (суперпозиции), если:

Обозначение:

Слайд 7

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

Слайд 8

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

Слайд 9

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

(суперпозиции)

Слайд 10

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

удовлетворяли требованиям к аргументам для применения суперпозиции

Корректно

Слайд 11

Замечание
Такое применение функции проецирования предложил К.Гёдель (1934)
Все функции fi, i =

1,…m зависят от n переменных, а функция ϕ имеет m переменных (по количеству функций fi)
Результат подстановки, функция ψ зависит от n переменных

Слайд 12

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

переменных и применения функции проецирования
Im n