• Abigailisms
  abigail@delanet.com.
  An Abigailism is a response to a question containing basic cognitive errors posed to a newsgroup (in particular, comp.lang.perl.misc). An example:
  Q. Do I need to test Perl scripts on a web server or can it be done offline?
  A. Do I need to have a bell on my bicycle, or can I ride it wearing a hat?
• Ackermann function
  Wilhelm Ackermann (1896-1962).
  This rapidly growing function is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive.
• Ada
  Ada Byron, Lady Lovelace (1815-1852).
  The Ada language was named after her. She was an assistant of Babbage, and arguably the first ever computer programmer. Web material on her abounds.
• Allen's interval calculus
  James Allen.
  A calculus for describing possible configurations of two one-pice temporal intervals.
• Armstrong's Axioms
  William W. Armstrong.
  Armstrong's Axioms are rules of inference for functional dependencies.
• AWK
  Alfred Aho, Peter Weinberger, Brian Kernighan.
  A Unix-based text/handling/macro programming language.
• Backus-Naur form
  John Backus, Peter Naur
  A formal metasyntax used to express context-free grammars.
• Bernoulli drive
  Daniel Bernoulli (1700-1782).
  Just like a disk drive but faster and more rugged - however not as fast as a hard drive.
• Bernstein's Conditions
  Arthur Bernstein.
  If the input sets of two tasks are independent of each other's output sets, and if their output sets are independent, they can execute in parallel .
• Bezier curve
  Pierre Bezier (1910 - 1999).
  A curve with a number of desirable properties, parameterised by a set of control points.
• Boolean logic
  George Boole (1815 - 1864).
  A simple logic, widely used in programming languages.
• Boyce Codd Normal Form
  Raymond Boyce, Edgar Codd.
  In databases, a relation is in Boyce-Codd Normal Form (BCNF) if every determinant is a candidate key
• Boyer-Moore Algorithm
  The Boyer-Moore algorithm is considered as the most efficient string-matching algorithm in usual applications.
• Bresenham's algorithm
  Jack Bresenham.
  In computer graphics, a straight-line drawing algorithm.
• Brooks's Law
  Fred Brooks.
  "Adding manpower to a late software project makes it later".
• Canny edge detector
  John Canny.
  In computer vision, the Canny edge detector found great favour and is, in some senses, optimal.
• Chen's notation
  Peter Chen.
  A particular representation of Entity-Relationship diagrams.
• Chomsky Hierarchy/Normal Form
  Noam Chomsky.
  The Chomsky hierarchy is a containment hierarchy of classes of formal grammars that generate formal languages.
  A formal grammar may be in Chomsky normal form if its production rules are of a particular form.
• Chu spaces
  Peter Chu.
  Chu spaces are a model of concurrent computation extending automata theory to express branching time and true concurrency.
• Church-Turing thesis
  Alonzo Church (1903-1995), Alan Turing (1912-1954),
  The Church-Turing thesis states in its most common form that every effective computation or algorithm can be carried out by a Turing machine.
• Cristian's algorithm
  Flaviu Cristian.
  A technique for synchronising the clocks of machines in a distributed system.
