markov_teorija_algorifmov (Марков - Теория алгоритмов), страница 2

А.Марковым важнейший частный случай задачи о точечном электроде в слоистой среде.) 'ч)См. Ю.В.Линнии и Н,А.Шаннн111. чее) По образованиюА. А. Мариов — физик. В 1924 г, он окончил фнзичесиое отделение физнио-математичесиого факультета Лениградского университета, после чего непродолжительное время работал в Государственном физико-техническом институте. С 1925 по 1928 г. он был аспирантом, а затем до 1985 г.— научным сотрудником Астрономического института, ПРЕДИСЛОВИЕ построения математики, его стремление строить математику конструктивно.

Нелегко в немногих словах объяснить и то, каким образом при тщательно подчеркиваемой неспешности, обстоятельности, выглядевшей иногда почти медлительностью„при его манере все делать самому, не прибегая к посторонней помощи даже в мелочах, А, А. Маркову удалось оставить такое огромное научное наследие.

Непросто рассказать и об истоках тех эстетических и стилистических норм, которых А. А.Марков придерживался в своих работах и соблюдения которых он требовал и от своих учеников, Было бы интересно — хотя и непросто — рассказать о необычной манере поведения А. А. Маркова, о его наблюдательности, тонком остроумии, о его неожиданных, порой парадоксальных, но неизменно метких и точных суждениях, которые часто бывали облечены в острую, незабываемую по своей артистичности форму. Сын великого русского математика академика Андрея Андреевича Маркова (1856 — 1922) А.

А. Марков-младший по своему рождению принадлежал к высшему слою российской интеллигенции, давшей нашей стране многих замечательных людей. Лучшие традиции этой среды — вера в высокую миссию культуры, самоотверженная любовь к науке, четкость моральных принципов, ясная иерархия жизненных ценностей— нашли отчетливое выражение в характере и даже во внешнем облике А. А. Маркова, удивительно благородного, стойкого и в высшем смысле слова демократичного, каким его знали и любили его ученики и все, кто был к нему в той или иной мере близок. Более полный рассказ об А.

А. Маркове требует того, что. бы к нему обратиться отдельно, и потому он должен быть отложен на будущее. Наилучший же доступный мне в настоящее время способ почтить память моего учителя состоит в том, чтобы постараться с наиболыпей тщательностью довести до конца начатый им труд. Одним из самых существенных факторов, определяющих значение математики и место ее в современной науке, является точность и высокая степень универсальности изобразительных средств, которыми она располагает, Эти средства позволяют стРоить уточненные модели самых разнообразных по своей пРиРоде фундаментальных научных понятий, в том числе и математических. Такие модели, будучи однажды построены, ПРЕДИСЛОВИЕ затем становятся доступными рассмотрению с помощью точных средств, и в изучении описываемых ими понятий, как правило, наступает заметный прогресс.

Разработка такого рода уточненной модели была произведена во второй половине 30-х годов нашего столетия и для одного из важнейших и употребительнейших понятий математики — а теперь и не только ее одной — понятия «алгорифма» '). В математическом обиходе под алгорифмом принято понимать «точное предписание, определяющее вычислительный процесс, ведущий от варьируемых исходных данных к искомому результату» (А.

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

Алгорифмами являются также известные еще из начальной школы правила арифметических действий над целыми числами, записанными в десятичной системе. Читатель сам вспомнит другие встречавшиеся в его практике примеры '"). Используя понятие алгорифма, математика до определенного времени может довольствоваться несколько расплывчатой, неуточненной формулировкой этого понятия, подобной той, которая была приведена выше.

Во всяком случае, так дело может обстоять до тех пор, пока речь будет идти о построении конкретных алгорифмов для решения таких-то и таких-то конкретных задач. Но как только мы„придя к предположению о возможной неразрешимости какой-либо интересующей нас алгорифмической проблемы в**), начнем пытаться доказывать, *) В сходном смысле в мзземзтине уцотреблиютси также термины ««редин«знее», «метод», «способ» и т. п.

Многие авторы пользуются ознз~зющим то же самое понятие словом «ачгоритм». *') Ииогдз, впрочем, в литературе и ззгорифмзм отнссит (чзще всего просто во иедорззуменню) и такие вычислительные реиомендзпии, которые ирн ближзйшем рассмотрении злгорифмзми не оказываются. Типичным примером может служить знзменитый «метед деления отрезка пополам», обычно применяемый в доказательстве теоремы Коши о нуле знзиопеременной непрерывной функции.

Причины, по которым этот мезод злгорифмом считзтьси не может, излагаются нами в б 64, Тем ие менее он все-твин имеет некоторое злгорифмичесное содержание, которое и выясняется изми вй 66ДЕ '««) ! )ерззрсшимыми, кзи мы теперь знаем, оказались такие знамени. зые злгорифмичесиие проблемы, кзи проблема рвзрешимостн дни исчислении вреди«итон, проблема тождества дли иолугруцп и дви групп, проблема гомеоморфии полиэдров, )О-и нробземз Гильбертз. Гипотеза о иерззре- ПРЕДИСЛОВИЕ ПРЕДИСЛОВИЕ )О что она действительно имеет место, мы в общем случае сразу же столкнемся с необходимостью уточнения понятия алгорифма, его стандартизации.

В самом деле, чтобы иметь возможность доказывать несуществование алгорифма, решающего задачу, для решения которой алгорифм а рг[ог! мог бы существовать "), мы должны точно уяснить себе тип объекта, предположение о существовании которого будет опровергаться. Попытка осознания этой ситуации, с одной стороны, и широкие исследования в области оснований математики и математической логики — с другой, привели к тому, что к середине 39-х годов проблема уточнения общего понятия алгорифма стала „носиться в воздухе" и в 1936 г.

были практически одновременно (и независимо друг от друга) опубликованы работы А. Ч е р ч а [1), С. К. К л и н и! 1) **), А. М. Т ь ю р и н г а [1) и Э. Л. П о с т а [1), в которых эта проблема была решена. В техническом отношении полученные решения были различными: Х-конверсии Черча, рекурсивные фуякции Эрбрана— Геделя — Клини и машины Тьюринга ***) внешне не походили друг на друга. Но вскоре была установлена взаимная моделируемость этих понятий, и А.

Черчем было высказано и обосновано положение о том, что найденное уточнение является адекватным, т. е. что оно правильно отражает сущность понятия эффективной вычислимости. Впоследствии это положение было С. К. Клиии названо — в честь его автора — «тезисом Черча» ***"). От этого момента и можно отсчитывать возраст теории алгорнфмов как точной математической дисциплины. Произведенное уточнение дало немедленный эффект: уже в том же 1936 г. А.

Ч е р ч е м [2! была доказана неразрешимость знаменитой Вп[зс)зе)г)цпйзргоЫеш — проблемы разре- шимости данной конкретной алгорифмичссхой проблсмм может возникнуть в результате систематических неудач при настойчивых попытках иайхм решающий ес алгорифм, что в перечисленных случаях и имело место фаитичесхи. Однако иногда ее иеразрсшимость мажет быть прсдусадава па осиове общих соображений (см., например, й б4.1).

е) Тем самым мы подчеркиваем, что речь идет ие о задачах типа «построить алгорифм, который по любым трем точкам иа плоскости указывал бы проходящую через иих прямую». Неразрешимость такого рода задач, конечно, может быть установлена и без уточиеиия понятия алгорифма. В приведенном примере оиа вытекает из существования трех точек, ие лежащих иа одиой прямой. ее) Клиии осиовывался при этом иа более раииих идеях Ж.