2010 - 2019
- 02 Nov 2015
at Aula Maxima, UCC
OLLSCOIL na hÉIREANN
THE NATIONAL UNIVERSITY OF IRELAND
TEXT OF THE INTRODUCTORY ADDRESS DELIVERED BY:
PROFESSOR MICHEL SCHELLEKENS, School of Computer Science & Information Technology, in University College Cork, on 2 November 2015, on the occasion of the conferring of the Degree of Doctor of Science, honoris causa, on DONALD ERVIN KNUTH
Deputy Lord Mayor of Cork, Mayor of Lincoln, Chancellor of the NUI, President, Registrar of the NUI, Distinguished Guests, Ladies and Gentlemen,
It is a great pleasure and honor, on this very day, November 2, 2015, Boole’s 200th birthday, to introduce an academic giant and Father of the Analysis of Algorithms, Donald Ervin Knuth.
Don is no stranger to this island. He and his wife Jill began their European honeymoon in the summer of 1961 disembarking from a Greek ocean liner in Cobh. Their two children John Martin Knuth and Jennifer Sierra Knuth were born in 1965 and 1966 respectively.
Don has been a generous supporter of UCC’s Boole Legacy interviews, donating his time, and expressing his admiration for the work and person of George Boole.
Today will mark Don Knuth’s third Celtic honorary degree, after having received doctorates from St Andrews and Glasgow in Scotland.
The connection with Ireland, the city of Cork and the figure of George Boole in particular, however, runs far deeper.
Both men were childhood prodigies. From an early age, both exhibited a great affinity for language. George Boole surprised adults with his knowledge of Latin, and later on Greek, French and German. Don Knuth attended Lutheran schools, where English grammar was taught in depth, sparking his deep interest in sentence structure, which contributed in turn to his investigations in compiler design and his love for coding and programming languages. It is well known that Don surprised judges of the confectionary manufacturer Ziegler by entering their competition to form as many words as possible from letters in "Ziegler's Giant Bar” with a grand total of 4500 words, 2000 more than the judges had compiled.
Both men were greatly influenced by their fathers. Boole’s father inspired young Boole through a deep love of science, and in particular the application of mathematics to scientific instruments. Donald’s father Ervin, a school teacher who taught in a Lutheran school, inspired a love for education, music, and mathematics. Ervin played the church organ at the Sunday church services and Donald soon became a passionate player and remains so to this very day. Don recently enjoyed visiting the organ in St. Finbarr’s cathedral and will soon visit SS Peter and Paul's Church for a guided tour of their organ. Some of Don’s favorite composers include Bach and Frank.
Following Alfred North Whitehead’s observation, it takes an unusual mind to undertake the analysis of the obvious. George Boole undertook the analysis of human thought while Don Knuth undertook the analysis of algorithms, investigating the efficiency of natural thought constructs dating back many centuries. Indeed, the origin of the term “algorithm” is rooted in a Latin translation of “al-Khwārizmī”, the Persian mathematician, astronomer and geographer.
Both George Boole and Don Knuth share a deep interest in finite structures. Boole’s love of finite structures is apparent in his wonderful textbook, “A Treatise on the Calculus of Finite Differences.” When Don Knuth created the new field “Analysis of Algorithms”, in the mid-sixties, the work deeply sourced this calculus of finite differences and Boole’s treatise in particular.
Both men share a love of imparting knowledge through meticulously crafted books. Don Knuth’s famous ongoing series, The Art of Computer Programming, has gained worldwide acclaim.
The development of the Analysis of Algorithms, laid out in Don’s first three volumes of The Art of Computer Programming, ultimately contributed to his receiving the 1974 ACM Turing award and the 1996 Kyoto Prize, the Japanese “Nobel” award.
In addition to his writings on computer science, Knuth is also the author of 3:16 Bible Texts Illuminated, in which he examines the Bible by a process of systematic sampling, namely an analysis of chapter 3, verse 16 of each book. Each verse is accompanied by a rendering in calligraphic art, contributed by a group of calligraphers under the leadership of Hermann Zapf. Even here, Boole and Knuth share an affinity for applying their knowledge to Bible study, where Boole expressed parts of the Bible through his logic.
Both men also share an algebraic view of the world and an intuitive affinity with symbolic manipulation, something Don commented on during UCC’s Boole Legacy interview in April 2015.
George Boole, at a time when our university was only just founded, introduced the world to an algebraic approach to logic. Don’s CalTech PhD thesis on finite semifields and projective planes illustrates his algebraic interest, a theme recurring in his later work.
His most recent volume, Vol 4A of The Art of Computer Programming, includes a discussion of Binary Decision Diagrams, data structures to represent and manipulate Boolean functions, and NP-complete problems, including the famous Boolean satisfiability problem. Don observed that this volume in the series is the most influenced by Boole. The word “Boole” is mentioned 607 times.
Finally, Boole and Knuth are also linked by an unusual coincidence: both have a celestial object named after them. In George Boole’s case, asteroid “17734 Boole”, discovered on January 22, 1998 by Paul G. Comba in Prescott, Arizona. In Don Knuth’s case, asteroid “21656 Knuth,” discovered on August 9, 1999 by P. Pravec and P. Kušnirák at the Ondřejov Observatory.
Boole lived during a time before the advent of Computer Science, yet in an era in which computational devices were beginning to raise considerable interest. Around the time in which our university was founded, Leibniz’s dream of mechanizing logic was rekindled through the work of George Boole, Charles Babbage and Ada Lovelace.
Don Knuth started his work in an era during which Computer Science emerged. Faced with the astonishing applications of our time, the successes of model checking in program verification, the evolution of SAT solvers and the rise of data analytics, impacting search engines, social media, autonomous cars as well as medicine and genetics, it is easy to forget that Computer Science is a relatively young field.
The father of Computer Science, Alan Turing, made his central contributions less than a century ago. Compared with the field of Mathematics, for which rigorous arguments emerged in Greek times, most notably in Euclid’s Elements, Computer Science is very much still in an emerging stage.
Large-scale software development in scope and achievement could be compared with medieval cathedral construction, supported by tremendous expertise and a host of state of the art techniques, but was not yet supported by a calculus such as Newton’s, enabling one to predict the properties of a building from blue prints.
Computer Science, “pre-Knuth”, lacked a systematic approach to properly predict the time it would take for an algorithm to complete when executed from its “blue-print”, the actual code. The first three volumes of Don’s The Art of Computer Programming lay out a foundation enabling one to predict algorithmic efficiency from the source code, giving rise to the field of the Analysis of Algorithms.
As such, Don Knuth’s work impacted the field of Computer Science during its early development, lending it the wings needed to lift it from an emerging field to a fully-fledged science.
The first three volumes of The Art of Computer Programming set new standards for the field and greatly helped shape the discipline. Volumes of TAOCP currently line the shelves of most Computer Scientists and Programmers.
For the listener not versed in Computer Science, it may be hard to comprehend the profound impact these works have had on the field. Many of the earlier results in Computer Science still lacked rigor, or where erroneous.
As a young mathematician and fledgling computer scientist embarking on a PhD combining Semantics with the vast world of the Analysis of Algorithms, I distinctly recall the moment when I opened Volume 3 of Don’s TAOCP, in which the Analysis of Algorithms was laid out with such perfect clarity, guiding the reader through each fundamental aspect with utmost care, rigor and tremendous attention to detail—a definite turning point, providing the firm basis needed to build on. This experience is echoed by programmers and fundamental researchers throughout the world.
Generations of Computer Scientists benefited from TAOCP. Bill Gates famously stated that "If you think you're a really good programmer... read (Knuth's) Art of Computer Programming... You should definitely send me a résumé if you can read the whole thing." The New York Times referred to it as “the profession's defining treatise.” Knuth’s wonderful series is like so many seeds, planted and nourished by the gardener with infinite care. Around the globe, a forest has grown on the back of this work, laying out for us the vast landscape of Computer Science.
It is often said that progress is made by standing on the shoulders of a giant. What is left unstated is the challenging climb to reach those shoulders. By having laid out the landscape of Computer Science, in its infinite beauty and intricacy, by dispelling mysteries of the field, and, indeed, in some cases by highlighting remaining mysteries, lending impetus to new investigations, Don Knuth, like Euclid before him, has given all of us and his chosen field a precious gift: to let us see this landscape through the eyes of a giant. He generously lent his brilliance to the scientific community, expertly laying out the work of those who came before. The Art of Computer Programming guides all with a firm yet gentle hand, playing out the intricacies of beautiful code as well as the mesmerizing mathematical underpinnings in a deceptively effortless way, reminiscent of Bach’s fugues.
His work did not stop with laying out the foundations of the Analysis of Algorithms, nor did it begin with this. He is a pioneer in computer programming with major contributions to the design and analysis of algorithms, computer languages and structured programming. Knuth has made a multitude of contributions to mathematics and computing, including the Knuth-Bendix algorithm. Knuth worked on the semantics of programming languages, attribution grammar, parsing and the Knuth-Morris-Pratt algorithm. He generalized the Robinson-Schensted correspondence between permutations and pairs of standard Young tableaux and lent the field the notion of Knuth equivalence.
Another contribution, which has transformed the way that mathematics is communicated, is Knuth's invention of TeX, a language for typesetting mathematical and scientific articles. Starting in 1976 Knuth took ten years off his other projects to work on the development of TeX and METAFONT, a computer software system for alphabet design in which he continued to write his Art of Computer Programming.
Born in Milwaukee, Wisconsin, Don Knuth received his PhD from California Institute of Technology in 1963. He held a position as the Fletcher Jones Professor of Computer Science at Stanford University from 1977 to 1989, where, since 1990, he is Professor of the Art of Computer Programming. In 1993 he became Professor Emeritus at Stanford University and continued to live on the University Campus.
He has received numerous prestigious awards, including the Turing Award of the Association for Computing Machinery, the U.S. National Medal of Science, the Steele prize of the American Mathematical Society, and the Computer Pioneer Award of the Institute of Electrical and Electronics Engineers. He is a member of the U.S. National Academy of Science and a member of the National Academy of Engineering. He was the first recipient of the Grace Murray Hopper Award from the Association for Computing Machinery; he was awarded the Adelskold Medal from the Swedish Academy of Sciences, the John von Neumann Medal from the IEEE; and the Kyoto Prize from the Inamori Foundation, the Japanese “Nobel”, solely awarded to researchers combining both scientific brilliance with integrity of character, recognizing dedicated service to the scientific community.
Don Knuth, father of the Analysis of Algorithms, author of the masterwork The Art of Computer Programming, independent thinker and dedicated teacher, it gives me great pleasure to invite you to receive the Degree of Doctor of Science, honoris causa.
Praehonorabilis Cancellarie, totaque universitas!
Praesento vobis hunc meum filium, quem scio tam moribus quam doctrina habilem et idoneum esse qui admittatur, honoris causa, ad gradum Doctoratus Scientiae, idque tibi fide mea testor ac spondeo totique Academiae.