- •Лекция 2. О понятии алгоритма. Декларативный подход о формализации понятия алгоритма.
- •1. Натуральные числа можно задавать конструктивным и конечным способом, например в десятичной системе счисления.
- •Примитивно-рекурсивные функции
- •0. Базисные примитивно-рекурсивные функции:
- •Правила построения примитивно-рекурсивных функций
- •Правило суперпозиции
- •Правило примитивной рекурсии
- •Функция g, таким образом, определена частично Частично-рекурсивные функции как формализация понятия вычислимых функций
- •Тезис Черча. Все вычислимые функции общерекурсивны.
Лекция 2. О понятии алгоритма. Декларативный подход о формализации понятия алгоритма.
Термин «алгоритм» впервые был использован средневековыми учеными, переводившими на латынь сочинения Аль Хорезми. Алгоритмами они называли правила арифметических действий на многоразрядными числами.
В XVII веке В.Лейбниц выдвинул идею формализации математики – т.е. построения универсального метода решения математических задач в виде системы правил манипулирования символами, с помощью которых эти задачи формулируются. В.Лейбниц ввел в употребление современную символику дифференциального и интегрального исчисления, в большой степени решившую задачу вычислений производных и интегралов при помощи формальных правил манипулирования символами.
Формальное понятие алгоритма было сформулировано как одно из понятий математической логики в 30-х годах XX века. В работах Э. Поста, А. Тьюринга, С. Клини, А. Черча и др. логиков. Несколько позже А.А. Марков ввел еще один формализм описания алгоритмов – т.н. нормальные алгорифмы Маркова.
Формальные аспекты понятия «алгоритм» изучаются в теории алгоритмов
Определение алгоритма как частично-рекурсивной функции
(С. Клини, А.Черч)
Понятие вычислимости. Вычислимые функции
Альтернативный (императивному) т.н. декларативный (описательный) подход к описанию алгоритмов состоит в описании алгоритма как функции преобразования Вход Выход.
Алгоритм: Вход Выход
или, в более привычных «школьных» обозначениях
y = A(x),
где A – алгоритмическая функция
x Х – входные данные (аргументы) из области определения X
y Y – выходные данные (значения) из области значений Y.
Изучение понятия алгоритма, следовательно, можно определить как изучение свойств функции A.
Точная постановка задачи формального определения алгоритма заключается в формализации понятия вычислимой функции.
Под вычислимыми функциями понимают натуральные функции натуральных аргументов, значения которых можно вычислить, исходя из значений аргументов, выполнив конечное число элементарных, точно определенных вычислительных действий.
В качестве областей определения аргументов и области значения функции выступают натуральные числа. Почему именно они?
1. Натуральные числа можно задавать конструктивным и конечным способом, например в десятичной системе счисления.
2. Требование конструктивности и конечности элементов областей определения и значения алгоритмических функций приводит к тому, что эти элементы можно перенумеровать и использовать таким образом в рассуждениях об алгоритмических функциях номера элементов вместо самих элементов.
Примеры вычислимых функций:
Z = x+y, z = min(x, y), z = x div y
Более сложные примеры прямо апеллируют к интуитивному понятию алгоритма:
Y = {наименьшее простое число, большее x и такое, что y+2 - также простое}
Y = {максимальный показатель степени в разложении числа x в произведение степеней простых сомножителей }
Примитивно-рекурсивные функции
0. Базисные примитивно-рекурсивные функции:
-
s(x) =df= x + 1 примитивно рекурсивна (по определению)
-
o(x) =df= 0 примитивно рекурсивна (по определению)
-
pi(x1,…,xi,…,xn) =df= xi примитивно рекурсивна (по определению)