8_Теория алгоритмов. (1019129), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

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

Всякий алгоритм однозначно ставит в соответствие исходным данным (в случае если определен на них) определенный результат. Поэтому с каждым алгоритмом однозначно связана функция, которую он вычисляет. Исследование этих вопросов привело к созданию в 30-х годах прошлого века теории рекурсивных функций. В этой теории, как и вообще в теории алгоритмов принят конструктивный, финитный подход, основной чертой которого является то, что все множество исследуемых объектов (в данном случае функций) строится из конечного числа исходных объектов – базиса – с помощью простых операций, эффективная вычислимость которых достаточна очевидна. Операции над функциями будем называть операторами.

Будем рассматривать только числовые функции, т.е. функции, аргументы и значения которых принадлежат множеству натуральных чисел N (в теории рекурсивных функций полагают N=0, 1, 2, …). Иначе говоря, числовой n-местной функцией называется функция, определенная на некотором подмножестве с натуральными значениями. Если область определения совпадает с множеством , т.е. , то говорят, что функция f всюду определенная, в противном случае – частично определенная.

Например:

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

– частично определенная функция (она определена при x  y).

Рекурсивным определением функции принято называть такое определение, при котором значения функции для данных аргументов определяются значениями функции для более простых аргументов (уже вычисленных) или значениями более простых функций.

Простейшим примером рекурсивного определения являются числа Фиббоначи, представляющие собой последовательность чисел , удовлетворяющих условиям

,

т.е. числа 1, 1, 2, 3, 5, 8, 13 … Каждое последующее число является суммой двух предыдущих чисел.

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

Примитивно-рекурсивные функции

Очевидно, что к вычислимым функциям следует отнести все константы, т.е. 0 и все натуральные числа 1, 2, 3 …

Однако в прямом включении бесконечного множества констант в базис нет необходимости. Для этого достаточно нуль функции 0(x)=0 и функции следования S(x)=x+1, чтобы получить весь натуральный ряд. Кроме того, в базис следует включить семейство функций проектирования (или введения фиктивных переменных)

.

Следующие всюду определенные числовые функции назовем простейшими:

1. 0(x)=0 – нуль-функция.

2. S(x)=x+1– функция следования.

3. , где – проектирующая функция.

Все эти функции вычислимы в интуитивном смысле.

Определим теперь операторы. Они обладают тем свойством, что, применяя их к функциям, вычислимым в интуитивном смысле, получаем функции, также вычислимые в интуитивном смысле.

1. Оператор суперпозиции. Суперпозиция является мощным средством получения новых функций из уже имеющихся. Напомним, что суперпозицией называется любая подстановка функций в функции. Оператором суперпозиции называется подстановка в функцию от m переменных m функций от n одних и тех же переменных. Например, для функций

(5-1)

В этом случае говорят, что n-местная функция получена с помощью оператора суперпозиции из m-местной функции и n-местных функций , если

.

1. Оператор примитивной рекурсии. Оператор примитивной рекурсии определяет -местную функцию f через n-местную функцию g и -местную функцию h следующим образом:

(5-2)

Пара равенств (2-2) называется схемой примитивной рекурсии.

Тот факт, что функция f определена схемой (5-2) выражается равенством . В случае, когда n=0, т.е. определяемая функция f является одноместной, схема (5-2) принимает более простой вид:

; (5-3)

где C – константа.

Схемы (5-2) и (5-3) определяют f рекурсивно не только через другие функции g и h, но и через значения f в предшествующих точках: значение f в точке y+1 зависит от значения f в точке y. Для вычисления понадобится k+1 вычислений по схеме (5-2) для . Пример – вычисление n!.

Существенным в операторе примитивной рекурсии является то, что независимо от числа переменных в f рекурсия ведется только по одной переменной y, остальные n переменных на момент применения схем (5-2) и (5-3) зафиксированы и играют роль параметров.

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

Этому определению можно придать более формальный индуктивный вид.

1. Функции , и для всех натуральных n, m, где m  n, являются примитивно рекурсивными.

2. Если g₁(x₁, x₂, …, x_n), …, g_m(x₁, x₂, …, x_n), h(x₁, x₂, …, x_n) примитивно рекурсивные, то – примитивно-рекурсивные функции для любых натуральных n, m.

