3.Простейшие эффективно вычислимые функции (операторы сдвига, аннулирования и проектирования). Оператор суперпозиции (подстановки) функций.

Для алгоритмических проблем типичным является то обстоятельство, что требуется найти алгоритм для решения задачи, в условия которой входят значения некоторой конечной системы целочисленных параметров x1, x2,…, xn, а искомым результатом также является целое число y. Следовательно, стоит вопрос о существовании алгоритма для вычисления значений числовой функции y, зависящей от целочисленных значений аргументов x1, x2,…, xn.

Определение 1. Функция называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значения.

Переход от алгоритма к эффективно вычислимой функции дает определенные преимущества. Дело в том, что все требования, которые предъявляются к алгоритмам, выполняются и для совокупности всех вычислимых функций, которая получила название совокупности рекурсивных функций.

Класс вычислимых функций можно построить следующим образом. Для начала выбираются простейшие функции:

1. (x) = x + 1 (оператор сдвига),

2. O(x) = 0 (оператор аннулирования),

3. Inm(x1, x2,…, xn) = xm (оператор проектирования).

Ясно, что все три простейшие функции всюду определены и интуитивно вычислимы.

Далее вводятся операции над функциями.

1. Суперпозиция функций. Пусть определены функции f1(x1, x2,…, xn), f2(x1, x2,…, xn), …, fm(x1, x2,…, xn) и функция (x1, x2,…, xm). Говорят, что функция (x1, x2,…, xn) получена суперпозицией функций fi(x1, x2,…, xn), если справедливо равенство

(x1, x2,…, xт) = ( f1(x1, x2,…, xn), f2(x1, x2,…, xn), …, fm(x1, x2,…, xn)).

Если каким-либо образом можно вычислить функции fi для определенных значений ai переменных xi, то, очевидно можно вычислить и функцию .

4.Оператор примитивной рекурсии и схема примитивной рекурсии. Примитивно рекурсивные функции, примеры. Класс примитивно рекурсивных функций и его замкнутость.

2. Схема примитивной рекурсии. Пусть имеются две функции (x2, x3,…, xn) и (x1, x2,… , xn, xn+1) (n > 1). Рассмотрим новую функцию, которая удовлетворяет следующим равенствам:

f(0, x2, x3,…, xn) = (x2, x3,…, xn),

f(y + 1, x2, x3,…, xn) = (y, f(y, x2, x3,…, xn), x2, x3,…, xn).

Отметим, что функция  зависит от n – 1 аргументов,  – от n + 1, а f – от n.

Функции, определенные с помощью таких равенств называются функциями, полученными по схеме рекурсии.

В качестве примера рассмотрим функцию f(y, x):

f(0, x) = x,

f(y + 1, x) = f(y, x) + 1.

Здесь функция (x) = x, а (y, f(y, x), x) = y + 1. Рассмотрим, как можно вычислить значение функции f(y, x) при y = 5, x = 2. Так как f(0, x) = (2) = 2, то из второго равенства последовательно имеем (начиная с y = 0):

f(1, 2) = (0, 2, 2) = 2 + 1 = 3,

f(2, 2) = (1, 3, 2) = 3 + 1 = 4,

f(3, 2) = (2, 4, 2) = 4 + 1 = 5,

f(4, 2) = (3, 5, 2) = 5 + 1 = 6,

f(5, 2) = (4, 6, 2) = 6 + 1 = 7 – искомое значение функции.

1.Рекурсивные функции

а) Терминологическое введение

По сути один и тот же метод, применительно к различным областям носит различные названия – это индукция, рекурсия и рекуррентные соотношения – различия касаются особенностей использования.

Под индукцией понимается метод доказательства утверждений, который строится на базе индукции при n=0,1, затем утверждение полагается правильным при n=n b и проводится доказательство для n+1.

Под рекурсией понимается метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом.

Термин рекуррентные соотношения связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.

Основной задачей исследования рекурсивно заданных функций является получение f(n) в явной или как еще говорят «замкнутой» форме, т.е. в виде аналитически заданной функции. В связи с этим рассмотрим ряд примеров:

б) Примеры рекурсивного задания функций

1. f(0)=0

f(n)= f(n-1)+1

2. f(0)=1

f(n)= n*f(n-1)

Последовательная подстановка дает – f(n)=1*2*3*…*n = n!

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

5.Оператор минимизации. Частично рекурсивные, общерекурсивные функции и уточнение интуитивного понятия алгоритма на основе частично рекурсивных функций. Соотношение между классами примитивно рекурсивных, частично рекурсивных и общерекурсивных функций. Тезис Черча.

3. Операция минимизации (-оператор). Пусть задана некоторая функция f(x, y). Зафиксируем значение x и выясним, при каком значении y f(x, y) = 0. Так как результат зависит от x, то наименьшее значение y, при котором f(x, y) = 0, есть функция от x. Принято обозначение

