Марков Андрей Андреевич (младший)

1903 год
-
1979 год

Россия (СССР)

Русский математик и логик, основатель школы т.н. конструктивной математики; сын математика А.А. Маркова.

А.А. Марков уточнил понятие нормального алгорифма.

«В начале 1950-х годов в работах А.А. Маркова (первые публикации которого по теории алгоритмов относятся ко второй половине 1940-х годов) получила развитие та идея, что все математические алгоритмы можно свести к повторению однотипных элементарных операций, выполняемых в строгом соответствии с чётко зафиксированным предписанием, которое после очень простого объяснения на естественном языке или даже демонстрации на примерах становится понятным каждому.
В 1951 г. в «Трудах Математического института АН СССР» (т. XXXVIII) была помещена статья А.А. Маркова «Теория алгорифмов», излагающая новую концепцию, а в 1954 г. вышла его большая монография. Ныне она, как и работы Чёрча и Тьюринга, принадлежит к логической классике».

Бирюков Б.В., Тростников В.Н., Жар холодных чисел и пафос бесстрастной логики. Формализация мышления от античных времен до эпохи кибернетики,  М., «Едиториал УРСС», 2004 г., с.147-148.


«… из доказанной в математической логике теоремы о возможности осуществления любого рекурсивного процесса на некоторой машине Тьюринга вытекает, что с помощью алгорифмов Маркова осуществимо всё, что осуществимо путём применения аппарата рекурсивных функций. Но не предусматривают ли марковские алгорифмы возможности более широкого круга процедур? Ведь алфавиты и списки формул подстановок могут быть чрезвычайно разнообразны.

Вскоре после создания Марковым своей теории, в 1953 г., была опубликована теорема, доказанная его учеником В. К. Детловсом, согласно которой всякий процесс, реализуемый с помощью нормального алгорифма, реализуем и посредством некоторой рекурсивной функции.

Это значит, что рекурсивные функции и машины Тьюринга «равнообъёмны» нормальным алгорифмам и что тезисы Чёрча и Тьюринга получают подкрепление в виде принципа, названного А. А. Марковым принципом нормализации (его естественно также называть тезисом Маркова): всякое точное общепонятное предписание, определяющее произвольный потенциально осуществимый процесс переработки слов в каком-либо алфавите, ведущий от варьируемых исходных данных к некоторому результату, может быть представлено в виде некоего нормального алгорифма.

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

Подобно тому как это сделал А. Чёрч в статье 1936 г., А.А. Марков приводит ряд аргументов в пользу своего тезиса. Как и у Чёрча, это не доказательство, а только соображения, к которым можно отнести эпитет «убедительные».

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

Познавательный статус данной гипотезы делает её похожей на закон сохранения энергии.

Обосновать его так, как математики доказывают теоремы, невозможно. Но этот закон - положение, подтверждаемое научными аргументами, идущими с самых различных сторон. […]

Так к началу 1950-х годов, то есть к моменту выхода на сцену ЭВМ, как итог развития логики и оснований математики и как непосредственный результат исследований Гёделя, Чёрча, Тьюринга, Маркова и других пионеров теории эффективной вычислимости, стал вырисовываться обширный круг процессов, обладающих следующими свойствами.

1. Они в принципе строго детерминированы, то есть каждый предыдущий этап (этапы) полностью определяют последующий.

2. Они потенциально осуществимы - в том смысле, что при достаточно долгом протекании без внешних помех приводят (точнее, могут приводить) к фактическому результату.

3. Они имеют атомарное строение - складываются из совокупности элементарных операций, которых имеется всего несколько видов и которые столь просты и наглядны, что их нетрудно объяснить любому человеку.

4. Они заключаются в переработке объектов, чётко различаемых и опознаваемых и - в силу этого - легко доступных для человеческих восприятия, запоминания и мышления».

Бирюков Б.В., Тростников В.Н., Жар холодных числе и пафос бесстрастной логики, М., «Едиториал УРСС», 2004 г., с.150 и 151.

 

Новости
Случайная цитата
  • Трудный балетный класс – выбор М.М. Плисецкой
    «Много лет она занималась в классе у Асафа Мессерера (он приходился ей дядей – Прим. И.Л. Викентьева). Это мужской класс, единственная женщина - Майя. Она стояла у палки в самом центре, слева и справа от неё премьеры - Васильев и Лавровский.Мессерер давал комбинации упражнений, но замечания делал крайне редко. «Если он будет каждого поправлять, то мы будем заниматься до глубокой ночи, - говорила Майя. - Хочешь хорошо танцевать - делай то, что предлагает Асаф. Так же - если хочешь хорошо играть Г...