рекурсивных функций, имеющих строгое математическое определение. Такие функции вычислимы, то есть существует алгоритм для их вычисления; если же функция не принадлежит к этому классу, то не существует алгоритма её вычисления (не надо его и искать).
2.Второе направление связано с машинной математикой путём рассмотрения процессов, осуществляемых машиной (Пост, Тьюринг). Впервые это сделали независимо друг от друга Тьюринг и Пост (1937). Это направление часто называют машиной Тьюринга. Программа для такой машины и есть алгоритм вычисления так называемой тьюринговой функции. Если же функция не является тьюринговой, то не существует алгоритма её вычисления.
3.Третье направление рассматривает алгоритм как преобразование слов в некотором алфавите, при этом элементарными операциями являются подстановки, то есть замены части слова другим словом. Такие алгоритмы носят название «нормальных» алгоритмов. Они разработаны А. А. Марковым.
Иуже в конце 20-го века разработаны так называемые нейронные сети — тоже строгое математическое определение алгоритма.
В дальнейшем будем рассматривать так называемые числовые функции, то есть функции, аргументы и значения которых принадлежат множеству натуральных чисел с нулём 0: {0, 1, 2, 3, … } . Если число аргументов , то область определения таких функций декартово произведение 0 × 0 × … × 0 = 0 , а область значений — 0.
Вычислимые функции — числовые функции, значения которых можно вычислить посредством некоторого алгоритма.
Например, sin не является числовой вычислимой функцией, так как хотя бы sin 1 даже на интуитивном уровне не вычислить машине точно, сколько знаков не брать.
22. Рекурсивные функции. 3 простейших ПРФ (примитивно-рекурсивных функций). Оператор суперпозиции. Примеры
Рекурсивные (рекуррентные) функции — это такие функции, значения которых можно вычислить для + 1, если можно вычислить до , то есть каждое последующее значение вычисляется, если известны предыдущие.
Пример — числа Фибоначчи — последовательность чисел ( ), удовлетворяющая условиям:
(0) = 1, (1) = 1, ( + 2) = ( ) + ( + 1), то есть 1, 1, 2, 3, 5, 8, 13, 21, …
Рекурсивные функции разбиваются на два класса:
1.Примитивно-рекурсивные.
2.Частично-рекурсивные.
Если функция частично-рекурсивная, то она и примитивно-рекурсивная. Обратное неверно. То есть класс частично-рекурсивных функция больше, так как включает в себя все примитивно-рекурсивные функции.
Введём три простейшие рекурсивные функции, которые по определению считаются примитивно-рекурсивными (ПРФ).
1.( ) = 0 — нуль-функция, оператор аннулирования.
2.( ) = + 1 — прибавление 1, функция Пеано, оператор сдвига.
3. |
( |
, … , |
) = |
, |
, = 1 … — |
функция-проектор, оператор |
|
1 |
|
|
|
0 |
|
проектирования. В частности, 1( ) = — простейшая ПРФ.
Очевидно, что эти три функции всюду определены (на 0) и вычислимы.
Оператор суперпозиции (получение сложной функции, или «функции от
функции»). |
|
|
|
|
|
|
|
|
|
|
|
||
Пусть |
|
даны функции |
( , … , |
), |
2 |
( , … , ), … , |
|
( , … , ) |
и функция |
||||
|
|
|
1 |
1 |
|
|
1 |
|
1 |
|
|
||
( , … , |
|
). Тогда применение оператора суперпозиции даёт новую функцию: |
|||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
( 1, … , ) = ( 1( 1, … , ), … , ( 1, … , ))
То есть в функцию вместо подставили ( 1, … , ).
Смысл оператора: если можно у вычислимой функции вычислить аргументы по формулам ( ), то и саму функцию также можно вычислить. То есть вычислимая сложная функция тоже вычислима.
Например, с помощью этого оператора можно получить из простейших рекурсивных функций следующие функции:
( ( )) = (0) = 1
( ( ( ))) = ( (0)) = (1) = 2
( ( ( ))) = ( ( + 1)) = ( + 2) = + 3
(… ( |
( , … , |
)) … ) = + |
|
|
|
1 |
|
|
|
− раз |
|
1( ( + 1)) = 1( + 2) = + 2
23. Оператор ПР (примитивной рекурсии). Доказать, что функции + , ,
|
|
|
|
−̇ , −̇ , | − | — ПРФ |
|
|
||||||
Примитивная рекурсия. |
|
|
|
|
|
|
|
|
||||
( + 1) -местная |
функция ( , … , |
, ) (то |
есть |
|
функция |
( + 1) аргументов) |
||||||
|
|
|
|
1 |
|
|
|
|
|
|
|
|
получена |
из |
-местной функции |
( , … , ) |
и |
|
( + 2) |
-местной |
функции |
||||
( , … , |
, , ) |
|
|
|
1 |
|
|
|
|
|
|
|
с |
помощью оператора примитивной рекурсии, если |
значение |
||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
( |
, … , |
, ) можно вычислить по так называемой схеме примитивной рекурсии: |
||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( , … , , 0) = ( , … , |
|
) |
|
|
||||
|
|
|
|
1 |
|
|
1 |
|
|
|
|
|
( 1, … , , + 1) = ( 1, … , , , ( 1, … , , ))
В это случае говорят: «рекурсия проводится по ».
При = 0 функция одного аргумента ( ) получается примитивной рекурсией по из = = и функции двух переменных ( , ) следующим образом:
(0) = = , ( + 1) = ( , ( ))
При = 1 функция двух аргументов ( , ) получается примитивной рекурсией поиз ( ) и функции трех переменных ( , , ) следующим образом:
( , 0) = ( ), ( , + 1) = ( , , ( , ))
При = 2 функция трех аргументов ( , , ) получается примитивной рекурсией поиз ( , ) и функции четырёх переменных ( , , , ) следующим образом:
( , , 0) = ( , ), ( , , + 1) = ( , , , ( , , ))
Обычно рекурсию проводят по последнему аргументу, но всегда можно переставить аргументы с помощью оператора суперпозиции.
Функция ( , … , ) называется примитивно-рекурсивной (ПРФ), если она может быть получена с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии, применённых к простейшим функциям
( ), ( ), ( 1, … , ).
Замечание 1. Очевидно, что для получения ПРФ функции, участвующие в схеме ПРФ и , должны быть тоже ПРФ.
Замечание 2. Очевидно, что ПРФ от переменных определена на пространстве 0 .
Замечание 3. Если про некоторые функции известно, что они ПРФ, то операторы можно применить к ним, а не доходить каждый раз до простейших.
Замечание 4. Если ( 1, 2) — ПРФ, то ( 2, 1) — тоже ПРФ, так как получена из( 1, 2) оператором суперпозиции.
Докажем, что следующие функции — ПРФ:
1. |
( , ) = + . Введем ( ) = — ПРФ, так как = 1( ). |
|
( , + 1) = + + 1 = ( + ) + 1 = ( , ) + 1 |
|
Введём ( , , ) = + 1 — ПРФ, так как + 1 = ( ). |
|
Тогда ( , ) = + получается по схеме примитивной рекурсии по : |
|
( , 0) = ( ) = = 1 ( ) |
|
1 |
|
{ ( , + 1) = ( , , ( , )) = ( , ) + 1 |
|
Следовательно, ( , ) = + — ПРФ. |
|
Следствие: сумма двух ПРФ есть также ПРФ. |
2. |
( , ) = . Введём ( ) = 0 — ПРФ. |
|
( , + 1) = ( + 1) = + = ( , ) + |
|
Введём ( , , ) = + — ПРФ (доказано выше). |
|
Тогда ( , ) = получается по схеме примитивной рекурсии: |
|
( , 0) = ( ) = 0 = ( ) |
|
{ ( , + 1) = ( , , ( , )) = ( , ) + |
|
Следовательно, ( , ) = — ПРФ. |
|
Следствие: произведение двух ПРФ есть также ПРФ. |
3. |
( ) = −̇ = { − 1, если ≥ 1 , 0: 0, 1, 2, …. |
0, если = 0
Эта функция получается по схеме примитивной рекурсии:
(0) = = 0 = ( )
{ ( + 1) = ( , ( )) = = 12( , ( ))
Где 12( , ( )) — функция-проектор (всегда выбирает ), ПРФ.
− , если ≥ 4. ( , ) = −̇ = { 0, если < .
Эта функция получается по схеме примитивной рекурсии:
{ ( , + 1) = ( , , ( , )) = ( , )−̇1
Где ( , , ) = −̇1 — ПРФ (доказано выше).
5. ( , ) = | − | = ( −̇ ) + ( −̇ ). Если ≥ , то | − | = − + 0. Если ≥ , то | − | = 0 + − .
− , ≥ То есть | − | = { − , ≥ .
Очевидно, что функция ( , ) = | − | — ПРФ как сумма двух ПРФ. Примитивно-рекурсивные функции определены для всех значений аргументов из 0 .
24.Оператор минимизации. Частично-рекурсивные функции. Доказать, что
− , ≥
÷ = {не определена, < — ЧРФ. Точное определение алгоритма. Тезис
Чёрча
ПРФ — примитивно-рекурсивная функция, определена для всех значений аргументов (каждый из аргументов пробегает свои значения независимо от других). Иногда это является недостатком, в том смысле, что вычислимая функция на самом деле не является ПРФ из-за того, что определена не для всех значений аргументов. Напомним, что и аргументы вычислимой функции, и сама функция принимают только неотрицательные целочисленные значения.
|
− , ≥ |
|
|
Например, |
( , ) = ÷ = {не определена, < |
естественно |
считать |
вычислимой. |
|
|
|
Но такие функции не могут быть ПРФ. Поэтому требуется ввести ещё один оператор.
Оператор минимизации ( -оператор).
Пусть имеется функция ( 1, … , , ) и пусть 1, 2, … , — фиксированы, тогда возможны 3 случая:
1.При любых : ( 1, … , , ) ≠ 0 . В этом случае будем считать, что оператор минимизации ( ) = ( 1, … , ) не определен в точке ( 1, … , ).
2.( 1, … , , 0) = 0. Тогда ( ) = ( 1, … , ) = 0.
3.Пусть — наименьший корень уравнения ( 1, … , , ) = 0 (где 1, … , — фиксированы). Тогда возможны 2 случая:
a.( 1, … , , − 1), ( 1, … , , − 2), … , ( 1, … , , 0) ≠ 0 и определены, тогда ( ) = ( 1, … , ) = .
b.Среди ( 1, … , , − 1), ( 1, … , , − 2), … , ( 1, … , , 0) есть хотя бы одно неопределённое значение, тогда ( ) = ( 1, … , ) тоже не определен.
Пишем |
( ) = ( |
, … , ) , так как очевидно, что |
оператор |
|
( ) зависит от |
|
|
|
1 |
|
|
|
|
( , … , ), то есть от точки, в которой мы его считаем. |
|
|
|
|||
1 |
|
|
|
|
|
|
Оператор минимизации ( ) — функция переменных |
( , … , ), значение |
||||||||
|
|
|
|
|
|
|
1 |
|
|
которой равно наименьшему корню уравнения ( , … , , ) = 0: |
( ) = при |
||||||||
|
|
|
|
|
1 |
|
|
|
|
условии, |
что |
определены |
значения |
( , … , |
, − 1), ( , … , , − |
||||
|
|
|
|
1 |
|
|
1 |
|
|
2), … , ( , … , |
, 0), то есть значения при , меньших чем . |
|
|
|
|||||
1 |
|
|
|
|
|
|
|
|
|
Для вычисления оператора минимизации |
есть следующий алгоритм: |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
1.Вычисляем ( 1, … , , 0). Если равно 0, то ( ) = 0. Если же не равно 0, то переходим следующему шагу.
2.Вычисляем ( 1, … , , 1). Если равно 0, то ( ) = 1. Если же не равно 0, то
переходим к следующему шагу ( ( 1, … , , 2)) и так далее.
Если ( ) ( 1, … , , ) ≠ 0 или на каком-то шаге значение ( 1, … , , ) не определено, то ( ) считаем неопределенным.
Частично-рекурсивная функция — функция, которая может быть получена с помощью применения конечного числа раз 3-х операторов (суперпозиции,
примитивной рекурсии и минимизации) к простейшим ПРФ ( ( ), ( ), |
( |
, … , )). |
|||||
|
|
|
|
|
|
1 |
|
|
− , ≥ |
|
|
|
|
||
|
Доказать, что ÷ = {не определена, < — частично-рекурсивная функция. |
||||||
|
Вспомним, что функции −̇ = { |
− , если ≥ |
и + — ПРФ. |
|
|
||
|
|
0, если < |
|
|
|||
|
Рассмотрим функцию ( , ) = | − | = ( −̇ ) + ( −̇ ). Эта функция есть ПРФ как |
||||||
сумма двух ПРФ. |
|
|
|
|
|
|
|
|
Введём теперь функцию ( , , ) = | − ( + )|. Очевидно, что она ПРФ. |
|
|||||
|
Тогда ( , ) = − = ( ) = |
{ |
− , ≥ |
. |
|
|
|
|
|
|
|
|
|||
|
|
|
не определена, < |
|
|
|
|
|
|
|
|
|
|
||
|
Действительно, уравнение ( , , ) = 0 это уравнение | − − | = 0. |
|
|
||||
|
Если ≥ , то корень = − — наименьший корень этого уравнения, так как: |
||||||
|
( , , − 1) = | − − ( − − 1)| = 1 ≠ 0 |
|
|
||||
|
( , , − 2) = | − − ( − − 2)| = 2 ≠ 0 |
|
|
||||
|
|
|
… |
|
|
|
|
|
( , , 0) = | − − 0| = | − | ≠ 0 если ≠ 0 |
|
|
||||
|
Если = , то корень = 0. |
|
|
|
|
|
|
|
Если же < , то ни при каком 0 = {0, 1, 2, … } | − − | ≠ 0, то есть оператор |
||||||
|
( ) не определен. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таким образом мы доказали, что ( , ) получена оператором минимизации из ПРФ, и поэтому является частично-рекурсивной функцией.
Общерекурсивная функция — частично-рекурсивная функция, которая определена при всех возможных значениях аргументов.
Тезис Чёрча. Любая частично-рекурсивная функция является вычислимой, то есть существует алгоритм для её вычисления, и, наоборот, любая вычислимая функция есть частично-рекурсивная функция.
Этот тезис нельзя доказать, так как он связывает строгое математическое понятие частично-рекурсивной функции с нестрогим математическим понятием вычислимой функции, но его можно опровергнуть, если построить пример функции вычислимой, но не являющейся частично-рекурсивной. Однако, до сих пор такой функции не найдено.
Первое строгое определение алгоритма:
Всякий алгоритм — есть процесс вычисления частично-рекурсивной функции. Если функция не частично-рекурсивная алгоритма для её вычисления нет.