(x) = y[f(x, y) = 0].

(читается: «наименьшее y такое, что f(x, y) = 0»)

Аналогично можно определить функцию для многих переменных:

( x1, x2,…, xn) = y[f(x1, x2,…, xn, y) = 0].

Переход от функции f к функции  называется применением -оператора.

Функция  может быть вычислена следующим образом:

1. Вычислим f(x1, x2,…, xn, 0). Если это значение f = 0, то полагаем ( x1, x2,…, xn) = 0 и завершаем вычисление. Иначе переходим к следующему шагу.

2. Вычислим f(x1, x2,…, xn, 1). Если это значение f(x1, x2,…, xn, 1) = 0, то полагаем ( x1, x2,…, xn) = 1 и завершаем вычисление. Иначе переходим к следующему шагу. И т.д.

Если окажется, что для всех достижимых (т.е. принадлижащих области определения) значений у функция f(x1, x2,…, xn, у)  0, то функцию ( x1, x2,…, xn) считают неопределенной.

Уточнение понятия алгоритма

В истории математики накопилось много случаев длительных и часто безрезультатных поисков тех или иных алгоритмов. При этом естественно возникало сомнение в существовании алгоритма.

Одним из ярких примеров такого случая является история решения десятой проблемы Д.Гильберта.

В 1900 году на втором международном математическом конгрессе в Париже немецкий математик Давид Гильберт огласил список 23 трудных проблем, на важность решения которых он обращал внимание математической общественности. Среди них была и следующая 10-я проблема Гильберта: требуется выработать алгоритм, позволяющий для любого диофантова уравнения выяснить, имеет ли оно целочисленное решение.

Рассмотрим всевозможные диофантовы уравнения, т.е. уравнения вида P = 0, где P является многочленом с целочисленными коэффициентами. Такими будут, например, уравнения

x2 + y2 – 2xz = 0,

10x5 + 7x2 + 5 = 0,

из которых первое с тремя неизвестными, а второе с одним неизвестным. В общем случае рассматривают уравнения с любым числом неизвестных. Такие уравнения могут иметь целочисленные решения, а могут и не иметь.

Так, уравнения x2 + y2 – 2xz = 0 имеет бесконечное множество целочисленных решений, а уравнение 10x5 + 7x2 + 5 = 0 таких решений не имеет.

Для частного случая диофантова уравнения с одним неизвестным давно известен алгоритм, позволяющий найти все целочисленные решения. Установлено, что если уравнение

Рn(x) = a0xn + a1xn-1 +…+ an-1x + an = 0

с целочисленными коэффициентами имеет целый корень, то он обязательно является делителем аn. В связи с этим можно предложить такой алгоритм:

1. Найти все делители числа аn: d1, d2, …, dn.

2. Вычислить Pn(x) для каждого из делителей числа аn.

3. Если при некотором i из совокупности 1, 2, …, k Рn(di) = 0, то di – корень уравнения. Если при всех i = 1, 2, …, k Рn(di)  0, то уравнение не имеет целочисленных решений.

Поиски решения десятой проблемы Гильберта привлекли внимание многих математиков и длились около 70 лет. И только в 1968 году молодым математиком Ю.Матиясевичем было доказано, что нет алгоритма, дающего решение поставленной задачи.

В подходах к определению понятия алгоритма можно выделить три основных направления.

Первое направление связано с уточнением понятия эффективно вычислимой функции. Этим занимались А.Черч, К.Гедель, С.Клини, определившие алгоритм как последовательность построения сложных функций из более простых. В результате был выделен класс так называемых частично-рекурсивных функций, имеющих строгое математическое определение. Анализ идей, приведших к этому классу функций, дал им возможность высказать гипотезу о том, что класс эффективно вычислимых функций совпадает с классом частично рекурсивных функций.

Второе направление связано с машинной математикой. Здесь сущность понятия алгоритма раскрывается путём рассмотрения процессов, осуществляемых в машине. Впервые это было сделано Тьюрингом, который предложил самую общую и вместе с тем самую простую концепцию вычислительной машины. Её описание было дано Тьюрингом в 1937 году. При этом Тьюринг исходил лишь из общей идеи работы машины как работы вычислителя, оперирующего в соответствии с некоторым строгим предписанием.

Третье направление связано с понятием нормальных алгоритмов, введённым и разработанным российским математиком А.А.Марковым. В рамках этого направления алгоритм рассматривается как конечный набор правил подстановок цепочек символов.

Удивительным научным фактом является доказательство эквивалентности приведенных выше определений алгоритма. Эквивалентность двух абстрактных моделей алгоритма состоит в том, что любой класс проблем, которые можно решить с помощью моделей одного типа, можно решить и на моделях другого типа. Оказалось, что все известные алгоритмы могут быть представлены аналогичными алгоритмами в рамках предложенных направлений (различных определений алгоритма).

