Новая философская энциклопедия В 4 томах. Том 1 (1184478), страница 49

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

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

Степень данного многочлена определяетобъем исходных данных, которые могут быть обработаны.В частности, для вычислений часто приемлемы алго­ритмы, число шагов которых растет как четвертая степеньот исходных данных, а для работы с большими базамиданных обычно неприемлемы даже квадратично расту­щие алгоритмы.Экспоненциальный рост числа шагов машины Тьюрин­га означает, что область реального применения данногоалгоритма жестко ограничена сверху и никакой рост вы­числительных ресурсов не может значительно поднятьпланку. Напр., для увеличения числа булевых переменныхв проверяемой пропорциональной формуле на 1 придетсяподнимать быстродействие машины в два раза.

Более чемэкспоненциальный рост означает практическую невычис­лимость.Прямая и обратная функции могут сильно различаться посложности, поэтому строить простые коды, практическине расшифровываемые без знания ключа. Это послужилоосновой современной практики кодирования и электрон­ных подписей.Сложность описания системы — гораздо более сложныйобъект, чем само ее описание. Т. о., познать систему пол­ностью может лишь система более высокого порядка. Ми­нимум сложности описаний конструктивных объектов сданным числом элементов растет медленнее, чем любая вы­числимая функция (т.

о., есть громадные, но исключитель­но просто описываемые объекты, напр. 10'° ). Сложностьописания большинства объектов данной длины не намногониже, чем длина записи этих объектов. Т. о., возникает по­нятие содержательного случайного объекта, не описывае­мого кратко никакими алгоритмическими средствами.На основе теории сложности описания А. Н. Колмогоров,Л.

А. Левин, П. Мартин-Леф и другие развили алгорит­мическую теорию вероятностей. Основой данной теорииявилось содержательное определение случайной последо­вательности по Р. Мизесу. Двоичная последовательностьслучайна, если из нее нельзя выбрать никакую последова­тельность с другой частотой нулей и единиц. Напр., пос­ледовательность 0, 1, 0, 1...

неслучайна, поскольку после­довательность ее четных членов состоит из одних единиц.В классической математике такое определение пусто. А. Н.Колмогоров уточнил его, предложив рассматривать лишьалгоритмические перестановки подмножеств членов дан­ной последовательности.

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

Это — алгоритмическая основа софизма,примененного в аргументе Саймона (см. Парадокс логи­ческий). Заметим, что тезис Черча содержит одно важноеонтологическое предположение: о невозможности обоз­реть вечность. Поэтому в общей теории относительности(в частности, во вселенной Гёделя, в которой время мо­жет ходить по кругу) имеются миры, в которых, пролетаясквозь вращающуюся черную дыру, можно вычислить ал­горитмически невычислимую функцию. Класс функций,которые могут быть вычислены в таких Вселенных, назы­вается гиперарифметическим. Он неопределим в арифме­тике и определим лишь в анализе.Лит.: Клини С.

К. Введение в метаматематику. М., 1957; Барендрегт X. λ-исчисление. Его синтаксис и семантика. М., 1984;Марков Α. Α., Нагорный Н. М. Теория алгоритмов. М., 1984; Те­ория рекурсий. — В кн.: Справочная книга по математическойлогике. М., 1982; Успенский В. Α., Семенов А. Л. Теория алгорит­мов: основные открытия и приложения. М., 1987; Роджерс X.Теория рекурсивных функций и эффективная вычислимость.М., 1972; Непейвода Η.

Η. Прикладная логика. Ижевск, 1997.Η. Η. Непейвода78АЛЕКСАНДЕРАЛГОРИТМИЧЕСКИЙ ЯЗЫК — искусственная системаязыковых средств, обладающая выразительными возмож­ностями, достаточными для того, чтобы с ее помощьюможно было задать любое принадлежащее заранее очер­ченному классу детерминированное общепонятное пред­писание, выполнение которого ведет от варьирующихв определенных пределах исходных данных к искомомурезультату.

Такого рода предписания носят название ал­горитмов, откуда и сам термин «алгоритмический язык».В систематическое употребление он был введен в 1958Г. Боттенбрухом. Исторически понятие алгоритмическогоязыка сформировалось в 50-х гг. 20 в. в процессе станов­ления компьютерного программирования как самосто­ятельной научной дисциплины. Однако теоретическиеистоки этого понятия прослеживаются еще в работах 30-хгг. С. К. Клини, Э.

Л. Поста, А. М. Тьюринга и А. Черчапо уточнению общего математического понятия алгорит­ма. В настоящее время теория алгоритмических языков,а также проблематика, связанная с их разработкой и ис­пользованием, составляет один из важнейших разделовинформатики.В логико-лингвистическом и гносеологическом аспектеалгоритмические языки представляют собой одну из мо­делей императива (повелительного наклонения), и потомувыступают, с одной стороны, как средство фиксации опе­рационного знания, а с другой — как инструмент машин­ной, человеко-машинной или даже просто человеческойкоммуникации.

За короткий промежуток времени алго­ритмические языки превратились в новое познавательноесредство, органически вошедшее в научную и практичес­кую деятельность человека. Обычно к ним предъявляетсятребование «универсальности», заключающееся в том, чтодолжна иметься возможность моделирования с их помо­щью любых алгоритмов из числа тех, которые дают какоелибо уточнение общего понятия алгоритма (напр., машинТьюринга). Абсолютная точность синтаксиса алгоритми­ческого языка необходима не во всех случаях. Но в опре­деленных ситуациях (напр., когда тексты, записанные накаком-либо алгоритмическом языке, начинают выступатьв роли средства общения с компьютером) этот алгоритми­ческий язык должен быть оформлен в виде соответствую­щего формализованного языка с четко описанным синтак­сисом и точно заданной семантикой его грамматическихкатегорий. Центральное место в таких алгоритмическихязыках занимают тексты, называющиеся программами(собственно говоря, именно они и выражают понятиеалгоритма).

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

На ранней стадии программирования употреб­лялись «машинно-ориентированные» алгоритмическиеязыки т. н. языки «низкого уровня»), учитывавшие структу­ру или даже характеристики конкретных вычислительныхмашин (систему команд, особенности и структуру памятии т. п.). Потом им на смену пришли «проблемноориентированные» алгоритмические языки (языки «высокого уровня»),освободившие пользователя от необходимости ориентиро­ваться на машины определенного типа и тем самым придав­шие его усилиям гораздо большую математическую направ­ленность.

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

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

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