Формализация понятия алгоритма. Универсальные модели алгоритмов

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

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

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

Второй тип модели связан с развитием вычислительной техники и основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный дискретный момент времени весьма примитивные операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Кроме того, эвристика этой модели близка к ЭВМ и, следовательно, к инженерной интуиции. Основной теоретической моделью этого типа является созданная в 30-х годах концепция машины Тьюринга. Именно машина Тьюринга явилась моделью современной ЭВМ и способствовала развитию современной вычислительной техники.

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

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

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

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

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

Например:

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru – всюду определенная двуместная функция.

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru – частично определенная функция (она определена при x ³ y).

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

Простейшим примером рекурсивного определения являются числа Фиббоначи, представляющие собой последовательность чисел Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru , удовлетворяющих условиям

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru ,

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

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

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

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

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

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru .

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

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

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

3) Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru , где Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru – проектирующая функция.

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

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

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

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru (5-1)

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

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru .

2 Оператор примитивной рекурсии. Оператор примитивной рекурсии Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru определяет Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru -местную функцию f через n-местную функцию g и Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru -местную функцию h следующим образом:

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru (5-2)

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

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

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru ; (5-3)

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

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

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

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

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

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

2. Если g1(x1, x2, …, xn), …, gm(x1, x2, …, xn), h(x1, x2, …, xn) примитивно рекурсивные, то Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru – примитивно-рекурсивные функции для любых натуральных n, m.

3. Если Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru и Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru – примитивно рекурсивные функции, то Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru – примитивно-рекурсивная функция.

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

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

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

1. Сложение Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru примитивно-рекурсивно:

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru ;

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru .

Таким образом, Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru , где Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru .

2. Умножение Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru примитивно-рекурсивно:

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru .

3. Возведение в степень Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru примитивно-рекурсивно:

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru ;

Формализация понятия алгоритма. Универсальные модели алгоритмов - student2.ru .

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

Наши рекомендации