Лекции - Теория алгоритмов
Подождите немного. Документ загружается.
Нулевая функция
► Рассмотрим n-арную функцию o
n
(x
1
,x
2
,...,x
n
), заданную
правилом
o
n
(x
1
,x
2
,...,x
n
)=0
для всех натуральных чисел x
1
,x
2
,...,x
n
.
► Данная функция называется нулевой функцией.
Нулевая функция, как и функция следования, очевидно
вычислима.
► Нулевую функцию при n=1 обозначаем через o(x).
Поэтому
O(x)=0
для всех натуральных чисел x.
► Нулевая функция при n=0 обозначается через о
0
и
отождествляется с числом 0.
Функция проектирования
► Пусть n 1, 1m n. Зададим функцию
проектирования I
n
m
(x
1
,x
2
,...,x
n
) правилом
I
n
m
(x
1
,x
2
,...,x
n
)=x
m
.
► Данная функция строке аргументов (x
1
,x
2
,...,x
n
)
сопоставляет ее компоненту x
m
с номером m.
Вычислимость функции проектирования обеспечивается
нашей способностью найти в строке (x
1
,x
2
,...,x
n
) место
с номером m и указать число на этом месте.
► Итак, следующие простейшие функции вычислимы:
► Функция следования.
► Нулевая функция.
► Функция проектирования .
Способы построения
новых вычислимых функций
► У нас имеется исходный набор простейших (базисных)
вычислимых функций. Мы будем пополнять этот набор
вычислимых функций. Для этого рассмотрим способы
построения из уже имеющихся вычислимых функций
новых вычислимых функций.
► Оператор суперпозиции S. Рассмотрим действие,
которое назовем оператором суперпозиции
(регулярной суперпозиции). С помощью этого
действия из некоторых функций h, g
1
, g
2
,..., g
m
создается новая функция f. Пусть m, n – натуральные
числа. Определим новую функцию f(x
1
,x
2
,...,x
n
) по
правилу:
f(x
1
,x
2
,...,x
n
)=
=h(g
1
(x
1
,x
2
,...,x
n
) ,g
2
(x
1
,x
2
,...,x
n
),...,g
m
(x
1
,x
2
,...,x
n
)).
Способы построения новых вычислимых функций
(продолжение)
► Функция f является частичной функцией от n
переменных. Ее значение f(x
1
,x
2
,...,x
n
)
определено тогда и только тогда, когда
определены все выражения в правой части из
последнего равенства. Если функции h, g
1
,
g
2
,..., g
m
вычислимы, то и функция f
вычислима. Алгоритм ее вычисление
описывается правой частью равенства. В
случае существования значения функции f, мы
за конечное число шагов получим число
f(x
1
,x
2
,...,x
n
) действиями, соответствующими
интуитивному представлению об алгоритме.
Способы построения новых вычислимых
функций (продолжение)
► Оператор примитивной рекурсии R. Рассмотрим
действие, которое назовем оператором примитивной
рекурсии. С помощью оператора примитивной
рекурсии мы конструируем функцию f от n+1
переменной из некоторых частичных функций g и h.
При этом функция g имеет n переменных, а функция h
имеет n+2 переменных. Значения новой функции f
вычисляем по двум правилам:
f(x
1
,x
2
,...,x
n
,0)= g(x
1
,x
2
,...,x
n
),
f(x
1
,x
2
,...,x
n
, y+1)= h(x
1
,x
2
,...,x
n
,y, f(x
1
,x
2
,...,x
n
,y)).
► Слово рекурсия (recurso на латинском языке -
возвращаюсь) означает вычисление значения
f(x
1
,x
2
,...,x
n
, y+1) с использованием f(x
1
,x
2
,...,x
n
, y)
(возвращением к ранее вычисленному значению).
► Как и в случае оператора суперпозиции, вычислимость
исходных функций g и h влечет вычислимость
построенной из них функции f.
Определение примитивно
рекурсивной функции
► Функция f называется примитивно рекурсивной, если она может быть
получена из простейших функций следования, нулевой функции и
функции проектирования с помощью конечного числа применений
операторов суперпозиции и примитивной рекурсии.
Тоже самое можно выразить в виде трех правил.
1) Простейшие функции
s(x)=x+1, o
n
(x
1
,x
2
,...,x
n
)=0, I
n
m
(x
1
,x
2
,...,x
n
)=x
m
примитивно рекурсивны.
2) Если функция f получена из примитивно рекурсивных функций с
помощью оператора суперпозиции или с помощью оператора
примитивной рекурсии, то функция f примитивно рекурсивна.
3) То, что функция f примитивно рекурсивна, устанавливается несколькими
применениями правил 1) и 2).
► Всякой примитивной рекурсивной функции можно приписать n -
наименьший номер шага, на котором она может быть получена.
Следовательно, можно проводить доказательство различных утверждений
для примитивно рекурсивных функций индукцией по шагу, на котором
они получены.
Примеры примитивно рекурсивных
функций
► Теорема 1. Следующие функции
являются примитивно рекурсивными:
1. f(x)=x;
2. g(x)=x+2;
3. Постоянная унарная функция f(x)=a;
4. Нульарная функция.
Операция введения фиктивных
переменных
► Пусть функция f(x
1
,x
2
,...,x
n
) примитивно рекурсивна. Добавим в строке
переменныхf(x
1
,x
2
,...,x
n
) еще одну переменную x
n+1
. Получим строку
x=(x
1
,x
2
,...,x
n
,x
n+1
) из n+1 переменной. Для функций проектирования
очевидны n равенств
I
n+1
1
(x)=x
1
,..., I
n+1
n
(x)=x
n
.
Введем функцию f’(x) от n+1 переменной правилом
f’ (x
1
,x
2
,...,x
n
,x
n+1
)=f(I
n+1
1
(x)=x
1
,..., I
n+1
n
(x))= f(x
1
,x
2
,...,x
n
).
Так как функция f примитивно рекурсивна, то и новая функция f’
примитивно рекурсивна.
► В дальнейшем мы будем вводить фиктивную переменную, и из
примитивно рекурсивной функции от n переменных получать примитивно
рекурсивную функцию от n+1 переменной. При такой операции введения
фиктивного переменной вместо обозначения f’ для новой функции
будем сохранять обозначение f исходной функции.
Еще две примитивно рекурсивные
функции
►Теорема 2. Функция сложения
f(x,y)=x+y
и функция умножения
f(x,y)=xy
примитивно рекурсивны.
Лекция 4. Частично рекурсивные
функции. Тезис Черча
► Пусть дана вычислимая функция
g(x
1
,x
2
,...,x
n
,y)
от
n+1
переменной, где
n0.
Нам нужно найти наименьшее число
y
с
условием
g(x
1
,x
2
,...,x
n
,y)=0.
Введем следующее ограничение.
Процедура нахождения числа
y
должна быть алгоритмом. Поэтому
должен быть представлен точный список действий для
неинтеллектуального исполнителя (машины) по нахождению
y
,
например, последовательная проверка одного за другим
следующих равенств
g(x
1
,x
2
,...,x
n
,0)=0,
g(x
1
,x
2
,...,x
n
,1)=0,
.............................
g(x
1
,x
2
,...,x
n
,y)=0.