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

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

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

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

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

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

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

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

Всякий алгоритм однозначно ставит в соответствие исходным данным (в случае если определен на них) определенный результат. Поэтому с каждым алгоритмом однозначно связана функция, которую он вычисляет. Исследование этих вопросов привело к созданию в 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-местных функций , если

.

2 Оператор примитивной рекурсии. Оператор примитивной рекурсии определяет -местную функцию 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. Сложение примитивно-рекурсивно:

;

.

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

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

.

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

;

.

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