Для алгоритмических проблем типичным является то обстоятельство, что требуется найти алгоритм для решения задачи, в условия которой входят значения некоторой конечной системы целочисленных параметров x1, x2,…, xn, а искомым результатом также является целое число y. Следовательно, стоит вопрос о существовании алгоритма для вычисления значений числовой функции y, зависящей от целочисленных значений аргументов x1, x2,…, xn.

Определение 1. Функция называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значения.

Переход от алгоритма к эффективно вычислимой функции дает определенные преимущества. Дело в том, что все требования, которые предъявляются к алгоритмам, выполняются и для совокупности всех вычислимых функций, которая получила название совокупности рекурсивных функций.

Класс вычислимых функций можно построить следующим образом. Для начала выбираются простейшие функции:

1. (x) = x + 1 (оператор сдвига),

2. O(x) = 0 (оператор аннулирования),

3. Inm(x1, x2,…, xn) = xm (оператор проектирования).

Ясно, что все три простейшие функции всюду определены и интуитивно вычислимы.

Далее вводятся операции над функциями.

1. Суперпозиция функций. Пусть определены функции f1(x1, x2,…, xn), f2(x1, x2,…, xn), …, fm(x1, x2,…, xn) и функция (x1, x2,…, xm). Говорят, что функция (x1, x2,…, xn) получена суперпозицией функций fi(x1, x2,…, xn), если справедливо равенство

(x1, x2,…, xт) = ( f1(x1, x2,…, xn), f2(x1, x2,…, xn), …, fm(x1, x2,…, xn)).

Если каким-либо образом можно вычислить функции fi для определенных значений ai переменных xi, то, очевидно можно вычислить и функцию .

2. Схема примитивной рекурсии. Пусть имеются две функции (x2, x3,…, xn) и (x1, x2,… , xn, xn+1) (n > 1). Рассмотрим новую функцию, которая удовлетворяет следующим равенствам:

f(0, x2, x3,…, xn) = (x2, x3,…, xn),

f(y + 1, x2, x3,…, xn) = (y, f(y, x2, x3,…, xn), x2, x3,…, xn).

Отметим, что функция  зависит от n – 1 аргументов,  – от n + 1, а f – от n.

Функции, определенные с помощью таких равенств называются функциями, полученными по схеме рекурсии.

В качестве примера рассмотрим функцию f(y, x):

f(0, x) = x,

f(y + 1, x) = f(y, x) + 1.

Здесь функция (x) = x, а (y, f(y, x), x) = y + 1. Рассмотрим, как можно вычислить значение функции f(y, x) при y = 5, x = 2. Так как f(0, x) = (2) = 2, то из второго равенства последовательно имеем (начиная с y = 0):

f(1, 2) = (0, 2, 2) = 2 + 1 = 3,

f(2, 2) = (1, 3, 2) = 3 + 1 = 4,

f(3, 2) = (2, 4, 2) = 4 + 1 = 5,

f(4, 2) = (3, 5, 2) = 5 + 1 = 6,

f(5, 2) = (4, 6, 2) = 6 + 1 = 7 – искомое значение функции.

3. Операция минимизации (-оператор). Пусть задана некоторая функция f(x, y). Зафиксируем значение x и выясним, при каком значении y f(x, y) = 0. Так как результат зависит от x, то наименьшее значение y, при котором f(x, y) = 0, есть функция от x. Принято обозначение

(x) = y[f(x, y) = 0].

(читается: «наименьшее y такое, что f(x, y) = 0»)

Аналогично можно определить функцию для многих переменных:

( x1, x2,…, xn) = y[f(x1, x2,…, xn, y) = 0].

Переход от функции f к функции  называется применением -оператора.

Функция  может быть вычислена следующим образом:

1. Вычислим f(x1, x2,…, xn, 0). Если это значение f = 0, то полагаем ( x1, x2,…, xn) = 0 и завершаем вычисление. Иначе переходим к следующему шагу.

2. Вычислим f(x1, x2,…, xn, 1). Если это значение f(x1, x2,…, xn, 1) = 0, то полагаем ( x1, x2,…, xn) = 1 и завершаем вычисление. Иначе переходим к следующему шагу. И т.д.

Если окажется, что для всех достижимых (т.е. принадлижащих области определения) значений у функция f(x1, x2,…, xn, у)  0, то функцию ( x1, x2,…, xn) считают неопределенной.

Определение 2. Функция f(x1, x2,…, xn) называется частично рекурсивной, если она может быть получена за конечное число шагов из простейших функций при помощи операций суперпозиции, схем примитивной рекурсии и -оператора.

Определение 3. Функция f(x1, x2,…, xn) называется общерекурсивной, если она частично рекурсивна и всюду определена.

Примерами общерекурсивных функций являются: f(x, y) = x + y, f(x, y) = x  y, f(x, y) = x + n.

Тезис А. Чёрча. Каждая интуитивно вычислимая функция является частично рекурсивной.

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