• Curry function
  Haskell Curry.
  For example, for any two parameter function f(x,y), there is a one parameter function f' such that f'(x) is a function that can be applied to y to give (f'(x))(y) = f (x,y). The function f' in the example above is called the "curried" form of the function f.
• Daaubechies wavelets
  Ingrid Daubechies.
  A family of wavelets: pioneering work of the 1980s.
• Davis-Putnam algorithm
  Martin Davis, Hilary Putnam.
  A depth-first search algorithm with backtracking and unit propagation.
• Dempster-Shafer theory of evidence
  Arthur Dempster, Glenn Shafer.
  Dempster-Shafer Theory considers a Universe of Discourse U, also called Frame of Discernment, which is a set of mutually exclusive alternatives
• Dijkstra's algorithm
  Edsger Dijkstra (1930 - 2002).
  An algorithm to find the shortest paths from a single source vertex to all other vertices in a weighted, directed graph.
• Duff's device
  Tom Duff.
  "The most dramatic use yet seen of fall through in C". Duff's device expresses general loop unrolling directly in C. Duff has written "I almost certainly did invent it. I had definitely not seen or heard of it when I came upon it, and nobody has ever even claimed prior knowledge, let alone provided dates and times. Please note that I do not claim to have invented loop unrolling, merely this particular expression of it in C."
• Fitts' law
  Paul Fitts.
  "The time to acquire a target is a function of the distance to and size of the target". This is useful is HCI. A more mathematical formulation exists.
• Floyd's algorithm
  Robert Floyd.
  An algorithm for finding the shortest path between two graph vertices.
• Foster's Metric
  John Foster.
  Foster's Metric measures software size/complexity, equating lines of code to measures of length. For large systems found in telecommunications applications which Foster maintained at BT, miles are used.
• Fourier transform
  Jospeh Fourier (1768-1830).
  Fourier theory and the Fourier transform are properly the property of mathematics, but they have found extensive use in the deriving of efficient computational algorithms, image and signal processing, and other areas of Computing.
• Gaussian X
  Johann Carl Friedrich Gauss (1777 - 1855).
  Many, many things in mathematics carry Gauss' name; a number of these are deployed in areas of Computing.
• Gentzen sequent calculus
  Gerhard Gentzen (1909-1945).
  A calculus used in proof theory.
• Gödel's incompleteness theorem
  Kurt Gödel (1906-1978).
  Perhaps one of the most important theorems proven in the 20th century, ranking with Einstein's Theory of Relativity and Heisenberg's Uncertainty Principle. Gödel demonstrated that within any given branch of mathematics, there would always be some propositions that couldn't be proven either true or false using the rules and axioms of that mathematical branch itself.
• Godwin's Law
  Mike Godwin.
  "As a Usenet discussion grows longer, the probability of a comparison involving Nazis or Hitler approaches one". This law is part of Usenet hacker culture.
• Gouraud shading
  Henri Gourad.
  The most common type of shading used in consumer 3D graphics hardware - it takes the lighting values at each of a triangle's three vertices, then interpolates those values across the surface of the triangle.
• Gray Code
  Frank Gray.
  the Gray Code is a binary numeral system where two successive values differ in only one bit.
• Guttman-Rosler Transform
  Uri Guttman, Larry Rosler.
  An improvement on the Schwartzian Transform (qv).
• Hamming code/distance
  Richard Hamming (1915-1998).
  Hamming distances are used in the definition of Hamming codes, an early forward error correction technique.
• Haskell
  Haskell Curry.
  A functional programming language.
• Henkin method
  Leon Henkin.
  A method used to prove the Compactness theorem that follows from Gödel's Completeness theorem. It was instrumental in shaping the further developments of logic and model theory.
• Hennesy-Milner Logic
  Matthew Hennessy and Robin Milner.
  A modal logic for processes. This theorem
• Herbrand's theorem/interpretation
  Jacques Herbrand (1908-1931).
  This theorem provides a reduction of the first-order provability problem to the propositional level, plus an open-ended search. It is often considered to be the theoretical basis of automated theorem proving for classical logic.
• Hilbert system
  David Hilbert (1862-1943).
  A Hilbert system is one of the major types of systems for doing derivation. Hilbert systems use only two connectives and only one rule of inference.
• Hintikka set
  Jaakko Hintikka.
  Hintikka (downward saturated) sets are defined in mathematical logic. They are guaranteed to be coherent and consistent. The construction of downward saturated sets is a purely syntactic procedure which produces a semantic truth assignment (truth function) for the set.
• Hoare's logic
  Sir Anthony Hoare.
  A set of techniques used in the definition and design of programming languages.
• Hopfield nets
  John Hopfield.
  Hopfield developed ideas in theoretical physics that were used to define a class of neural network auto-associators called Hopfield nets.
• Horn clause
  Alfred Horn.
  In logic, a set of atomic literals with at most one positive literal.
• Hough transform
  Paul Hough.
  In image processing and low level vision, a technique for locating parameterised shapes such as conic sections in images.
• Huffman code
  David Huffman (1925-1999).
  A technique for compression, depending on statistical irregularity in the input.
• Jensen's device
  Jørn Jensen.
  A technique to implement pass-by-name, pioneered in Algol-60.
• Kahn process networks
  Gilles Kahn (1946-2006).
  These networks are a model for parallel processing.
• Kalman filter
  Rudolf Kalman (1930-).
  The Kalman filter is a set of mathematical equations that provides an efficient computational (recursive) solution of the least-squares method.
• Kohonen nets
  Teuvo Kohonen.
  A variety of self-teaching neural network.
• Kripke semantics
  Saul Kripke.
  A logic in which there are more than just two truth values; instead a semantics which uses partial orders is used.
• KPM algorithm
  Donald Knuth, Vaughn Pratt, James Morris.
  A very efficient string matching algorithm that minimises the number of matches that are tried.
• LZW compression
  Abraham Lempel, Jakob Ziv, Terry Welch.
  A widely used and efficient data compression algorithm.
• Mandelbrot set
  Benoit Mandelbrot (1924-2010). The very beautiful mandelbrot set displays fractal properties and has appeared as a poster on many bedroom walls.
• Markov chains/processes
  Andrei Markov (1856-1922).
  Markov processes are state-based systems in which the state changes are governed by probabalistic rules independent of time, but dependent on recent states.
• McQuary limit
  George McQuary.
  A 4-line limit suggested for signature fields in newsnet postings. Originally proposed to save bandwidth (and money), now a courtesy.
• Miranda
  Miranda in The Tempest.
  A non-strict purely functional programming language developed by David Turner. It is the successor of the functional languages SASL and KRC. (Miranda first used the expression "Brave New World").
• Moore's law
  Gordon Moore.
  Stated in 1965, Moore observed an exponential rise in the complexity of IC's. Recently, this has sometimes been interpreted as an annual doubling of computer power, or halving of cost/size ...
• McCulloch-Pitts neurons
  Warren McCulloch (1898-1969), Walter Pitts (1924-).
  A computational model of a brain neuron. Famous for being early (pre-"computers"), and very widely used in artificial neural networks.
• Nagle's algorithm
  John Nagle.
  A part of the TCP protocol designed to dampen "lumpy" behaviour observed as a result of one-byte transmissions.
• Needham-Schroeder protocol
  Roger Needham (1935-2003), Michael Schroeder.
  A protocol for the distribution of cryptographic keys.
• Nyquist criterion
  Harry Nyquist (1889-1976).
  Nyquist's criterion says that a signal must be sampled at least twice as often as its highest frequency to enable correct reconstruction of the signal when transmitted.
• Oberon
  Oberon was King of the Fairies in "A Midsummernight's Dream".
  A software environment developed at ETH, Zurich.
• Pascal
  Blaise Pascal (1623-1662).
  A computer language developed by Niklaus Wirth. It saw great favour as an initial teaching language, and persists.
• Perlin noise
  Ken Perlin.
  Perlin noise is a function for generating coherent noise over a space, meaning that for any two points in the space, the value of the noise function changes smoothly as you move from one point to the other.
• Petri nets
  Carl Petri.
  Widely used in the modelling of computer systems.
• Phong shading
  Phong Biu-Tuong.
  Phong shading is done by interpolating vertex normals across the surface of a polygon, or triangle, and illuminating the pixel at each point.
• Post's correspondence problem
  Emil Post.
  A correspondence problem in combinatorics, that is generally insoluble.
• Prewitt edge detector
  Judy Prewitt.
  A well known edge detector that computes an approximation to the first differential of the image intensity function.
• Python
  Monty Python.
  It is acknowledged that the programming language Python takes its name from the fictional TV character.
• Rice's theorem
  Henry Rice.
  Rice's theorem states that any non-trivial property of the partial function that is defined by an algorithm is undecidable.
• RSA encryption
  Ronald Rivest, Adi Shamir, Leonard Adleman.
  A widely known and used asymmetric encryption algorithm.
• Ruby's postulate
  Sam Ruby.
  The accuracy of metadata is inversely proportional to the square of the distance between the data and the metadata.
• Schwartzian transform
  Randal Schwartz.
  When sorting on a computed field, compute-then-sort to save on comparisons. Popularly used by Perl and Shell programmers.
• Shannon's theorem
  Claude Shannon (1916-2001).
  Shannon's fundamental and very famous Theorem gives an upper bound to the capacity of a link, in bits per second (bps), as a function of the available bandwidth and the signal-to-noise ratio of the link.
• Shell sort
  Donald Shell.
  The most efficient of the O(n2) class of sorting algorithms.
• Skolem constant
  Thoralf Skolem (1887-1963).
  A Skolem constant is a new constant that is substituted for a variable when eliminating an existential quantifier from a fact or a universal quantifier from a conjecture.
• Sobel edge detector
  Irwin Sobel.
  A primitive but effective highlighter in images of "edges" (sharp changes in intensity).
• Stigler's law
  Stephen Stigler.
  As applicable here as anywhere, Stigler's Law of Eponymy states that (on the Principle of Humility) no law, theorem, principle or phenomenon is named after the person who discovered it. Stigler is a statistician.
• Turing machine
  Alan Turing (1912-1954).
  A Turing machine is an abstract representation of a computing device. It consists of a read/write head that scans a (possibly infinite) one-dimensional (bi-directional) tape divided into squares, each of which is inscribed with a 0 or 1. Computation begins with the machine, in a given "state", scanning a square. It erases what it finds there, prints a 0 or 1, moves to an adjacent square, and goes into a new state. This behaviour is completely determined by three parameters: (1) the state the machine is in, (2) the number on the square it is scanning, and (3) a table of instructions.
• Turing test
  Alan Turing (1912-1954).
  If you can't tell the difference between machine behaviour and human behaviour, then the machine is "intelligent".
• Von Neumann architecture
  John von Neumann (1903-1957)
  Thge architecture of nearly all computer systems. There is some debate over whether von neumann really? gets the credit for this, but he published the essentials.
• Warnock's Dilemma
  Bryan Warnock.
  The act of choosing whether the lack of response to a discussion-list post is because of its brilliance (there's nothing to add) or because of its stupidity (it doesn't deserve comment). Like many such this originated on a Perl list.
• Warren Abstract Machine
  David Warren.
  Virtual memory architecture and instruction set into which Prolog is compiled.
• Wiener filter
  Norbert Wiener (1894-1964).
  An optimal filter used for the removal of noise from a signal which is corrupted by the measuring process itself.
• Zawinski's law
  Jamie Zawinski.
  "Every program attempts to expand until it can read mail. Those programs which cannot so expand are replaced by ones which can."

Back to Famous Computer Scientists.