JINFO.ORG

This section concerns contributions to the development of information science and technology at its logical (as opposed to its hardware) level. Specifically, this section deals with areas such as computation theory, artificial intelligence, the statistical theories of information, communication, and systems control, cryptography, operations research, computer and network architectures, and algorithm and software design. The general level of this contribution is reflected in the current ~45% Jewish membership in the Computer and Information Sciences division of the US National Academy of Sciences and in the percentages of Jewish recipients shown below for several of the most prestigious awards in the field.

Jewish Computer and Information Scientists

Jewish Recipients of the ACM A.M. Turing Award in Computer Science (33% of recipients)Jewish Recipients of the IEEE C.E. Shannon Award in Information Theory (33% of recipients)Jewish Recipients of the John von Neumann Theory Prize in Operations Research (41% of recipients)Jewish Recipients of the EATCS/ACM Kurt Gödel Prize in Theoretical Computer Science (45% of recipients)Jewish Recipients of the ACM Paris Kanellakis Theory & Practice Award in Computer Science (45% of recipients)Jewish Recipients of the IMU Rolf Nevanlinna Prize in Computer & Information Science(56% of recipients)Some of the more notable Jewish contributions are listed below. (The names of non-Jewish scientists and engineers mentioned in the accompanying discussion have been denoted with the superscript "+"in order to avoid confusion.)

- The interpretation of thermodynamic
entropy as an information metric by Leo Szilard. Szilard's 1929 analysis of the Maxwell's demon paradox "is now considered to be the earliest known paper in what became the field of 'information theory' in the 1950s and 1960s."^{ 1}Other important information metrics were formulated by John von Neumann, Solomon Kullback, and Alfréd Rényi. The von Neumann entropy, e.g., is the quantum generalization of Szilard's classical information measure and is one of the fundamental concepts in quantum information theory.

The introduction of the diagonal argument proof method by Georg Cantor*. This method is central to the derivation of the incompleteness and noncomputability results of Gödel^{+}, Turing^{+}, Church^{+}, and Post that lie at the foundation of theoretical computer science. In a 1936 paper, Emil Post described a mechanical definition of computation, known as the Post machine, which is equivalent to the Turing machine introduced by Alan Turing^{+}in a paper that appeared several months later. Post had understood the undecidability implications of such a definition as early as 1921, but had hesitated to publish and lost priority toGödel^{+}, who approached the problem from a very different perspective in his 1931 paper.Post was also one of the four principal founders of the theory of recursive functions, which is of immense importance in theoretical computer science.^{2}

