Article
Algorithms in the Homeland of
Al-Khorezmi
“Algorithm in Modern
Mathematics and its Applications” is
the
mail
topic of an international symposium of
mathematicians that
took place in the homeland of the
great Uzbek mathematician and
astronomer of IX century Mohammed
al-Khorezmi. Yesterday the
international meeting where for
several day scientists have been
discussing a problem of
mathematical programs building finished
its
work.
“Pravda”, September 23, 1979
The notion of “algorithm” has
long become familiar not only to
mathematicians: it is a conceptual
basis of various information processing
processes; the availability of proper
algorithms makes it
possible to automate such processes.
However it is not always clearly
realized that the word algorithm
itself is a derivative of the name of
a geographic site, namely the word Khorezm.
The term “algorithm” owes its origin
to the great
Uzbek scientist of IX century whose full
name is Abu Abdullah (or Abu
Djafar) Mohammed ibn
Musah al-Khorezmi (where
al-Khorezmi means “citizen of
Khorezm). Latin versifications of Al-
Khorizmi’s arithmetic treatise
wrote in Arabic was for the medieval
Europe the introduction to
Indian positional number system and the
skill of calculation in this system.
In Latin titles of XII
century versifications of Al-Khorezmi
works his name was transcribed as alchorismi
or algorismi,
and the Latin translation of the same
period of his arithmetic treatise
started with a phrase Dixit
algorismi, i.e. “Al-Khorezmi said”.
This originated the word algorithm –
first as a designation of
our decimal positional arithmetic and
digital calculation algorithms (i.e. the
first arithmetic
procedures dealing with symbols: because
before those times calculations were
made with the help
of abacus – a counting frame) and
later as a reference to any algorithm.
The first chapter of a multi-
volume monograph “The art of computer
programming” by eminent American
specialist in
programming Donald E. Knuth starts as
follows: “The notion of algorithm is
basic to all of computer
programming, so we should begin with a
careful analysis of this concept. The
word ”algorithm”
itself is quite interesting…it comes
from the name of a famous Persian
textbook author, Abu Ja’far
Mohammed ibn Musa al-Khowarizmi (c. 825)
– literally, “Father of Ja’far,
Mohammed, son of
Moses, native of Khowarizm”. Today
Khowarizm is a small Soviet town Khiva.”
It is appropriate to
make two comments on this citation:1)
the customary Russian name for
“Khowarizm” is Khorezm;
2) Khiva is not Khorezm (Khowarizm), but
a town of Khorezm region of Uzbek SSR (from
1920 to
1923 – the capital of Khorezm
People’s Soviet Republic, and from
1923 to 1924 – the capital of
Khorezm Soviet Socialist Republic). The
Uzbek Khorezm region of today (with the
capital in
Urgench city) is a natural successor of
ancient Khorezm oasis, famous center of
civilization that
enriched the mankind with a whole galaxy
of remarkable philosophers, scientists
and poets (Biruni
and Avicenna among them). It is why the
idea arose to make a kind of scientific
pilgrimage of
mathematicians to Khorezm, al-Khorezmi
homeland. Symposium conduction was also
supposed,
but not just another “usual”
symposium with talks prepared in advance,
but an exchange of opinions
on fundamental problems of mathematics
and computer science. Desert nature and
breath of ancient
history distinguishing the conference
site were supposed to give the
participants a chance to distract
themselves from everyday work, to help
them to focus their thoughts and to
impart more
philosophical profundity and perspective
to their meditation.
An important and difficult task
of conducting in Urgench an
international symposium “Algorithms
in modern mathematics and its
applications” dedicated to al-Khorezmi
was shouldered by Uzbek
SSR Academy of Science with the
assistance of the USSR Academy of
Science and first of all – its
Siberian Branch, in collaboration with
Khorezm regional governing body.
Direct organization and
management of the symposium was effected
by a corresponding member of
the USSR AS, Informatics Department Head
of the SBAS Computing Center A.P. Ershov
(Novosibirsk) and Turing Prize winner,
member of the USA National Academy of
Sciences,
professor of the Stanford University
Computer Science Department D.E. Knuth (Stanford).
Among
those who visited Urgench to take part
in the symposium there also were
vice-president of the
UzSSR AS S.Kh. Sirazhdinov (Tashkent)
who headed the symposium organizing
committee, IFIP
honorary member and ex-president,
professor H. Zemanek (Vienna), general
director of UzSSR AS
Scientific-Iindustrial Corporation “Kibernetika”,
full member of Uzbek Academy of Sciences
V.K.
Kabulov (Tashkent), senior research
fellow of the same corporation, Ph.D. in
physics and
mathematics A.V. Kabulov (Tashkent),
Section Head of the Institute of
Cybernetics of the same
corporation, Ph.D. in engineering K.Sh.
Babamuradov (Tashkent), member of Royal
Dutch
Academy if Sciences, director of
Mathematical Center A. van Wijngaarden (Amsterdam),
member
of the USA National Academy of Sciences,
professor of Wisconsin State University
S.K. Kleene
(Madison), Department Head of the SBAS
Institute of Mathematics, a
corresponding member of the
USSR AS Yu.L. Ershov (Novosibirsk),
senior research fellow of the same
institute, professor
B.A. Trakhtenbrot (Novosibirsk),
director of the USSR AS Institute of
Astronomy, a corresponding
member of the USSR AS, Lenin Prize
winner S.S. Lavrov (Leningrad),
Academician-secretary of
the UzSSR AS Department of Mechanics and
Control Processes, a corresponding
member of the
UzSSR AS T.R. Rashidov (Tashkent),
deputy department chief of Ukrainian AS
Institute of
Cybernetics, USSR State Award laureate,
professor J.V. Kapitonova (Kiev), senior
research fellow
of the same institute, USSR State Award
laureate, doctor of physical and
mathematical sciences
A.A. Letichevski (Kiev), Dr. H. Kaufman
(Munich), senior research fellows of the
USSR AS
Mathematical Institute Lenin Prize
winner, professor Y.I. Manin,(Moscow),
professor N.A. Shanin
(Leningrad), doctor of physical and
mathematical sciences Y.V. Matiasevich (Leningrad),
and Ph.D.
in physics and mathematics A.O. Slisenko
(Leningrad), director of
the Institute of Informatics
Foundations of Polish Academy of
Sciences professor Z. Pawlak (Warsaw),
research fellow of the
same institute, professor A.
Mazurkiewicz (Warsaw), ex-president of
the European Association for
Theoretical Programming, Warwick
University professor M.S. Paterson (Coventry),
heads of
laboratories of the USSR AS Computing
Center professor O.S. Ryzhov (Moscow)
and Ph.D. in
physics and mathematics V.M. Kurochkin (Moscow),
senior research fellow of the same
Center,
Ph.D. in physics and mathematics N.M.
Nagorny (Moscow), Sector Head of
Estonian AS Institute
of Cybernetics, professor E.H. Tyugu (Tallinn),
Moscow University professor V.A.
Uspensky
(Moscow), junior member of teaching of
the same university, Ph.D. in physics
and mathematics
A.L. Semenov (Moscow), professor of
Swiss Federal Center of Technology E.
Specker (Zurich),
Zurich University professor V. Strassen
(Zurich), senior research fellow of the
All-Union scientific
and research Institute of Systemic
Research of the USSR AS and USSR State
Committee for
Science and Technology doctor of
engineering G.M. Adelson-Velsky (Moscow),
Department Head
of the Latvian University Computing
Center, doctor of physical and
mathematical sciences
Y.M. Barzdyn (Riga), dean of the Applied
Mathematics Department of Tashkent
University, doctor
of physical and mathematical sciences
G.N. Salikhov (Tashkent), laboratory
head of the Leningrad
University Research Institute of
Mechanics and Mathematics, doctor of
physical and mathematical
sciences G.S. Tseitin (Leningrad),
deputy director of the SBAS Computing
Center, Ph.D. in physics
and mathematics V.E. Kotov (Novosibirsk),
assistant professor of Udmurt University
N.N.
Nepeivoda (Izhevsk), research fellow of
the Institute of Mathematics of
Bulgarian Academy of
Sciences, Ph.D. in physics and
mathematics A.O. Buda (Sofia), and
others. The USSR AS full
member, director of the UkrSSR AS,
Laureate of Lenin and USSR State Awards
V.M. Glushkov
(Kiev), and member of Bavarian Academy
of Sciences F.L. Bauer (Munich) sent
their papers.
September 16, 1979 in one of
central public gardens of Urgench, in
presence of symposium
participants and local community
representatives the foundation of a
monument to al-Khorezmi was
laid. Chairman of Urgench city executive
committee B. Kurbanbaev and professor
Heinz Zemanek,
the most prominent researcher of the
life and works of al-Khorezmi, made
speeches at the meeting.
On the same day a grand opening of the
International Symposium took place in
the great conference
hall of the House of Soviets.
Vice-president of Uzbek SSR Academy of
Sciences, academician
S.Kh. Sirazhdinov, delivered the opening
speech at the symposium. Also speaking
at the opening
session were chairman of regional
executive committee R. Ishchanov,
professor H. Zemanek,
corresponding member of the USSR AS A.P.
Ershov, member of the USA National
Academy of
Sciences D.E. Knuth, full member of
Uzbek Academy of Sciences V.K. Kabulov.
The working session of the
symposium continued for four days:
September 17, 18, 21, 22, two
sessions a day. Symposium program,
extremely rich and intense, deserves to
be fully cited below.
Monday, September 17, morning
session
A.P. Ershov, Chairman
8.30 – 9.50
H. Zemanek. Al-Khorezmi has said.
Part 1. The background and the
personality of Al-Khorezmi.
9.50 – 10.30
S.Kh. Sirazhdinov. On Euler
numbers and Euler polynomial roots.
11.00 – 12.30
D.E. Knuth Algorithm in modern
mathematics and computer science.
Monday, September 17, afternoon
session
D.E. Knuth, Chairman
15.30 – 17.00
V.A. Uspensky and A.L. Semenov.
What does the theory of algorithms give?
(Major discoveries in the theory of
algorithms for the last half of a
century).
17.30 – 18.30
J.M. Barzdin. On inductive
synthesis of algorithms.
Tuesday, September 18, morning
session
S.C. Kleene, Chairman
8.00 – 9.00
H.Zemanek. Al-Khorezmi has said.
Part II. The works and the influence of
Al-Khorezmi.
9.00 – 10.00
Yu.I. Manin. Algorithm as a
mathematical model.
10.30 – 12.00
A. van Wijngaarden. Languageless
programming.
Tuesday, September 18, afternoon
session
S.S. Lavrov, Chairman
16.00 – 16.45
N.N. Nepeivoda. An outline of the
mathematical theory of program synthesis.
16.45 – 17.30
E.H. Tyugu. The structured
synthesis of programs.
18.00 – 18.30
A. Kreczmar. From schemata theory
to algorithmic and dynamic logic.
18.30 – 19.00
A.A. Letichevsky. On the search
for invariant relations in programs.
19.00 – 19.30
A. Mazurkiewicz. On concurrent
algorithms.
A general discussion on “How to
write a program of a million
instructions” took place during the
break between morning and afternoon
sessions on September 18.
Friday, September 21, morning
session
M.S. Paterson, Chairman
10.00 – 11.00
B.A. Trakhtenbrot. Some
reflections on the connection between
computer science and the theory of
algorithms.
11.00 – 12.00
G.M. Adelson-Velsky and A.O.
Slisenko. What can be done with problems
in exhaustive searches?
12.30 – 13.15
Yu.V. Kapitonova. On goodness and
badness of putting combinatorial
processes on a computer.
13.15 – 14.00
V. Strassen. Algorithms for
algebras.
Friday, September 21, afternoon
session
V.A. Uspensky, Chairman
16.30 – 17.15
S.C. Kleene. Algorithms in
various contexts.
17.15 – 18.00
N.A. Shanin. The role of
algorithm in the semantics of
arithmetical languages.
18.30 – 19.15
Yu.L. Ershov. How algebra helps
to solve problems in the theory of
algorithms.
19.15 – 20.00
G.S. Tseytin. From logicism to
proceduralism (an autobiographical
account).
Saturday, September 22, morning
session
S.Kh. Sirazhdinov, Chairman
8.00 – 9.00
F.L. Bauer Algorithms and algebra
(presented by D.E. Knuth)
9.00 – 10.00
M.S. Paterson. The linear postman:
message-forwarding algorithms using
sequential storage.
10.30 – 11.45
A.P. Ershov. A definition of
computable functions (computable
functions over algebraic systems).
11.45 – 12.00
V.M. Glushkov. On formal
transformation of algorithms (presented
by A.A. Letichevsky)
Saturday, September 22, afternoon
session
H. Zemanek, Chairman
16.00 – 18.00
Brief (1/4hour) communications:
Yu.V. Matijasevich. What should
we do having proved a decision problem
to be unsolvable?
N.M. Nagorny. Algorithms as a
basis for formulating constructive
mathematical notions.
G.N. Salikhov. On an algorithm
for finding weights and nodes of cubic
formulae.
A.V. Kabulov. Automation of
solving some problems in discrete
mathematics.
A.O. Buda. Four lessons of riding
two horses of theoretical and system
programming.
S.S. Lavrov. Our theories are not
mad enough.
A.V. Anisimov. Backtracking
transformers.
A.L. Semenov. Choosing complexity
functions properly.
A.P. Ershov. Concluding remarks.
D. Knuth. Nathematics also uses
low-level languages (concluding remarks).
After the formal closing of the
symposium, September 22, at 20.00 an
evening “algorithm party”
was held, where one of the founders of
modern theory of algorithms Steven C.
Kleene shared with
the participants his personal
reminiscences on the origin of the idea
of recursive function.
The symposium work was being
constantly covered by regional newspaper
“Khoresm Pravda”.
September 21 a special Urgench
television program was brodcasted.
September 18 a central Uzbek
paper “Pravda Vostoka” published an
announcement about beginning of the
Symposium, and
September 25 inserted a summary of the
results of its work. Symposium
participants constantly (and
with gratitude) felt attention on the
part of UzbSSR Academy of Sciences and
Khorezm regional
leaders. An idea was put forward to
rename one of Urgench streets into
“Algorithm Street”.
The richness of symposium
scientific program was well supplemented
with the chance to get to
know original culture of Khoresm and
other regions of Uzbekistan. The meeting
in Urgench was
unique in conception and fruitful in
realization; it will long be a source of
unforgettable memories
for all its participants. Urgench
Symposium, that took place on the
ancient homeland of an
“algorithm” notion ancestor, will
undoubtedly go down in history of the
theory of algorithms.
A.P.
Ershov, V.A. Uspensky
Íàçàä
|
