At age 94, pioneer Turing award winner, computational complexity theory, Juris Hartmanis, died

7月29日,1993年图灵奖得主、One of the founders of computational complexity theoryJuris Hartmanis去世,享年94岁.

From physics to mathematics,Ultimately, he devoted himself to the field of computer science

Hartmanis于1928年7月5Born in Latvia,父亲Mārtiņš Hartmanisis a general of the Latvian army,于1940He was arrested in the war and died in prison. 

二战结束时,HartmanisA family became“流民”immigrated to Germany.在那里,Hartmanis学习物理,并于1949Received a BA in Physics from the University of Marlborough in 2007.1950年,HartmanisA family receives funding to immigrate to the United States,He entered the University of Kansas City for a master's degree,But because the school does not have a graduate program in physics,所以HartmanisJust change to math.

只用一年时间,Hartmanis就于1951Received a master's degree in applied mathematics,He was accepted as a Ph.D. candidate at the California Institute of Technology,Engage in lattice theory(latticetheory)的研究.1955年,HartmanisComplete a doctoral dissertation and obtain a PhD in mathematics.

1955年-1957年期间,HartmanisEntered Cornell University as a math lecturer,He then joined the Ohio State University Mathematics Department as an assistant professor for one year.在那之后,HartmanisWas attracted to General Electric based in Schenectady, NY (Schenectady) 的研究实验室,A stay is seven years.Because a new one was built there“Information Research Department”Conduct research in computing and informatics,This new field excitesHartmanisGreat interest and enthusiasm.

1965年,HartmanisLeaving General Electric to return to Cornell University,But this time it wasn't back in the math department,Instead, create and lead a new computer science department——One of the first computer science departments in the world.as the founder and first chair of the department,Hartmanis的眼光、The courage and democratic style have attracted a group of famous scholars to join,Among them Hopecroft(J．E．Hopcroft,1986年图灵奖得主)、格利斯(D．Giles,1995年ACMOutstanding Computer Education Award recipient)、霍洛维茨(E．Horowitz)、韦格纳(P．Wegner)和肖(A．Shaw)等.

在Hartmanis的带领下,Cornell University's computer science department has become the highest level among American universities、One of the most influential computer science departments.He served three times as head of the department,分别为1965-71年、1977-83年和1992-93年,并于1980年成为Walter R. Reed工程学教授.

Hartmanis于1996-1998left Cornell University,Served as Assistant Director of the National Science Foundation,Responsible for the Computer and Information Science and Engineering Council.1989年,HartmanisElected to the National Academy of Engineering,For his significant contributions to computational complexity theory and computational research and education.此外,HartmanisHe is also a member of the American Computer Society and the American Mathematical Society,也是美国国家科学院院士.1995年5月,The University of Missouri-Kansas City awarded him the title of Honorary Doctor of Humanities.

“计算复杂性”Theoretical Pioneers

在通用电气工作期间,HartmanisDeveloped many principles of computational complexity theory.正是在这一时期,他与同事Richard StearnsTogether they founded the field of computational complexity.

当时,Shannon's information theory came out not long ago,Shannon gave a formula,Can be calculated below a certain signal and noise average power,The maximum amount of information transmitted per unit time for a channel of a given bandwidth（This formula is called 「香农公式」) .studied physicsHartmanis受此启发,Keenly thought,The abstract calculation process should also have precise quantitative rules,to determine the answer to each question,How much computational effort is required.

around this idea,1965年,他们的论文“On the computational complexity of the algorithm（On the Computational Complexity of Algorithms）”Published in Key Moments in the Development of Theoretical Computer Science,Their key contribution is the collection of several different concepts and special cases about complexity levels into a general theory of computational complexity.

They define time and space complexity levels for functions and sets with arbitrary asymptotic keys,Several general results are proved、Linear acceleration and robustness to slight perturbations of the model.They also discuss approximate rational numbers and the complexity of algebra.Although the main research object is multi-band Turing machines,But they correctly argue that these concepts are universal,The same behavior would appear in any reasonable model.

Computational complexity theory as we know it today,from this seminal paper.for this achievement,Hartmanis和Stearns于1993Awarded the highest award in computer science in 2007-——图灵奖.

In addition to academic achievements,HartmanisHe is also well received in his usual work and teaching.

in a commemorative article,Hartmaniscolleagues in the Department of Computer Science at Cornell UniversityAnil Nerode提到：“He was chosen to host and organize a new computer science department,It is because he has shown scientific and interpersonal skills,And the broad vision for which he became famous.I will miss him very much.”

网站TRIBUTE ARCHIVEwrote in the obituary：“HartmanisIs a kind and patient person,Young children can sense his kindness and be attracted to him.He likes to talk,And because of his wide range of interests,Acted wisely on many topics.We will miss him greatly.”

一位HartmanisStudents taught at Cornell UniversityRyan Williams,An article was dedicated to expressing condolences,他提到：“I am so grateful to have known him.Without his trust,I wouldn't be a theoretical computer scientist;Without his initial influence,Nor would I be a good scientist.I wrote this article in tears;I want every reader to have the opportunity to make such a profound impact on a young man's life.”

参考链接：

• https://blog.computationalcomplexity.org/2022/07/juris-hartmanis-passed-away-on-july-29.html

• https://scottaaronson.blog/?p=6622

• http://www.techcn.com.cn/index.php?edition-view-132459-3

• https://rjlipton.wpcomstaging.com/2022/07/29/juris-hartmanis-1928-2022/

• https://www.tributearchive.com/obituaries/25480435/juris-hartmanis

• https://cacm.acm.org/magazines/2015/4/184690-an-interview-with-juris-hartmanis/fulltext

---

《新程序员001-004》已全面上市,欢迎扫描下方二维码或点击进入立即订阅,即可畅享电子书及精美纸质书！