The design of Colossus, the first all-electronic, digital, programmable computer by Max Newman*. Although Colossus was not a general purpose computer and had only limited programmability, it represented an important milestone. Newman, a Cambridge University professor of mathematics, headed the "Newmanry," a special code-breaking unit at Bletchley Park in England during World War II. Colossus was designed and built to break the German Lorenz cipher, which was used by the Nazi high command to encrypt its highest priority communications. The Colossus machines (which were physically constructed by a team working under the electrical engineer Tommy Flowers^{+}) played a critical role in securing Allied victory in Europe and were influential in the post-war development of computers in England.^{3 }(Contrary to what is sometimes claimed, Alan Turing^{+}, who was Newman's protégé, had relatively little direct involvement with Colossus, although his ideas were extremely influential. Newman later declined to become "Sir Max Newman" in protest against the treatment accorded Turing^{+}by the postwar British government.)

The design of the logical architecture employed in virtually all modern computers by John von Neumann. The von Neumann architecture was incorporated into the design of EDVAC, the first all-electronic, binary, stored-program, general purpose computer.^{4}Von Neumann's 1946 paper "Preliminary Discussion of the Logical Design of an Electronic Computing Instrument" has been described as "the most influential paper in the history of computer science ... the ideas it contains, collectively known as the von Neumann machine, have provided the foundation for essentially all computer system developments since that date."^{5}Von Neumann also invented the theory of system fault tolerance and the cellular automata model of computation. The universal von Neumann constructor, a generalization of the universal Turing machine that emerged out of von Neumann's theory of self-reproducing automata, is one of the foundational concepts in the field of molecular nanotechnology.

The invention of parallel supercomputing architecturesby Stephen Unger, Daniel Slotnick, David Schaefer, and Włodzimierz Holsztyński. Unger, Slotnick, Schaefer, and Hosztyński are four of the "eight men [who] dominate the history of SIMD computer architectures."^{ 6}SIMD (single instruction, multiple data) refers to the basic parallel processing technique employed in the earliest supercomputers.^{7}Unger was the first to propose and explore such architectures in the late 1950s. Slotnick designed SOLOMON in the early 1960s and built the first parallel processing prototypes. He was later the architect ofIlliac IV, the first important parallel supercomputer, which had up to 256 processing elements. Built with 64 processing elements in the early 1970s with ARPA (now DARPA) funding and operated by NASA, Illiac IV remained the world's fastest computer until its shutdown in 1981. In the late 1970s and early 1980s, Schaefer initiated and managed the development of NASA'sMassively Parallel Processor (MPP), the first truly massively parallel supercomputer, with 16,384 processing elements. Holsztyński designed theGeometric-Arithmetic Parallel Processor (GAPP)in 1981. GAPPs with hundreds of thousands of processing elements are used today in real-time video image processing applications such as image enhancement and noise reduction, video data compression, and format and frame rate conversion.

The co-discovery of NP-completeness by Leonid Levin. Levin and Stephen Cook^{+}independently discovered and proved what is now referred to as the Cook-Levin theorem, the central result concerning the P = NP? question, which is the major open problem in theoretical computer science. Richard Karp introduced the terms "P" and "NP" and defined NP-completeness (although not the term itself) in its present form. He also identified the decision problem formulations of many well-known, combinatorially intractable problems as being NP-complete. Levin, Karp, and Manuel Blum are considered to be three of the six founders of the field of computational complexity theory.

The invention of context-free languages by Noam Chomsky. This work was based on Emil Post's theory of production systems in mathematical logic. It is the basis of the BNF notation widely used to specify the syntax rules of programming languages. Chomsky's hierarchical classification of formal languages initiated the field of formal language theory in computer science.

The co-invention of BASIC by John Kemeny. Kemeny and Thomas Kurtz^{+}developed this popular programming language. At least one-third of the nine-person team that developed FORTRAN under John Backus^{+}at IBM were Jewish. Also at IBM,Adin Falkoff collaborated with Kenneth Iverson^{+}on the design and development of the array processing language APL.Ada, an advanced programming language adopted by the US Department of Defense as its standard high-level computer language in the 1980s and 1990s, was designed by Jean Ichbiah. LISP, the second-oldest high-level programming language still in use (primarily in artificial intelligence research), was invented by John McCarthy* in 1958. Barbara Liskov was awarded the 2008 ACM Turing Award for fundamental advances in programming language design. The ACM press release noted that her innovations "are now the basis of every important programming language since 1975, including Ada, C++, Java, and C#."

The invention of the MINIX operating system by Andrew Tanenbaum. MINIX was the precursor to, and inspiration for, thewidely used Linux operating system.

The invention of the computer spreadsheet by Dan Bricklin and Robert Frankston. Bricklin and Frankston's VisiCalc spreadsheet was the first "killer app." The Lotus 1-2-3 spreadsheet program, the most successful software product of its time, was developed by Jonathan Sachs and Mitchell Kapor.

The co-founding of the field of artificial intelligence by Marvin Minsky, Herbert Simon*, and John McCarthy*. (Allen Newell^{+}is considered to have been the other one of its four founders.^{8})

The development of computer algebra (symbol manipulation) programs by Jean Sammet (FORMAC), Carl Engelman (MATHLAB), Joel Moses (MACSYMA), and Stephen Wolfram (Mathematica).

The invention of reversible computation theory by Rolf Landauer.Reversible computation circumvents the thermodynamic limits on irreversible computation established by John von Neumann, and is one of the foundations of quantum computing.The ballistic architecture, or Fredkin gate, model of reversible computation was introduced by Edward Fredkin.

The invention of quantum computing by Paul Benioff, Richard Feynman, and David Deutsch.

The invention of DNA computing by Leonard Adleman.

The invention of fuzzy logic by Max Black and Lotfi Zadeh* (independently).

The invention of algorithmic complexity by Ray Solomonoff. Also termed Kolmogorovcomplexity or algorithmic information theory, Solomonoff's 1964 work was later arrived at independently by Andrei Kolmogorov^{+}(1965) and Gregory Chaitin (1969).

The invention of the Monte Carlo method by Stanislaw Ulam and John von Neumann. This statistical numerical method is one of the cornerstones of computer simulation science.Von Neumann invented the first computer-based random number generator for use in Monte Carlo simulations.

The invention of nondeterministic algorithms by Michael Rabin. Such algorithms employ Monte Carlo methods to provide efficiently computable solutions that are correct with high (but less than one hundred percent) probability to many problems whose exact solution is computationally intractable. Rabin's probabilistic primality testing, e.g., is essential to the practical implementation of RSA public-key cryptography.

The invention of the SIMPLEXlinear programmingalgorithmby George B. Dantzig. Linear programming (LP),invented independently by Dantzig and Leonid Kantorovich,is a powerful optimization techniquethat iswidely used in economics and engineering. It has been estimated that, aside from database operations such as sorting and searching, LP consumes more computer time than any other mathematical procedure.^{9}The SIMPLEX algorithm remains LP's fundamental numerical solution technique.

The invention of the ellipsoid method of convex optimization by Naum Shor and, independently, by Arkadi Nemirovski and David Yudin. This technique, which was successfully employed by Leonid Khachiyan^{+}to prove the polynomial-time complexity of linear programming, underlies most modern results concerning the computational complexity of convex optimization programs. The ellipsoid method provided the first effective solver for semidefinite programs (which are encountered in many engineering applications) and has led to significant advances in combinatorial optimization.

The invention or co-invention of four of CiSE's "Top Ten Algorithms of the Century" by Stanislaw Ulam, John von Neumann, George Dantzig, Cornelius Lanczos, Leslie Greengard, and Vladimir Rokhlin. The January/February 2000 issue of Computing in Science & Engineering, a joint publication of the American Institute of Physics and the IEEE Computer Society, assembled a list of "the ten algorithms with the greatest influence on the development and practice of science and engineering in the 20th century." In addition to the Monte Carlo method and the SIMPLEX algorithm discussed above, the top ten algorithms included the Krylov subspace iteration method for the solution of large systems of linear equations (Lanczos) and the fast multipole algorithm for the solution of many-body problems (Greengard and Rokhlin).

The invention of the Wiener filter by Norbert Wiener. The Wiener filter is an optimal filter for extracting signals from noise in stationary stochastic systems and is one of the central results in statistical communication theory, a field pioneered by Wiener.(A version of the Wiener filter was also formulated independently by Andrei Kolmogorov^{+}.) The nonlinear, recursive Wiener filter,its extension to nonstationary systems for use in tracking and guidance was first formulated by Peter Swerling in 1959.^{10}Wiener and Alexander Khinchine independently derived the Wiener-Khinchine theorem, another central result instatistical communication theory.

The invention of statistical decision theory by Abraham Wald.Among other applications,statistical decision theory plays an important role in radar, control, and communication. Its minimax decision rules derive from John von Neumann's theory of optimal strategies (theory of games).

The invention of dynamic programming by Richard Bellman. This procedure solves sequential, or multi-stage, decision problemsand is one of the foundations of modern control theory. It also constitutes the basis for many powerful algorithms, including the Viterbi algorithm, invented by Andrew Viterbi, that is used to decode convolutional codes employed in error correction and in CDMA and GSM digital cellular telephony.

The co-invention of public-key cryptography by Martin Hellman. Hellman and Whitfield Diffie^{+}devised the Diffie-Hellman algorithm for secure key distribution over nonsecure channels.

The co-invention of RSA by Adi Shamir and Leonard Adleman. RSA (which is named for its three co-inventors,Shamir, Adleman, and RonaldRivest^{+})is the most widely used public-key algorithm.

The invention of quantum cryptography by Stephen Wiesner. Although quantum key distribution was invented in the mid-1980s by others, it was specifically acknowledged to have been inspired by Wiesner's circa 1970 work that established the basic principles underlying the use of quantum mechanics to achieve information security.

The development of mathematical and statistical cryptanalysis by William Friedman. Friedman's innovations are ranked amongst the greatest in the history of cryptology; hesupervised the breaking of the Japanese diplomatic code PURPLE in 1940 anddirected US cryptanalysis during World War II. Other important World War II cryptologists included Solomon Kullback, Leo Rosen, and Abraham Sinkov in the US and Max Newman*, I.J. Good, and Leo Marks in England. Newman and Good were instrumental in the design of Colossus, which was used to break the Lorenz cipher employed by the German high command. Marks, the chief cryptologist of the Special Operations Executive (SOE) of MI6, revolutionized the one-time pad.

The invention of convolutional codes by Peter Elias. Important decoding algorithms for these error correction codes were invented byBarney Reiffen, Robert Fano, and Andrew Viterbi.

The co-invention of the Reed-Solomon error correction code by Gustave Solomon.Reed-Solomonand Viterbi- or Fano-decoded convolutional codes, or hybrid concatenations of the two, are probably the most widely used error correction techniques at present.

The invention of the LZ data compression algorithm by Jacob Ziv and Abraham Lempel. Although LZ coding was not the first data compression technique invented, it is today the most widely used in commercial systems.

The development of automated, electronically switched telephone networks by Amos Joel. Joel received both the 1989 Kyoto Prize ("Japan's Nobel Prize") andthe 1993 US National Medal of Technologyfor work that revolutionized telephone switching systems worldwide. Joel's 1972 US Patent No. 3,663,762, "Mobile Communication System," is the basis of the switching technology that made cellular telephone networks possible.

The co-invention of spread spectrum communications by Hedy Lamarr. Lamarr (the Hollywood actress) and George Antheil^{+}(a Hollywood composer) received US Patent No. 2,292,387, "Secret Communication System," in 1942 for the invention of frequency-hopped spread spectrum. The digital form of spread spectrum that is widely used in cellular communications (CDMA) was developed by Qualcomm, a company founded by the information theorists Irwin Jacobs and Andrew Viterbi. Jacobs received the US National Medal of Technology in 1994 and Viterbi received the US National Medal of Science in 2007. Both were recognized for their pioneering innovations in digital wireless communications. Joel Engel also received the Medal of Technology in 1994 as one of the two "fathers of the cellular phone" for his work on the development of the basic network architecture used worldwide in cellular telephony.

The co-invention of the Internet by Leonard Kleinrock, Paul Baran, Vinton Cerf,* and Robert Kahn. Together with Kleinrock, Baran, Cerf, and Kahn, Donald Davies^{+}and Lawrence Roberts^{+}are the six individuals most frequently cited as principal inventors of the Internet. Kleinrock, Cerf, Kahn, andRoberts^{+}were awarded the US National Academy of Engineering's half-million dollar Draper Prizein 2001"for the development of the Internet." Baran,Kleinrock,Davies^{+},andRoberts^{+}received the first IEEE Internet Award in 2000 for "their early, preeminent contributions in conceiving, analyzing and demonstrating packet-switching networks, the foundation technology of the Internet." Cerf, Kahn, andBaran receivedUS National Medals of Technology, the former two in 1997 and the latter in 2007. Kleinrock was awarded the US National Medal of Science in 2007.Cerf and Kahnco-invented the TCP/IP protocol for integration of heterogeneous networks, which is the basis of the Internet's "inter-networking" architecture. They shared the 2004 ACM Turing Awardfor this work,and in 2005 each received the US Presidential Medal of Freedom.

The invention of Alohanet (precursor toEthernet) by Norman Abramson. Alohanet was a packet-switched research network that solved the major problem of packet interference, or "packet collision." Alohanet was further developed by Robert Metcalfe^{+}into Ethernet (which Metcalfe^{+}originally called the Alto Aloha network), the standard method used in local area computer networking. Radia Perlman's spanning tree protocol, which solved the problem of broadcast storms due to network switching loops, was the critical enabler that allowed Ethernet to realize high levels of robust network complexity.

The invention of Google by Sergey Brin and Larry Page*.The algorithm employed by Google,the most powerful and widely used search engine on the Internet,employs an adaptation of the citation frequency "impact factor" metric originally inventedin the 1950sby Eugene Garfield to rank the relative influence of scientific researchers, articles, and journals.

NOTES

1. See Genius in the Shadows: A Biography of Leo Szilard, by William Lanouette (Scribner's, New York, 1992, p. 63).

2. See "Emil Post and His Anticipation of Gödel and Turing," by John Stillwell in Mathematics Magazine (Mathematical Association of America, Washington, DC, Vol. 77, No. 1, Feb. 2004, pp. 3-14). See also http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Post.html.

3.See "Max Newman: Mathematician, Codebreaker and Computer Pioneer," by William Newman in Colossus: The First Electronic Computer, edited by Jack Copeland (Oxford, Oxford and New York, 2004).

4. See http://www.nationmaster.com/encyclopedia/EDVAC.

5. Encyclopedia of Computer Science (Fourth Edition), edited by Anthony Ralston, Edwin D. Reilly, and David Hemmendinger (Wiley, Chichester, England, 2003, p. 1841).

6.Parallel Supercomputing in SIMD Architectures, by R. Michael Hord (CRC Press, Boca Raton, FL, 1990).

7. Although most supercomputers are now based on MIMD (multiple instruction, multiple data) architectures, their individual processing nodes generally embody small-scale SIMD capabilities. The still hypothetical quantum computer can be thought of as an SIMD machine with exponentially manyvirtualprocessors.

8. See AI: The Tumultuous History of the Search for Artificial Intelligence, by Daniel Crevier (Basic Books, New York, 1993, p. 26), orEncyclopedia of Computer Science (Fourth Edition), edited by Anthony Ralston, Edwin D. Reilly, and David Hemmendinger (Wiley, Chichester, England, 2003, p. 91).

9.See http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Dantzig_George.html.

10. See the next-to-last paragraphs in http://www.siam.org/news/news.php?id=526 and in the obituary published in the November 2000 issue of Physics Today (pp. 75-76). See also the discussion in the Appendix to Tracking and Kalman Filtering Made Easy, by Eli Brookner (Wiley, New York, 1998, pp. 383-387).

* Georg Cantor and Herbert Simon had Jewish fathers; Simon's mother was of partial Jewish descent, which was also the case, at a minimum, for the mother of Georg Cantor. Max Newman and Vinton Cerf had Jewish fathers and non-Jewish mothers, while John McCarthy, Larry Page, and Lotfi Zadeh have, or had, Jewish mothers. For more information, see the footnotes to these and other listings inJewish Computer and Information Scientists.

+ Non-Jewish.

QUESTIONS AND COMMENTS: CONTACT US

JINFO HOME

Copyright © 2004-2017 JINFO.ORG. All rights reserved.

Reproduction of any part of this website

without the express, prior written permission of JINFO.ORG is prohibited.