Мальцев А.И. Алгоритмы и рекурсивные функции

До начала XX столетия математика удовлетворялась интуитивным пред­став­ле­ни­ем алгоритма, ибо считалось, что любая корректно сфор­му­ли­ро­ван­ная ма­те­ма­ти­че­ская проблема должна иметь ре­ше­ние. Если это ре­ше­ние не найдено сейчас, то это только потому, что современное раз­ви­тие ма­те­матики не в состоянии спра­вить­ся с этой задачей. Со вре­ме­нем ме­тод ре­ше­ния обя­зательно будет найден. А по­лу­чен­ный метод все­г­да мож­но опи­сать так, чтобы он был понятен большинству.

Положение существенно изменилось в начале XX века, когда жизнь поставила пе­ред ма­те­ма­тик­ами такие задачи, существование ре­ше­ний ко­то­рых вызывало у мно­гих обоснованные сомнения. Доказать отсутствие правил, описывающих спо­соб решения означенных задач, можно только детерминировав само понятие ал­го­рит­ма — интуитивного представления о нем в данном контексте явно не­до­ста­точ­но. Полное математическое определение алгоритма стало на повестке дня математического сообщества одной из фун­да­мен­таль­ных проблем к моменту зарождения простейших средств вычислительной техники, т.е. к началу 30-х го­дов XX ст.

Начиная с 1935 года, был предположен ряд уточнений понятия алгоритма следующими категориями:

• Определение функции (Алонсо Чёрч, Стивен Клини)
• Общерекурсивные функции (Курт Гёдель, Стивен Клини, Жак Эрбран)
• Рекурсивные функции (Курт Гёдель, Стивен Клини)
• Машина Тьюринга (Алан Тьюринг, Эмиль Пост)
• Марковские алгоритмы (Андрей Марков-ст.)
• Графические схемы (Роза Петер)

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

К истории термина «алгоритм»

Алгоритмам и их свойствам посвящено боль­шое число фундаментальных работ, среди которых основной можно счи­тать работу Дональда Эрвина Кнута (Donald Ervin Knuth), в которой он пишет, что само слово «алгоритм» или, как рань­ше говорили — «алгорифм», представляет большой интерес.

«На пер­вый взгляд может показаться, что кто-то собирался написать слово «лога­рифм», но случайно поменял местами буквы. В словаре Webster’s New World Dictionary, вышедшем в 1957 г. этого слова еще не было. Там находим только устаревшую форму «algorism» — старинное слово, кото­рое оз­на­ча­ет «выполнение арифметических действий в помощью арабских цифр», — писал Кнут.

В средние века абакисты считали на аба­ках (счет­ных досках), а алгоритмики использовали algorism. В эпоху возрождения это слово ока­залось забытым. Одни лингвисты того времени пытались объяснить его значение сочетанием слов «algiros» (больной) и «arithmos» (число), другие не соглашались с таким толкованием и утверждали, что это слово проис­ходит от «King Algor Of Castile».

Наконец, историками математики было установлено истинное проис­хождение слова «algorism»: оно происходит от имени автора знаменитого персидского учебника по математике Абу Абд Аллах Мухаммед ибн Муса аль-Хо­рез­ми, что означает буквально «Отец Абдулы, Муххамед, сын Мус­сы, уроженец Хорезма». Аль-Хорезми на­пи­сал знаменитую «Книгу о вос­становлении и противопоставлении», которая определила еще одно слово: «алгебра».

Постепенно форма и значение слова «algorism» исказились. Как объяс­няется в словаре Oxford English Dictionary, это слово «претерпело мно­жество псевдоэтимологических искажений, включая последний вариант «algorithm», где произошла путаница с корнем слова греческого проис­хождения «arithmetic». Этот переход от «algorism» к «algorithm» кажется вполне закономерным ввиду того, что происхождение рассматриваемого слова было полностью забыто. В старинном немецком математическом сло­варе Vollständiges mathematisches Lexicon (Leipzig, 1747) дано следующее определение слова algorithmus: «Этот термин включает в себя понятие о четырех типах арифметических операций, а именно: о сложении, умножении, вычитании и делении». Латинское выражение algorithmus infinitesimalis в то время использовалось для определения «способов выполнения действий с бесконечно малыми величинами, открытыми Лейбницем (Leibniz)».

Дональд Кнут утверждает, что «современное значение слова «алго­ритм» во многом аналогично таким понятиям, как рецепт, процесс, метод, способ, процедура, программа. Но все-таки слово «algorithm» имеет допол­нительный смысловой оттенок. Алгоритм — это не просто последователь­ность выполнения операций для решения задачи определенного типа».