3. Если и – примитивно рекурсивные функции, то – примитивно-рекурсивная функция.

4. Других примитивно-рекурсивных функций нет.

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

Пример 1. Покажем, что сложение, умножение, возведение в степень примитивно-рекурсивно:

1. Сложение примитивно-рекурсивно:

;

.

Таким образом, , где .

1. Умножение примитивно-рекурсивно:

.

1. Возведение в степень примитивно-рекурсивно:

;

.

8.4 МАШИНА ТЬЮРИНГА.

Введение. История вопроса.

В 1935 г. возникло такое положение: свойства, обнаруженные у некоторого точно определенного класса вычислимых теоретико-числовых функций, изучавшихся Чёрчем и Клини в 1932—1935 гг. и названных " -определимыми функциями", упорно подсказывали мысль, что этот класс, может быть, охватывает все функции, которые в соответствии с нашим интуитивным представлением можно рассматривать как вычислимые. При этих обстоятельствах Чёрч выдвинул тезис (опубликован в 1936 г.), что все функции, которые интуитивно мы можем рассматривать как вычислимые, или, говоря его словами, как «эффективно вычислимые», являются -определимыми, или, эквивалентным образом, общерекурсивными.

Несколько позже, но независимо появилась статья Тьюринга (1936), в которой был введен еще один точно определенный класс интуитивно вычислимых функций, которые мы будем называть «функциями, вычислимыми по Тьюрингу», и относительно этого класса было высказано такое же утверждение; это утверждение мы называем тезисом Тьюринга. Вскоре Тьюрингом [1937] было показано, что его вычислимые функции — это то же самое, что -определимые функции, и, следовательно, то же самое, что и общерекурсивные функции. Поэтому тезисы Тьюринга и Чёрча эквивалентны. Мы будем обычно ссылаться на оба эти тезиса как на тезис Чёрча, а в связи с тем его вариантом, в котором идет речь о «машинах Тьюринга»,— как на тезис Чёрча — Тьюринга. В 1936 г. Пост независимо от Тьюринга опубликовал в довольно сжатом изложении формулировку, в основе ту же, что у Тьюринга. В 1943 г., основываясь на своей неопубликованной работе 1920— 1922 гг., он опубликовал третий эквивалент аналогичного тезиса. Еще одну эквивалентную формулировку дает теория алгоритмов Маркова [1951г].

Область использования машины Тьюринга

Понятие машины Тьюринга возникает в результате прямой попытки разложить интуитивно известные нам вычислительные процедуры на элементарные операции: Тьюринг привел ряд доводов в пользу того, что повторения его элементарных операций было бы достаточно для проведения любого возможного вычисления. Поэтому машина Тьюринга (МТ) используется:

1. если требуется доказать возможность алгоритмической реализации вычислительной функции;

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

Для этого мы моделируем работу произвольного алгоритма в терминах рассматриваемой задачи. Затем определяется класс машин-вычислителей, которые могут решить данную задачу – формально описываются правила работы машины, исходные данные, ограничения и т.д. (поскольку в определении задачи ничего не говорится о программах так таковых в привычном для нас понимании, то алгоритмическая разрешимость или неразрешимость, сводится к проблеме остановки произвольного алгоритма решения задачи). В качестве машины-вычислителя выберем машину Тьюринга, поскольку ранее было показано, что всякая вычислимая функция реализуема на МТ и сведем решение данной задачи к существующим группам задач, для которых известно, что они решаются на МТ.

Принцип работы машины Тьюринга.

Далее вставка 8А

8.5. Тезис Черча. Алгоритмически неразрешимые проблемы.

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

Тезис Тьюринга. Для любого алгоритма, понимаемого в интуитивном смысле, можно построить машину Тьюринга, функционирование которой эквивалентно этому алгоритму.

Понятие машины Тьюринга является строгим уточнением понятия алгоритма. Переход от интуитивного понятия алгоритма к точному понятию машины Тьюринга позволяет решить вопрос алгоритмической (машинной) разрешимости той или иной проблемы.

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

Характеристики

Список файлов книги