Презентация на тему ВЫЧИСЛИМЫЕ ФУНКЦИИИ ИХ ПРЕДСТАВЛЕНИЯ В ТЕОРИИ АЛГОРИТМОВ

продукт «Вычислимые функции»
4

исследование рекурсивных функций,
разработка элективного курса «Вычислимые функции»,
создание

программной поддержки элективного курса «Вычислимые функции», которая является демонстрационной и практической составляющей этого курса.

называется вычислимой, если существует алгоритм, ее вычисляющий

(Верещагин Н.К.)
Алгоритм — это процесс последовательного построения величин, идущий в дискретном времени таким образом, что в начальный момент задается исходная конечная система величин, а в каждый следующий момент система величин получается по определенному закону (программе) из системы величин, имевшихся в предыдущий момент времени
(Мальцев А.И.)

Черч, Гедель)
Абстрактные машины (машины Тьюринга, Поста)
Комбинаторные модели (алгоритмы Маркова)

Направленность алгоритма
Массовость алгоритма

x’ = x +1
Функция выбора

где 1< m ≤ n

Операторы (операции над функциями):
Оператор суперпозиции
=(h, g1,…,gm)=h(g1(x1,…,xn),…,gm(x1,…,xn))=f(x1,…,xn)
Оператор примитивной рекурсии

быть получена из константы 0, функции следования и функции

выбора с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.

y≤ z, такому,
что P(x1,…,xn, y) истинно,
µyy≤z P(x1

,…, xn ,y)= если такое y существует;
z в противном случае.

Ограниченный оператор минимизации примитивно-рекурсивен!

быть построена из простейших функций

0, x’ = x +1, с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и µ-оператора.

Частично-рекурсивная функция называется общерекурсивной, если она всюду определена.

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

учетом
приоритетов
операций

окном
Доказательство примитивности элементарной функции