Алгоритмы и рекурсивные функции

Существенный вклад в теорию алгоритмов уже в наше время внес советский математик Анатолий Иванович Мальцев. Его книга «Алгоритмы и рекурсивные функции» (1965) стала настольной для прикладных математиков, раскрывая природу и сущность алгоритмизации. О том, что она сразу стала библиографической редкостью говорить не приходится. К счастью, монография была переиздана в 1986 г. Ее стоит прочесть тем, кто хочет честно посмотреть в глаза искусственному интеллекту компьютеров.

А.И. Мальцев констатирует интуитивность понятия алгоритма, которое «хотя и нестрогое, но настолько ясное, что практически не было серьезных случаев, когда математики разошлись бы во мнениях относи­тельно того, является ли алгоритмом тот или иной конкретно заданный процесс». Однако, положение изменилось в XX веке, выдвинувшем на первый план такие алгоритмические проблемы, существо­вание положительного решения которых было сомнительным. Действи­тельно, одно дело — доказать существование алгоритма, другое — дока­зать отсутствие алгоритма. Первое можно сделать путем фактического описания процесса, решающего задачу; в этом случае достаточно и интуи­тивного понятия алгоритма, чтобы удостовериться в том, что описанный процесс и есть алгоритм. Доказать несуществование алгоритма таким путем невозможно. Для этого нужно точно знать, что такое алгоритм. В 20-х годах XX века задача точного определения понятия алгоритма стала одной из центральных математических проблем. Решение ее было получено в середине 30-х годов того же века в работах Гильберта, Геделя, Черча, Клини, Поста и Тьюринга в двух форматах. Первое решение было основано на понятии рекурсивной функции, второе — на описании точно очерченного класса процессов.

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

Torrent

• Мальцев А.И. // Алгоритмы и рекурсивные функции, 1-е изд. — Москва: «Наука», 1965 — 394 с.
• Мальцев А.И. // Алгоритмы и рекурсивные функции, 2-е изд. — Москва: «Наука», 1986 — 368 с.

Список литературы

1. Мальцев А.И. Алгоритмы и рекурсивные функции. — М.: «Наука», 1986. — 367 с.
2. Кнут Д.Э. Искусство программирования. Т. 1. Основные алгоритмы / Пер.с агл.: уч. пос., 3-е изд., под общей ред. докт. физ.-мат. наук, проф. Ю.В. Козаченко. — М.: Изд. дом «Вильямс», 2000. — 720 с.
3. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и ана­лиз. 2-е изд. — М.: «Вильямс», 2005. — 1290 с.
4. Алферова З.В. Теория алгоритмов. — М. : Статистика, 1973. — 164 с.
5. Subramaniam V. Programming Scala. Tackle Multicore Complexity on Java Virtual Ma­chine. The Progmatic Programmers. — Pragmatic Bookshelf. — Raleigh, North Carolina, Dallas, Texas, 2008. — 218 p.
6. Пирс Б. Типы в языках программирования / Пер. с англ. —М.: «Лямбда пресс» & «Добросвет», 2012. — 655 с.
7. Foundational Theories of Classical and Constructive Mathematics. Ed. Giovanni Somma- ruga. — Springer: The Western Ontario Series in Philosophy of Science, 2011. — 316 p.
8. Маклейн С. Категории для работающего математика.—М.: ФИЗМАТЛИТ, 2004.— 352 с.
9. Лафоре Р. Структуры данных и алгоритмы в Java //Классика Computer Science.— М. : Изд-во «Питер», 2013. — 704 с.
10. Гильберт Д., Бернайс П.Основания математики. Логические исчиления и формали­зация арифметики. — М. : «Наука», 1982. — 550 с.
11. Godel K. Uber formal unentscheidbare Siitze der Principia Mathematica und verwandter SystemeI//Monatsheftefurmathematikundphysik.— 1931. — Т. 38, № 1. — С. 173—198.
12. Барендрегт АП.Ламбда-исчисление. Его синтаксис и семантика. — М. : Мир, 1985. —606 с.
13. Kleene S.C. General recursive functions of natural numberse // Mathematische Annalen.— 1936. — 112. — P. 727—742.
14. Успенский В.А. Машина Поста. — М.: Наука, 1979. — C. 89—95.
15. Turing A. On computable numbers, with an application to the Entscheidungs problem // Proc. of the London Mathematical Society. Series 2. — 1936-7. — 42. — P. 230—265.
16. Хорстман К. Scala для нетерпеливых /Пер. с англ.—M.: Изд-во «ДМК», 2013.— 407 с.
17. Марков А.А. Теория алгорифмов // Тр. Математич. ин-та им. В.А. Стеклова. Т. 42. — М.: МАИК «Наука/Интерпериодика», 1954. — 376 с.
18. Седжвик Р., Уэйн К. Алгоритмы на Java, 4-е изд. — М.: «И.Д. Вильямс», 2013. — 848 с.
19. Рублев В.С. Основы теории алгоримов.— Ярославль: Ярославский гос. ун-т им. П.Е. Де­мидова, 2005. — 143 с.
20. Н.А. Kravtsov, I.A. Prytulyuk A NEW ALGORITHM CLASSIFICATION The author’s classification of algorithms based on the review of famous fundamental and modern works is presented. The author’s classification is different from already known ones due to the in­volved terms of high order algorithms and context-related algorithms.

