This section concerns contributions to the development of information science and technology at its logical (as opposed to its hardware) level.  (A separate section addressing the latter will appear later this year.)  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 40% 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 three 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 (26% of recipients)
• Jewish Recipients of the IEEE C.E. Shannon Award in Information Theory (37% of recipients)
• Jewish Recipients of the John von Neumann Theory Prize in Operations Research (44% 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."¹  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, that 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 to Gö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.²

• 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.³  (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.⁴  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."⁵  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 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-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 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. 

• The invention of the MINIX operating system by Andrew Tanenbaum.  MINIX was the precursor of, and inspiration for, the widely 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.⁶)

• The developmment 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 Kolmogorov complexity 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 SIMPLEX linear programming algorithm by George B. Dantzig.   Linear programming (LP), invented independently by Dantzig and Leonid Kantorovich, is a powerful optimization technique that is widely 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.⁷  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.⁸  Wiener and Alexander Khinchine independently derived the Wiener-Khinchine theorem, another central result in statistical 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 problems and 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 Ronald Rivest⁺) 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; he supervised the breaking of the Japanese diplomatic code PURPLE in 1940 and directed 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 by Barney Reiffen, Robert Fano, and Andrew Viterbi.

• The co-invention of the Reed-Solomon error correction code by Gustave Solomon.  Reed-Solomon and 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") and the 1993 US National Medal of Technology for work that revolutionized telephone switching systems worldwide.

• 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 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, and Robert Kahn.  Together with Kleinrock, Baran, and Kahn, Donald Davies⁺, Vinton Cerf⁺, and Lawrence Roberts⁺ are the six individuals most frequently cited as principal inventors of the Internet.  Kleinrock, Kahn, Roberts⁺, and Cerf⁺ were awarded the US National Academy of Engineering's half-million dollar Draper Prize⁹ in 2001 "for the development of the Internet."  Baran, Kleinrock, Davies⁺, and Roberts⁺ 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."  Kahn and Baran received US National Medals of Technology in 1997 and 2007, respectively.  Kleinrock was awarded the US National Medal of Science in 2007.  Kahn and Cerf⁺ co-invented the TCP/IP protocols for integration of heterogeneous networks, which is the basis of the Internet's "inter-networking" architecture.  They shared the 2004 A. M. Turing Award for this work, and in 2005 each received the US Presidential Medal of Freedom.
  

• The invention of Alohanet (precursor to Ethernet) 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.

• 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 invented in the 1950s by 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. See  AI: The Tumultuous History of the Search for Artificial Intelligence, by Daniel Crevier (Basic Books, New York, 1993, p. 26), or Encyclopedia of Computer Science (Fourth Edition), edited by Anthony Ralston, Edwin D. Reilly, and David Hemmendinger (Wiley, Chichester, England, 2003, p. 91).
7. See http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Dantzig_George.html.
8. See the next-to-last paragraphs in  http://www.siam.org/news/news.php?id=526 and http://www.aip.org/pt/vol-53/iss-11/p75.html.
9. See http://www.nae.edu/NAE/awardscom.nsf/weblinks/DWHT-4T7KER?OpenDocument.
 
*  Georg Cantor and Herbert Simon had  Jewish fathers; Simon's mother was of partial Jewish descent, which was probably also the case for the mother of Georg Cantor.  Max Newman had a Jewish father and a non-Jewish mother, while John McCarthy, Larry Page, and Lotfi Zadeh have, or had, Jewish mothers.  For more information, see the footnotes to these and other listings in Jewish Computer and Information Scientists.

+ Non-Jewish.

---

QUESTIONS AND COMMENTS: CONTACT US

JINFO HOME

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