Новая философская энциклопедия В 4 томах. Том 1 (1184478), страница 48
Текст из файла (страница 48)
ОдновременноА. Чёрч и X. Б. Карри создали одно из самых абстрактныхАЛГОРИТМпонятий алгоритма: λ-определимость, выразимость с помощью терма комбинаторной логики.И ранее созданные теоретические понятия, и самые элементарные, и самые абстрактные из вновь появившихсяуточнений алгоритма оказались эквивалентны. Этот факт,подтвержденный в дальнейшем для всех вновь появлявшихся точных определений алгоритма, послужил основойутверждения, скромно называемого в математике тезисомЧерча, хотя степень его подтвержденное™, ныне выше,чем у любого физического «закона». Содержательное понятие алгоритма эквивалентно по объему любому из имеющихся в данным момент математических уточнений этогопонятия, в частности вычислимости на машине Тьюринга.Одним из последних появилось уточнение алгоритма,наиболее близкое к современным языкам программирования, - рекурсивные схемы Скотта.
Это — совокупностьопределений видаf.(2) «= if Ρ ( ί ) then t(x) else r ( i ) ,где 1 - кортеж переменных, а сами определяемые функциимогут входить в выражения /, г. Определение понимаетсяследующим образом: проверяется предикат Р, если он истинен, вычисляется t, иначе г. Если в вычисляемом выражении встречаются определяемые функции, они вновь потем же правилам заменяются на их определения. Хотя пообъему определяемых функций существующие уточненияпонятия алгоритма эквивалентны, они различаются посвоей направленности. Эти различия можно подчеркнуть,рассматривая относительные алгоритмы, строящиеся набазе некоторых абстрактных структур данных и операцийнад ними. Относительные алгоритмы, получающиеся набазе различных определений алгоритма, могут определять разные классы функций при одних и тех же исходныхструктурах и элементарных операциях.
Так, напр., машиныТьюринга приводят к одним из наиболее узких определений относительных алгоритмов, а комбинаторная логика ирекурсивные схемы — наоборот, к весьма широким.При модификации машин Тьюринга разделением входнойи выходной ленты (со входом можно лишь читать, на выходную — лишь писать, причем после записи и чтения мынеобратимо сдвигаем ленты на одну ячейку) получаетсяважное понятие конечного автомата, моделирующее вычислительные машины без внешней памяти.
Возможностиконечных автоматов значительно меньше, в частности наних нельзя распознать простые числа.С понятием алгоритма тесно связано понятие порождающего процесса, или исчисления. Порождающий процессотличается от алгоритма тем, что он принципиально недетерминирован, его правила суть не предписания, а разрешения выполнить некоторое действие. Примером исчисления может служить логический вывод либо разбор вформальной грамматике.Рассмотрение алгоритмов показало, что нельзя ограничиваться всюду определенными функциями и соответственнонельзя проходить мимо выражений, не имеющих значения.Ошибка является компаньоном программы.
Одним из первых результатов теории ангоритмов явилась теорема о том,что не любую вычислимую функцию можно продолжитьдо всюду определенной вычислимой функции. Практическим примером таких функций является любой интерпретатор программ, напр., BASIC. Если не ограничивать возможности программиста, то нельзя создать интерпретатор,который невозможно было бы привести в нерабочеесостояние исполнением синтаксически корректной программы.Множество, характеристическое свойство которого является всюду определенным вычислимым предикатом, называется разрешимым.
Множество, принадлежность элементакоторому можно установить за конечное число шагов применением некоторого алгоритма, называется перечислимым. Напр., множество тавтологий классической логикивысказываний разрешимо, а множество тавтологий классической логики предикатов перечислимо. Заметим, что в случае перечислимого множества алгоритмически установитьможно лишь истинность, а не ложность. В классическойматематике имеет место следующий критерий разрешимости: множество разрешимо, если и оно, и его дополнениеперечислимы.
В конструктивной этот критерий эквивалентен принципу Маркова (см. Конструктивное направление).Другая характеризация перечислимого множества - множество объектов, выводимых в некотором исчислении.Необходимо отметить, что схема вычислительного процесса на компьютере конца 20 в. — написание программы наязыке высокого уровня, трансляция ее в машинный язык иисполнение компьютером — имеет теоретической основойтеорему об универсальном алгоритме. При любом точномопределении алгоритмов каждый алгоритм может быть задан своим определением, которое является конструктивным объектом.
Этот конструктивный объект может бытьалгоритмически в содержательном смысле (и при этомдостаточно просто и естественно) закодирован тем видомконструктивных объектов, которые обрабатываются данными алгоритмами. Напр., определение алгоритма можетбыть записано как слово в некотором алфавите, а если мывзяли определение алгоритма, в котором рассматриваютсялишь натуральные числа, такое слово может быть естественно представлено как число в системе счисления, основанием которой является количество букв в алфавите.
Тогда имеется универсальный алгоритм U, перерабатывающийлюбую пару (φ, Ρ), где φ — конструктивный объект, называемый записью или программой (относительно U) алгоритмаφ, в результат применения φ к Р. Универсальный алгоритмне может быть всюду определен. Примером универсального алгоритма может служить транслятор с алгоритмического языка, в частности с Паскаля, вместе с операционнойсистемой, исполняющей получившуюся программу.Если рассматривать лишь конструктивные объекты, тоалгоритм естественно отождествить с его программой относительно некоторого U.
То, что такое отождествлениеявляется ограниченным, показывают проблемы современной теории и практики программирования. Одной изсамых трудных возникающих в этом случае проблем является восстановление алгоритма по реализующей его конкретной программе.Если понятие алгоритма, перерабатывающего реальныеконструктивные объекты, можно считать однозначно определенным, то его обобщение на объекты высших типовдопускает многочисленные варианты, неэквивалентныедруг другу. Обобшение теории алгоритмов на абстрактныевычисления и объекты высших порядков является однимиз основных направлений исследований современной теории алгоритмов.77АЛГОРИТМДругим важнейшим направлением развития теории алгоритмов служит теория сложности вычислений, рассматривающая проблемы оценки ресурсов, необходимых дляработы алгоритмов.
Основы ее закладывали российскиеученые А. Н. Колмогоров и А. А. Марков и венгерский математик С. Кальмар. Вот некоторые из ее результатов, имеющих методологическое значение.Имеются два типа сложности — сложность определенияи сложность вычислений. Они раскрывают разные стороны исследуемых методов и объектов, хотя между нимиимеются некоторые зависимости. В частности, чем быстрее вычисление алгоритма, определяющего некоторыйобъект, тем, как правило, сложнее его описание. Во многих практических случаях, напр., для сортировки данных,приходится искать компромисс и использовать не самыебыстрые теоретически, хотя и более простые в действииалгоритмы.Если сложность определения практически не зависит отконкретного уточнения понятия алгоритма, то число шагови используемая память резко различаются, напр., для рекурсивных схем и машин Тьюринга.
Самое простое понятие машин Тьюринга оказалось наиболее подходящим длятеоретического анализа вычислительной сложности задач.Число шагов и используемая память — взаимозависимыехарактеристики вычислительного процесса. Часто удается убыстрить процесс, задействовав больше памяти, либоуменьшить память, увеличив число шагов процесса. Нотакая оптимизация ресурсов возможна лишь в ограниченных пределах, и более критическим является число шагов.Память теоретически можно неограниченно уменьшать,замедляя программу (конечно же она тем не менее растет сростом исходных данных, но не более чем линейно). Имеются и такие случаи, когда за счет сложности описанияалгоритма можно неограниченно убыстрять процесс вычисления (теорема об ускорении). Тем не менее практически и здесь быстро наступает предел ввиду неустойчивостиработы сложных алгоритмов.Практически вычислимыми оказываются функции, числошагов вычисления которых на машине Тьюринга можетбыть оценено некоторым многочленом от длины исходных данных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
