Россия (СССР)
Русский математик и логик, основатель школы т.н. конструктивной математики; сын математика А.А. Маркова.
А.А. Марков уточнил понятие нормального алгорифма.
«В начале 1950-х годов в работах А.А. Маркова (первые публикации которого по теории алгоритмов относятся ко второй половине 1940-х годов) получила развитие та идея, что все математические алгоритмы можно свести к повторению однотипных элементарных операций, выполняемых в строгом соответствии с чётко зафиксированным предписанием, которое после очень простого объяснения на естественном языке или даже демонстрации на примерах становится понятным каждому.
В 1951 г. в «Трудах Математического института АН СССР» (т. XXXVIII) была помещена статья А.А. Маркова «Теория алгорифмов», излагающая новую концепцию, а в 1954 г. вышла его большая монография. Ныне она, как и работы Чёрча и Тьюринга, принадлежит к логической классике».
Бирюков Б.В., Тростников В.Н., Жар холодных чисел и пафос бесстрастной логики. Формализация мышления от античных времен до эпохи кибернетики, М., «Едиториал УРСС», 2004 г., с.147-148.
«… из доказанной в математической логике теоремы о возможности осуществления любого рекурсивного процесса на некоторой машине Тьюринга вытекает, что с помощью алгорифмов Маркова осуществимо всё, что осуществимо путём применения аппарата рекурсивных функций. Но не предусматривают ли марковские алгорифмы возможности более широкого круга процедур? Ведь алфавиты и списки формул подстановок могут быть чрезвычайно разнообразны.
Вскоре после создания Марковым своей теории, в 1953 г., была опубликована теорема, доказанная его учеником В. К. Детловсом, согласно которой всякий процесс, реализуемый с помощью нормального алгорифма, реализуем и посредством некоторой рекурсивной функции.
Это значит, что рекурсивные функции и машины Тьюринга «равнообъёмны» нормальным алгорифмам и что тезисы Чёрча и Тьюринга получают подкрепление в виде принципа, названного А. А. Марковым принципом нормализации (его естественно также называть тезисом Маркова): всякое точное общепонятное предписание, определяющее произвольный потенциально осуществимый процесс переработки слов в каком-либо алфавите, ведущий от варьируемых исходных данных к некоторому результату, может быть представлено в виде некоего нормального алгорифма.
Общность и значимость этого принципа становятся ясными, как только мы примем во внимание, что любой вычислительный процесс, более того, всякий иной жестко детерминированный процесс, протекающий в переменной, но однотипной среде, можно трактовать как переработку слов в опреде-ленном алфавите.
Подобно тому как это сделал А. Чёрч в статье 1936 г., А.А. Марков приводит ряд аргументов в пользу своего тезиса. Как и у Чёрча, это не доказательство, а только соображения, к которым можно отнести эпитет «убедительные».
Они опираются прежде всего на живую практику математики. Исследования Маркова, позволившие ему выдвинуть разумные основания в пользу принципа нормализации, следует считать важной вехой в становлении основной гипотезы теории алгоритмов (теории эффективной вычислимости) - гипотезы, общий смысл которой состоит в утверждении, что различные оказавшиеся эквивалентными друг другу уточнения идеи алгоритма и вычислимости - рекурсивные функции, машины Тьюринга, нормальные алгорифмы - исчерпывающим образом описывают (каждое в терминах своего специфического языка) эту идею.
Познавательный статус данной гипотезы делает её похожей на закон сохранения энергии.
Обосновать его так, как математики доказывают теоремы, невозможно. Но этот закон - положение, подтверждаемое научными аргументами, идущими с самых различных сторон. […]
Так к началу 1950-х годов, то есть к моменту выхода на сцену ЭВМ, как итог развития логики и оснований математики и как непосредственный результат исследований Гёделя, Чёрча, Тьюринга, Маркова и других пионеров теории эффективной вычислимости, стал вырисовываться обширный круг процессов, обладающих следующими свойствами.
1. Они в принципе строго детерминированы, то есть каждый предыдущий этап (этапы) полностью определяют последующий.
2. Они потенциально осуществимы - в том смысле, что при достаточно долгом протекании без внешних помех приводят (точнее, могут приводить) к фактическому результату.
3. Они имеют атомарное строение - складываются из совокупности элементарных операций, которых имеется всего несколько видов и которые столь просты и наглядны, что их нетрудно объяснить любому человеку.
4. Они заключаются в переработке объектов, чётко различаемых и опознаваемых и - в силу этого - легко доступных для человеческих восприятия, запоминания и мышления».
Бирюков Б.В., Тростников В.Н., Жар холодных числе и пафос бесстрастной логики, М., «Едиториал УРСС», 2004 г., с.150 и 151.
Регистрация на конференц
Страница конференции во ВКонтакте: 