Другие источники

1. Maltsev, A. (1986), Algoritmy i rekursivnyie funktsii [Algorithms and recursive functions], Nauka, Moscow, Russia.
2. Knut, D. (1968), Iskustvo programmirovaniya. Toml. Osnovnyie algoritmy [The Art of Computer Programming. Vol. 1. Fundamental Algorithms], Manual, Third Edition, trans­lated from English by Prof. Kozachenko, Yu.V., Williams, Moscow, Russia.
3. Cormen, T.H., Leizerson, Ch.I., Rivest, R.L. and Shtain, K. (1990), Algoritmy:postroyeniye i analiz [Algorithms: structure and analysis], Williams, Moscow, Russia.
4. Alferova, Z.V. (1973), Teoriya algoritmov [Algorithmtheory], Statistika, Moscow, Russia.
5. Subramaniam, V. (2008), Programming Scala. Tackle multicore complexity on Java virtual machine. The pragmatic programmers, Pragmatic bookshelf, Raleigh, North Carolina, Dal­las, Texas, USA.
6. Pirs, B. (2012), Tipy v yazykakh programmirovaniya [Types in programming languages], Lambda Press and Dobrosvet, Moscow, Russia.
7. Foundational theories of classical and constructive mathematics (2011), Ed. by Giovanni Sommaruga, Springer: The Western Ontario Series in Philosophy of Science, Canada.
8. Makleyn, S. (1998), Kategorii dlya rabotayushchego matematika [Categories for the work­ing mathematician], Translated from English, Fizmatlit, Moscow, Russia.
9. Lafore, R. (2002), Struktury dannykh i algoritmy v Java [Data structures and algorithms in Java], Piter, Moscow, Russia.
10. Gilbert, D. andBernays, P. (1982), Osnovaniya matematiki. Logicheskie ischileniya iforma- lizatsiya arifmetiki [Mathematics bases. Logical calculus and arithmetic formalization], Nauka, Moscow, Russia.
11. Gödel, K. (1931), Uber formal unentscheidbare Siitze der Principia Mathematica und ver­wandter Systeme I, Monatshefte fUr mathematik und physic, Vol. 38, no. 1, pp. 173-198.
12. Barendregt, H.P. (1985), Lambda-ischislenie. Yego sintaksis i semantika [The Lambda cal­culus. Its syntax and semantics], Translated from English, Mir, Moscow, Russia.
13. Kleene, S.C. (1936), General recursive functions of natural numbers, Mathematische Anna­len, Vol. 112, pp. 727-742.
14. Uspenskiy, V. (1979), Mashina Posta [Post-Turing machine], Nauka, Moscow, Russia.
15. Turing, A. (1936), On computable numbers, with an application to the Entscheidungs prob­lem, Proc. of the London Mathematical Society, Series 2, Vol. 42, pp. 230-265, available at: http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf ( accessed August 2015).
16. Khorstman, С. (2012), Skala dlya neterpelivykh [Scala for the impatient], translated from English, DMK, Moscow, Russia.
17. Markov, A. (1954), “Algorithm theory”, Trudyi matematich. in-ta im. V. A. Steklova, Vol. 42, MAIK «Nauka/Interperiodika», Moscow, Russia.
18. Sedzhvik, R. andUeyn, K. (2011), Algoritmy naJava [Algorithms in Java], Williams, Mos­cow, Russia.
19. Rublev, V. (2005), Osnovyi teorii algorimov [Fundamentals of algorithm theory], P.G. De­midov Yaroslavl State University, Yaroslavl, Russia.
20. The Yoda of Silicon Valley // The New York Times