4406 entries. 94 themes. Last updated December 26, 2016.

Computer Science / Computing Theory Timeline

Ancient Babylonian Algorithms: The Earliest Programs Circa 1,800 BCE – 1,600 BCE

In 1972 computer scientist and mathematician Donald E. Knuth published "Ancient Babylonian Algorithms," in which he provided the first English translations of various cuneiform mathematical tablets, with commentary. The tablets he studied ranged in date from 1800-1600 BCE. As a reflection of how comparatively little prestige computer science had as an academic subject at the time, Knuth began his paper with the statement:

"One of the ways to help make computer science respectable is to show that is deeply rooted in history, not just a short-lived phenomenon. Therefore it is natural to turn to the earliest surviving documents which deal with computation, and to study how people approached the subject nearly 4000 years ago."

From his paper I offer a few selections:

" 'Babylonian Programming'

"The Babylonian mathematicians were not limited simply to the processes of addition, subtraction, multiplication, and division; they were adept at solving many types of algebraic equations. But they did not have an algebraic notation that is quite as transparent as ours; they represented each formula by a set-by-step list of rules for its evaluation, i.e. by an algorithm for computing that formula. In effect, they worked with a 'machine language' representation of formulas instead of a symbolic language.

"The flavor of Babylonian mathematics can best be appreciated by studying several examples. The translations below attempt to render the words of the original texts as faithfully as possible into good English, without extensive editorial interpretation. Several remarks have been added in parentheses, to explain some of the things that were originally unstated on the tables. All numbers are presented Babylonian-style, i.e. without exponents, so the reader is warned that he will have to supply an appropriate scale factor in his head; thus, it is necessary to remember that I might mean 60 and 15 might mean 1/4.

"The first example that we shall discuss is excerpted from an Old-Babylonian tablet which was originally about 5 x 8 x 1 inches in size. Half of it now appears in the British Museum, about one-fourth appears in the Staatliche Museen, Berlin, and the other fourth has apparently been lost or destroyed over the years....

This is the procedure.

" The first step here is to divide 27, 46, 40 by 3,20; this is reduced to muliplication by the reciprocal. The multiplication was done by referring to tables, probably by manipulating stones or sand in some manner and then writing down the answer. The square root was also computed by referring to tables, since we know that many tables of n vs. existed. Note that the rule for computing the values of x and y such that x - y =d and xy = p ≠ (d/2).

"The calculations described in Babylonian tablets are not merely the solutions to specific individual problems; they are actually general procedures for solving a whole class of problems. The numbers shown are merely included as an aid to exposition, in order to clarify the general method. This fact is clear because there are numerous instances where a particular case of the general method reduces to multiplying by 1; such a multiplication is explicity carried out, in order to abide by the general rules. Note also the stereotyped ending, 'This is the procedure,' which is commonly found at the end of each section on a table. Thus the Babylonian procedures are genuine algorithms, and we can commend the Babylonians for developing a nice way to explain an algorithm by example as the algorithm itself was being defined.... (pp. 672-73).

Knuth, Ancient Babylonian Algorithms, Communications of the ACM 15, no. 7 (July 1972) 671-77.

Leibniz on Binary Arithmetic March 15, 1679 – 1705

A manuscript dated March 15, 1679 by Gottfried Wilhelm Leibniz, preserved in the Gottfried Wilhelm Leibniz, Bibliothek Niedersächsische Landesbibliothek, Hannover, “includes a brief discussion of the possibility of designing a mechanical binary calculator which would use moving balls to represent binary digits.”

Though Leibniz thought of the application of binary arithmetic to computing in 1679, the machine he outlined was never built, and he published nothing on the subject until his Explication de l'arithmétique binaire, qui se sert des seuls caracteres 0 & 1; avec des remarques sur son utilité, & sur ce qu'elle donne le sens des anciens figues Chinoises de Fohy' published in Histoire de l'Académie Royale des Sciences année MDCCIII. Avec les mémoires de mathématiques, which appeared in print in 1705.

"The publication of the Explication was prompted by Leibniz's correspondence with Joachim Bouvet, a member of the Jesuit Mission in China. Leibniz had developed an interest in China, and in April 1697 he edited a collection of letters and essays by members of the Mission, entitled Novissima Sinica. A copy of this came into the hands of Bouvet, who wrote to Leibniz on 18 October 1697 expressing his commendation of the work. Thus began an extended correspondence between the two men which proved to be very important for the dissemination of Leibniz's ideas about binary arithmetic. The crucial exchange began on 15 February 1701, when Leibniz wrote to Bouvet describing for his correspondent the principles of his binary arithmetic, including the analogy of the formation of all the numbers from 0 and 1 with the creation of the world by God out of nothing. Bouvet immediately recognised the relationship between the hexagrams of the I ching and the binary numbers and he communicated his discovery in a letter written in Peking on 4 November 1701. This reached Leibniz, after a detour through England, on 1 April 1703. With this letter, Bouvet enclosed a woodcut of the arrangement of the hexagrams attributed to Fu-Hsi, the mythical founder of Chinese culture, which holds the key to the identification. Within a week of receiving Bouvet's letter, Leibniz had sent to Abbé Bignon for publication in the Mémoires of the Paris Academy his Explication de l'Arithmétique binaire,... & sue ce qu'elle donne le sens des anciens figures Chinoises de Fohy. Ten days later he sent a brief account to Hans Sloane, the Secretary of the Royal Society. Leibniz viewed binary arithmetic less as a computational tool than as a means of discovering mathematical, philosophical and even theological truths. He remarked to Tschirnhaus in 1682 that he anticipated from the use of binary numbers discoveries in number theory that other progressions could not reveal. It was at the same time a candidate for the characteristica generalis, his long sought-for alphabet of human thought. With base 2 numeration Leibniz witnessed a confluence of several intellectual strands in his world view, including theological and mystical ideas of order, harmony and creation. Fontanelle, secretary of the Paris Academy, wrote the unsigned review of Liebniz's paper for the Mémoires section of the volume. He noted that arithmetic could have different bases besides ten; bases such as 12, and two as in the case of Leibniz's binary system. He also noted that although the binary system was not practical for common use Leibniz thought that it would be of advantage in advanced mathematics" (W.P. Watson, antiquarian book description, accessed from ilabdatabase.com on 01-21-2010).

This manuscript was first published in 1966 to commemorate the 250th anniversary of Leibniz's death as Herrn von Leibniz' Rechnung mit Null und Eins. That book included facsimiles of Leibniz's "Explication de l'arithmétique binaire" (1705), his two letters to Johann Christian Schulenberg on binary arithmetic (March 29 and May 17, 1698), published in the Opera Omnia of 1768, and historical articles and German translations.

(This entry was last revised on 07-26-2014.)

Thomas Simpson Publishes the Earliest Formal Treatment of "Data-Processing" 1755

In 1755 English mathematician Thomas Simpson published "On the Advantage of Taking the Mean of a Number of Observations, in Practical Astronomy" in the Philosophical Transactions of the Royal Society 49, part 1, 82-93.  Simpson's paper was "a milestone in statistical inference, as well as the earliest formal treatment of any data-processing practice" (Hook & Norman, Origins of Cyberspace [2002] No. 16).

Babbage Describes the Logic and Operation of Machinery by Means of Notation 1826

In 1826 mathematician and engineer Charles Babbage published "On a Method of Expressing by Signs the Action of Machinery," Philosophical Transactions 111 (1826) 250-65, 4 plates. This was the first publication of Babbage's exposition of his system of mechanical notation that enabled him to describe the logic and operation of his machines on paper as they would be fabricated in metal. Babbage later stated that "Without the aid of this language I could not have invented the Analytical Engine; nor do I believe that any machinery of equal complexity can ever be contrived without the assistance of that or of some other equivalent language. The Difference Engine No. 2 . . . is entirely described by its aid" (Babbage, Passages from the Life of a Philosopher [1864], 104).

Babbage considered his mechanical notation system to be one of his finest inventions, and thought it should be widely implemented. It was a source of frustration to him that no other machine designer adopted it (probably because no other engineer during Babbage's time attempted to build machines as logically and mechanically complex as Babbage's). More than one hundred years later, in the 1930s, when developments in logic were applied to switching systems in the earliest efforts to develop electromechanical calculators, Claude Shannon demonstrated that Boolean algebra could be applied to the same types of problems for which Babbage had designed his mechanical notation system.

"While making designs for the Difference Engine, Babbage found great difficulty in ascertaining from ordinary drawings-plans and elevations-the state of rest or motion of individual parts as computation proceeded: that is to say in following in detail succeeding stages of a machine's action. This led him to develop a mechanical notation which provided a systematic method for labeling parts of a machine, classifying each part as fixed or moveable; a formal method for indicating the relative motions of the several parts which was easy to follow; and means for relating notations and drawings so that they might illustrate and explain each other. As the calculating engines developed the notation became a powerful but complex formal tool. Although its scope was much wider than logical systems, the mechanical notation was the most powerful formal method for describing switching systems until Boolean algebra was applied to the problem in the middle of the twentieth century. In its mature form the mechanical notation was to comprise three main components: a systematic method for preparing and labeling complex mechanical drawings; timing diagrams; and logic diagrams, which show the general flow of control" (Hyman, Charles Babbage [1982], 58).

Hook & Norman, Origins of Cyberspace (2001) no. 37.

Luigi Menabrea Publishes the First Computer Programs, Designed for Babbage's Analytical Engine. Ada Lovelace Translates them Into English 1840 – 1843

In 1842 Italian mathematician and politician Luigi Federico Menabrea published "Notions sur la machine analytique de M. Charles Babbage" in Bibliothèque universelle de Genève, nouvelle série 41 (1842) 352–76. This was the first published account of Charles Babbage’s Analytical Engine and the first account of its logical design, including the first examples of computer programs ever published. As is well known, Babbage’s conception and design of his Analytical Engine—the first general purpose programmable digital computer—were so far ahead of the imagination of his mathematical and scientific colleagues that few expressed much curiosity regarding it. Babbage first conceived the Analytical Engine in 1834. This general-purpose mechanical machine— never completely constructed—embodied in its design most of the features of the general-purpose programmable digital computer. In its conception and design Babbage incorporated ideas and names from the textile industry, including data and program input, output, and storage on punched cards similar to those used in Jacquard looms, a central processing unit called the "mill," and memory called the "store."The only presentation that Babbage made concerning the design and operation of the Analytical Engine was to a group of Italian scientists.

In 1840 Babbage traveled to Torino (Turin) Italy to make a presentation on the Analytical Engine. Babbage’s talk, complete with charts, drawings, models, and mechanical notations, emphasized the Engine’s signal feature: its ability to guide its own operations—what we call conditional branching. In attendance at Babbage’s lecture was the young Italian mathematician Luigi Federico Menabrea (later prime minister of Italy), who prepared from his notes an account of the principles of the Analytical Engine. Reflecting a lack of urgency regarding radical innovation unimaginable to us today, Menabrea did not get around to publishing his paper until two years after Babbage made his presentation, and when he did so he published it in French in a Swiss journal. Shortly after Menabrea’s paper appeared Babbage was refused government funding for construction of the machine.

"In keeping with the more general nature and immaterial status of the Analytical Engine, Menabrea’s account dealt little with mechanical details. Instead he described the functional organization and mathematical operation of this more flexible and powerful invention. To illustrate its capabilities, he presented several charts or tables of the steps through which the machine would be directed to go in performing calculations and finding numerical solutions to algebraic equations. These steps were the instructions the engine’s operator would punch in coded form on cards to be fed into the machine; hence, the charts constituted the first computer programs [emphasis ours]. Menabrea’s charts were taken from those Babbage brought to Torino to illustrate his talks there"(Stein, Ada: A Life and Legacy, 92).

Menabrea’s 23-page paper was translated into English the following year by Lord Byron’s daughter, Augusta Ada King, Countess of Lovelace, daughter of Lord Byron, who, in collaboration with Babbage, added a series of lengthy notes enlarging on the intended design and operation of Babbage’s machine. Menabrea’s paper and Ada Lovelace’s translation represent the only detailed publications on the Analytical Engine before Babbage’s account in his autobiography (1864). Menabrea himself wrote only two other very brief articles about the Analytical Engine in 1855, primarily concerning his gratification that Countess Lovelace had translated his paper.

Hook & Norman, Origins of Cyberspace (2002) No. 60.

"Without being Worked out by Human Head & Hands. . . ."

While she was working on her translation, on July 10, 1843 Ada Lovelace composed a letter to Babbage concerning her notes to Menabrea's paper on programming Babbage's Analytical Engine. This autograph letter, preserved in the British Library (Add. MS 37192 folios 362v-363), includes the following text:

"I want to put in something about Bernouilli's Numbers, in one of my Notes, as an example of how an implicit function may be worked out by the engine, without  having been worked out by human head & hands first. Give me the necessary data and formulae."

The letter is notable for suggesting that Ada's knowledge of mathematics was limited, and that she may have mainly contributed poetic language to her annotations of the English translation of Menabrea's key paper, while incorporating mathematical examples written by Babbage. Because of Ada's fame as Byron's daughter, and her social position as the Countess of Lovelace, Babbage hoped that Ada's translation and annotation of Menabrea's paper would help promote building the Analytical Engine.

In October 1843, Ada Lovelace's "Sketch of the Analytical Engine Invented by Charles Babbage . . . with Notes by the Translator" was published in Scientific Memoirs, Selected from the Transactions of Foreign Academies of Science and Learned Societies 3 (1843): 666-731 plus 1 folding chart. At Babbage’s suggestion, Lady Lovelace added seven explanatory notes to her translation, which run about three times the length of the original. Her annotated translation has been called “” (Bromley, “Introduction” in Babbage, Henry Prevost, , xv). As Babbage never published a detailed description of the Analytical Engine, Ada’s translation of Menabrea’s paper, with its lengthy explanatory notes, represents the most complete contemporary account in English of this much-misunderstood machine.

At Babbage’s suggestion, Lady Lovelace added seven explanatory notes to her translation, which run about three times the length of the original. Her annotated translation has been called “the most important paper in the history of digital computing before modern times” (Bromley, “Introduction” in Babbage, Henry Prevost, Babbage’s Calculating Engines, xv). As Babbage never published a detailed description of the Analytical Engine, Ada’s translation of Menabrea’s paper, with its lengthy explanatory notes, represents the most complete contemporary account in English of this much-misunderstood machine.

"Babbage supplied Ada with algorithms for the solution of various problems, which she illustrated in her notes in the form of charts detailing the stepwise sequence of events as the machine progressed through a string of instructions input from punched cards" (Swade, The Cogwheel Brain, 165).

These were the first published examples of  computer “programs,” though neither Ada nor Babbage used this term. She also expanded upon Babbage’s general views of the Analytical Engine as a symbol-manipulating device rather than a mere processor of numbers, suggesting that it might act upon other things besides number, were objects found whose mutual fundamental relations could be expressed by those of the abstract science of operations. . . . Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent (p. 694) . . . Many persons who are not conversant with mathematical studies, imagine that because the business of the engine is to give its results innumerical notation, the nature of its processes must consequently be arithmetical and numerical, rather than algebraical and analytical. This is an error. The engine can arrange and combine its numerical quantities exactly as if they were letters or any other general symbols; and in fact it might bring out its results in algebraical notation, were provisions made accordingly (p. 713).

Much has been written concerning what mathematical abilities Ada may have possessed. Study of the published correspondence between her and Babbage is not especially flattering either to her personality or mathematical talents: it shows that while Ada was personally enamored of her own mathematical prowess, she was in reality no more than a talented novice who at times required Babbage’s coaching. Their genuine friendship aside, Babbage’s motives for encouraging Ada’s involvement in his work are not hard to discern. As Lord Byron’s only legitimate daughter, Ada was an extraordinary celebrity, and as the wife of a prominent aristocrat she was in a position to act as patron to Babbage and his engines, though she never did so.

The First Published Computer Programs, Translated and Augmented by Lord Byron's Daughter October 1843

In October 1843, Augusta Ada King, Countess of Lovelace, daughter of Lord Byron, translated Menabrea’s paper, "Notions sur la machine analytique de M. Charles Babbage" (1842).  Her "Sketch of the Analytical Engine Invented by Charles Babbage . . . with Notes by the Translator" published in Scientific Memoirs, Selected from the Transactions of Foreign Academies of Science and Learned Societies 3 (1843): 666-731 plus 1 folding chart, was the first edition in English of the the first published account of Babbage’s Analytical Engine, and, more significantly, of its logical design.

In 1840 Babbage traveled to Torino to present to a group of Italian scientists an account of the Engine. Babbage’s talk, complete with drawings, models and mechanical notations, emphasized the Engine’s signal feature: its ability to guide its own operations. It also included the first computer programs though Babbage did not use that word. In attendance at Babbage’s lecture was the young Italian mathematician Luigi Federico Menabrea (later Prime Minister of Italy), who prepared from his notes an account of the principles of the Analytical Engine, which he published in French in 1842.

In keeping with the more general nature and immaterial status of the Analytical Engine, Menabrea’s account dealt little with mechanical details. Instead he described the functional organization and mathematical operation of this more flexible and powerful invention. To illustrate its capabilities, he presented several charts or tables of the steps through which the machine would be directed to go in performing calculations and finding numerical solutions to algebraic equations. These steps were the instructions the engine’s operator would punch in coded form on cards to be fed into the machine; hence, the charts constituted the first computer programs. Menabrea’s charts were taken from those Babbage brought to Torino to illustrate his talks there (Stein, Ada: A Life and Legacy, 92).

Menabrea’s paper was translated into English by Babbage’s close friend Ada, Countess of Lovelace, daughter of the poet Byron and a talented mathematician in her own right. At Babbage’s suggestion, Lady Lovelace added seven explanatory notes to her translation, which run about three times the length of the original. Her annotated translation has been called “the most important paper in the history of digital computing before modern times” (Bromley, “Introduction” in Babbage, Henry Prevost, Babbage’s Calculating Engines, xv). As Babbage never published a detailed description of the Analytical Engine, Ada’s translation of Menabrea’s paper, with its lengthy explanatory notes, represents the most complete contemporary account in English of this much-misunderstood machine.

Babbage supplied Ada with algorithms for the solution of various problems, which she illustrated in her notes in the form of charts detailing the stepwise sequence of events as the machine progressed through a string of instructions input from punched cards (Swade, The Cogwheel Brain, 165). This was the first published example of a computer “program,” though neither Ada nor Babbage used this term. She also expanded upon Babbage’s general views of the Analytical Engine as a symbol-manipulating device rather than a mere processor of numbers, suggesting that it might act upon other things besides number, were objects found whose mutual fundamental relations could be expressed by those of the abstract science of operations. . . . Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent (p. 694) . . . Many persons who are not conversant with mathematical studies, imagine that because the business of the engine is to give its results in numerical notation, the nature of its processes must consequently be arithmetical and numerical, rather than algebraical and analytical. This is an error. The engine can arrange and combine its numerical quantities exactly as if they were letters or any other general symbols; and in fact it might bring out its results in algebraical notation, were provisions made accordingly (p. 713).

Much has been written concerning what mathematical abilities Ada may have possessed. Study of the published correspondence between her and Babbage (see Toole 1992) is not especially flattering either to her personality or mathematical talents: it shows that while Ada was personally enamored of her own mathematical prowess, she was in reality no more than a talented novice who at times required Babbage’s coaching. Their genuine friendship aside, Babbage’s motives for encouraging Ada’s involvement in his work are not hard to discern. As Lord Byron’s only legitimate daughter, Ada was an extraordinary celebrity, and as the wife of a prominent aristocrat she was in a position to act as patron to Babbage and his engines (though she never in fact did so).

George Boole Develops Boolean Algebra 1847 – 1854

In 1847 English mathematician and philosopher George Boole published a pamphlet entitled The Mathematical Analysis of Logichis first exposition of Boolean algebra. Seven years later in 1854, Boole published a much longer exposition entitled An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities. This work contains the full expression of the first practical system of logic in algebraic form.

"He [Boole] did not regard logic as a branch of mathematics, as the title of his earlier pamphlet [The Mathematical Analysis of Logic (1847)] might be taken to imply, but he pointed out such a deep analogy between the symbols of algebra and those which can be made, in his opinion, to represent logical forms and syllogisms, that we can hardly help saying that (especially his) formal logic is mathematics restricted to the two quantities, 0 and 1. By unity Boole denoted the universe of thinkable objects; literal symbols, such as x, y, z, v, u, etc., were used with the elective meaning attaching to common adjectives and substantives. Thus, if x=horned and y=sheep, then the successive acts of election represented by x and y, if performed on unity, give the whole of the class horned sheep. Boole showed that elective symbols of this kind obey the same primary laws of combination as algebraic symbols, whence it followed that they could be added, subtracted, multiplied and even divided, almost exactly in the same manner as numbers. Thus, (1 - x) would represent the operation of selecting all things in the world except horned things, that is, all not horned things, and (1 - x) (1 - y) would give us all things neither horned nor sheep. By the use of such symbols propositions could be reduced to the form of equations, and the syllogistic conclusion from two premises was obtained by eliminating the middle term according to ordinary algebraic rules.

"Still more original and remarkable, however, was that part of his system, fully stated in his Laws of Thought, formed a general symbolic method of logical inference. Given any propositions involving any number of terms, Boole showed how, by the purely symbolic treatment of the premises, to draw any conclusion logically contained in those premises. The second part of the Laws of Thought contained a corresponding attempt to discover a general method in probabilities, which should enable us from the given probabilities of any system of events to determine the consequent probability of any other event logically connected with the given events" (Wikipedia article on George Boole, accessed 01-09-2008).

Though the audience for Boole's highly specialized work would have been judged to be small, and the edition size reduced accordingly, the existence of three issues of the first edition, all dated 1854, would suggest that the edition may have required several years to sell. The points of the issues are as follows:

1. Probable first issue: London: Walton and Maberly, Upper Gower-Street, and Ivy Lane, Paternoster-Row. Cambridge: Macmilan and Co., errata leaf bound in the back, and binding of black zigzag cloth with blindstamped border, panel, central lozenge and corner and side ornaments.

2. Probable second issue: London: Walton and Maberly as above, but with the errata after the last numbered leaf of preliminaries, an additional printed "Note" leaf following 2E4 concerning a more complex error, an eight-page Walton and Maberly catalogue of "Educational Works and Works in Science and General Literature" and a binding of black blind-panelled zigzag cloth without the central lozenge.

3. Third issue: London: Macmillan and Co. Errata on recto of last unsigned leaf, and bound in green cloth, gilt-lettered spine. This may be a later, or remainder binding

Hook & Norman, The Haskell F. Norman Library of Science and Medicine (1991) no. 266.

Babbage's "Passages from the Life of a Philosopher" 1864

In 1864 English mathematician, engineer and computer designer Charles Babbage published his autobiography, Passages from the Life of a Philosopher, in which he presented the most detailed descriptions of his Difference and Analytical Enginespublished during his lifetime, and wrote about his struggles to have his highly futuristic inventions appreciated by society.

In the wording of his title Babbage used the word philosopher in its now obsolete sense of what we call a "scientist." The word scientist, coined by William Whewell, was not widely used until the end of the 19th or early 20th century. (See Reading 6.2.)

Maxwell's "On Governors" : Exposition on Feedback Mechanisms 1868

In 1868 Scottish physicist and mathematician James Clerk Maxwell published “On Governors,” a classic paper on feedback mechanisms.

William Stanley Jevons Constructs the First Logic Machine to Solve Complicated Problems Faster than Man 1870

In 1870 English mathematician and economist William Stanley Jevons constructed his “logical piano,” the first logic machine to solve complicated problems with superhuman speed.  Jevons described his machine in "On the mechanical performance of logical inference," Philosophical Transactions of the Royal Society 160 (1870), 497-518 with 3 plates.

First demonstrated before the Royal Society in 1870, the original logical piano is still on display in the Museum of the History of Science, Oxford. The internal structure of the machine is illustrated in the three plates accompanying Jevons' paper, which provide a reasonable guide to its construction. Jevons was a pioneer of symbolic logic, and his paper includes a detailed explanation of his system of equational logic, which derived from (and in some important ways improved) the symbolic logic devised by Boole over two decades earlier.

Gardner, Logic Machines and Diagrams, 91-103. Schabas, A World Ruled by Number, 54ff. Lee, Computer Pioneers, 400-401. Randell, The Origins of Digital Computers,  479.

Charles Sanders Pierce Recognizes that Logical Operations Could be Carried Out by Electrical Switching Circuits 1886

In 1886 American American philosopher, logician, mathematician, and scientist Charles Sanders Peirce recognized that logical operations could be carried out by electrical switching circuits. This idea he mentioned in a letter to his former student Allan Marquand

Prior to receiving Peirce's letter, in 1881-82, inspired by William Stanley Jevons' logical piano, Marquand built a mechanical logical machine that is still exant according to the Wikipedia article on Marquand. Marquand first published a description of his mechanical machine in 1885. After receiving Peirce's letter, in 1887 Marquand "outlined a machine to do logic using electric circuits. This necessitated his development of Marquand diagrams" (Wikipedia article on Allan Marquand, accessed 10-08-2013).

In October 2013 history-computer.com reproduced a circuit diagram for the electromagnetic logical machine in Marquand's archive that was made about 1890. Other than diagrams of this kind there is no evidence that Marchand or Peirce ever built an electrical logic machine.

The Peirce-Marquand communication or collaboration on the use of electrical switching circuits to carry out logical operations is a remarkable precursor of ideas later developed by Claude Shannon in his thesis of 1937.

(This entry was last revised on 02-23-2016.)

The Most Complete Work on Babbage's Computers 1889

Charles Babbage’s son Henry Prevost Babbage completed and published his father’s unfinished edition of writings on the Difference Engine No. 1 and the Analytical Engine, together with a listing of his father’s unpublished plans and notebooks. These appear under the title of Babbage’s Calculating Engines.

This work was the principal source of information for the technical operation of Babbage’s Difference and Analytical engines. Toward the end of his life, Babbage began assembling his own and other’s previously published writings on his Difference and Analytical Engines with the intent of publishing a history of his work designing the machines, and descriptions of the way that the machines would operate. However, Babbage died before he could accomplish this task. He had the first 294 pages of this work typeset and printed on slightly varying qualities of paper during his lifetime. The differences in the paper used for portions of the work would suggest that sections were printed intermittently rather than all at one time. It would appear that Babbage’s purpose in producing this work was to collect the most significant published writings on his calculating engines, most of which had appeared as obscure pamphlets or in little-read journals, together with a listing of what remained unpublished, including all of Babbage’s notebooks and engineering drawings (listed on pp. 271-294), in the hope that his unfinished projects might be completed at some future date.

Almost twenty years after Babbage’s death, his youngest son, Major-General Henry Prevost Babbage, to whom Babbage had bequeathed his parts for his calculating engines, and everything else pertaining to them, completed the book, incorporating the printed sheets that Babbage had produced along with concluding material, reflecting his own frustrated efforts to effect realization of Babbage’s engines. Were it not for this volume, and for the bibliography of Babbage’s works published both here (on the last three printed pages of the book) and in Babbage’s autobiography, Babbage’s achievements might have been forgotten. Henry Babbage also completed six small demonstration pieces of the Difference Engine No. 1, and in 1910 at the age of 86, Henry Babbage also completed an experimental four-function calculator for the Mill for the Analytical Engine.  This was the only portion of the Analytical Engine that was ever produced in metal.

As it turned out Babbage’s designs were not implemented until the 20th century because in the era of human computers there was no pressing need for the machines that Babbage envisioned and designed. Yet because of these published works, Babbage’s ambitions and his ideas remained alive in the minds of people working in mechanical computation long after his technology had fallen into obsolescence. When Vannevar Bush suggested in 1936 that electromechanical technology might be the way to realize “Babbage’s large conception” of the Analytical Engine, he cited this volume among his references; and in building the electromechanical Harvard Mark I, Howard Aiken saw himself fulfilling Babbage’s ambition. However, some experts have inferred that Aiken’s knowledge of Babbage’s work may have been limited to what he read in Babbage’s autobiography, Passages from the Life of a Philosopher, as Aiken did not include conditional branching in the design of the Mark I—a key idea that Babbage designed into the Analytical Engine.

Hyman, Charles Babbage, Pioneer of the Computer, 254. Van Sinderen, Alfred W. "The Printed Papers of Charles Babbage" Annals of the History of Computing, 2 (April 1980) :169-185 mentions in item CB80, that Babbage listed a History of the Analytical Engine as being “in the press” in 1864.

David Hilbert's "Mathematische Probleme" 1900

In 1900, at the beginning of a new century, German mathematician and physicist David Hilbert of the University of Göttingen published in Mathematische Probleme a list of twenty-three problems that he predicted would be of central importance to the advance of mathematics in the twentieth century.

In the second of these problems Hilbert called for a mathematical proof of the consistency of the arithmetic axioms—a question that influenced both the development of mathematical logic and computing.

Hilbert's paper was first published in Nachrichten der Königliche Gesellschaft zur Wissenschaften zu Göttingen, Mathematische-physikalischen Klasse, 3 (1900).

Hook & Norman, Origins of Cyberspace (2002) no. 320.

Torres y Quevedo Invents the First Decision-Making Automaton 1912 – 1915

In 1912 Spanish civil engineer and mathematician, and Director of the Laboratory of Applied Mechanics at the Ateneo Científico, Literario y Artístico de MadridLeonardo Torres y Quevedo built the first decision-making automaton — a chess-playing machine that pit the machine’s rook and king against the king of a human opponent.  Torres's machine, which he called El Ajedrecista (The Chessplayer) used electromagnets under the board to "play" the endgame rook and king against the lone king.

"Well, not precisely play. But the machine could, in a totally unassisted and automated fashion, deliver mate with King and Rook against King. This was possible regardless of the initial position of the pieces on the board. For the sake of simplicity, the algorithm used to calculate the positions didn't always deliver mate in the minimum amount of moves possible, but it did mate the opponent flawlessly every time. The machine, dubbed El Ajedrecista (Spanish for “the chessplayer”), was built in 1912 and made its public debut during the Paris World Fair of 1914, creating great excitement at the time. It used a mechanical arm to make its moves and electrical sensors to detect its opponent's replies." (http://www.chessbase.com/newsprint.asp?newsid=1799, accessed 10-31-2012).

The implications of Torres's machines were not lost on all observers. On November 6, 1915 Scientific American magazine in their Supplement 2079 pp. 296-298 published an illustrated article entitled "Torres and his Remarkable Automatic Devices. He Would Substitute Machinery for the Human Mind."

Lowenheim's Contribution to the Lowenheim-Skolem Theorem 1915

In 1915 German mathematician Leopold Löwenheim of Berlin published Über Möglichkeiten im Relativkalkül, containing the first appearance of what is now known as the Löwenheim-Skolem theorem, the first theorem of modern logic, anticipating Kurt Gödel’s completeness theorem of 1930. Löwenheim's paper was first published in Mathematischen Annalen 76 (1915) 447-470. A summary and English translation are in van Heijenoort, From Frege to Gödel (1967) 228-51.

Skolem's Contribution to the Lowenheim-Skolem Theorem 1920

In 1920 Norwegian mathematician Thoraf Albert Skolem of the University of Oslo proved the Lowenheim-Skolem theorem, a landmark in mathematical logic. Skolem's paper was first published as "Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen", Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse 6 (1920) 1–36.

Hook & Norman, Origins of Cyberspace (2002) No. 365. An English translation of Skolem's paper appears in van Heijenoort, From Frege to Gödel (1967) 254-63.

Hilbert Asks, Is Mathematics Complete, is it Consistent, and is it Decidable? 1928

At the International Congress of Mathematicians held in Bologna, Italy, in 1928 mathematician and physicist David Hilbert returned to the second of the twenty-three problems posed in his 1900 paper Mathematische Probleme, asking is mathematics complete, is it consistent, and is it decidable?

Three years later, the first two of these questions were answered in the negative by Kurt Gödel. Working independently, Alonzo Church, Alan Turing, and Emil Post published answers to the third question in 1936.

Hilbert's paper was first published in Atti del Congresso Internazionale dei Matematici, Bologna 3-10 settembre 1928 (VI) I (1929) 135-41.

Hook & Norman, Origins of Cyberspace (2002) no. 320.

Von Neumann Invents the Theory of Games 1928

In 1928 Hungarian-American mathematician, physicist, economist and polymath John von Neumann then working at Humboldt-Universität zu Berlin, published "Zur Theorie der Gesellschaftsspiele" in Mathematische Annalen, 100, 295–300. This paper "On the Theory of Parlor Games" propounded the minimax theorem, inventing the theory of games.

Godel's Incompleteness Theorems 1931

In 1931 Austrian logician, mathematician and philosopher Kurt Gödel published while in Vienna Über formal unentscheidbare Sätze der "Principia Mathematica" und verwandter Systeme (called in English "On Formally Undecidable Propositions of 'Principia Mathematica' and Related Systems"). That article dated November 17, 1930, which first appeared in the 1931 volume of Monatshefte für Mathematik, contained Godel's first and second incompleteness theorems

van Heijenoort, ed. From Frege to Gödel: A Source Book on Mathematical Logic 1879–1931 (1967) 592-617.

Key Contributions of Konrad Zuse to the History of Computer Design and Software 1934 – 1958

Konrad Zuse made numerous original contributions to computer design and software that predated American and English developments, but because Zuse worked in Nazi Germany his ideas were unknown outside of Germany until well after World War II, and thus had no influence on the development of the computer industry in America and England. While completing his engineering degree at the Technische Universität Berlin in 1934, Zuse,realized that an automatic calculator would need only a control, a memory, and an arithmetic unit. On April 11, 1936 Zuse applied for a patent on his electromagnetic, program-controlled calculator, called the Z1, which he built in the living room of his parents’ apartment in Berlin. Zuse completed the ZI, which had 30,000 parts, in 1938. Independently of Claude Shannon, Zuse developed a form of symbolic logic to assist in the design of the binary circuits

The Z1 was the first freely programmable, binary-based calculating machine ever built, but it did not function reliably, and it was destroyed in World War II. Zuse's patent application is the only surviving documentation of Zuse's prewar work on computers. Between 1986 and 1989 Zuse and three associates created a replica of the Z1, which is preserved in the Deutsche Technikmuseum, Berlin.

With his associate Helmut Schreyer, Zuse began work on his Z2 shortly after completing the Z1. In 1939 the men completed the Z2 machine in Berlin. It used the same kind of mechanical memory as the Z1, but used 800 relays in the arithmetic and control units. On October 15, 1939 Helmut Schreyer wrote a memorandum concerning the Z2, Rechnische Rechenmachine (unpublished at the time), in which he stated that it would be possible to build a computer with vacuum tubes that would process “10,000 operations per second.” This memorandum and the rest of Zuse's and Schreyer's ideas only became known in the west after World War II.

In 1940 the German government began funding Zuse's work through the Aerodynamische Versuchsanstalt (AVA, Aerodynamic Research Institute, forerunner of the Deutsches Zentrum für Luft- und Raumfahrt e.V, DLR). At this time Zuse built the S1 and S2 computers —special purpose machines for computing aerodynamic corrections to the wings of radio-controlled flying bombs.

"The S2 featured an integrated analog-to-digital converter under program control, making it the first process-controlled computer. These machines contributed to the Henschel Werke Hs 293 and Hs 294 guided missiles developed by the German military between 1941 and 1945, which were the precursors to the modern cruise missile. The circuit design of the S1 was the predecessor of Zuse's Z11. Zuse believed that these machines had been captured by occupying Soviet troops in 1945" (Wikipedia article on Konrad Zuse, accessed 03-03-2012).

Continuing to work in Berlin, with the assistance of Helmut Shreyer, Zuse completed his Z3 machine on May 12, 1941. This was the world’s first fully functional Turing-complete electromechanical digital computer—with twenty-four hundred relays. The Z3 ran programs punched into rolls of discarded movie film. In 1944 it was destroyed in bombing raids. Also in 1941 Schreyer received his doctorate in telecommunications engineering from the Technische Universität Berlin with a dissertation on the use of vacuum-tube relays in switching circuits. Schreyer converted Zuse’s logical designs into electronic circuits, building a simple prototype of an electronic computer with 100 vacuum tubes, which achieved a switching frequency of 10,000 Hz. Because no one outside of Germany had any knowledge of the Z3, Zuse's design had no influence on the development of computing in the the United States or England during or after World War II. In 2012 there was a replica of the Z3 on display in the Deutsches Museum, Munich.

In 1942 Zuse started work on the Z4 electromechanical computer in Berlin, completing the work shortly before V-E Day in 1945. Built by his company, Zuse Apparatebau, the Z4 was the world's first commercial digital computer. To safeguard it against bombing, the machine was dismantled and shipped from Berlin to a village in the Bavarian Alps. In 1950 it was refurbished, modified, and installed at ETH in Zurich. For several years it was the only working electronic digital computer in continental Europe, and it remained operational in Zurich until 1955. It is preserved in the Deutsches Museum in Munich.

"The Z4 was very similar to the Z3 in its design but was significantly enhanced in a number of respects. The memory consisted of 32-bit rather than 22-bit floating point words. A special unit called the Planfertigungsteil (program construction unit), which punched the program tapes made programming and correcting programs for the machine much easier by the use of symbolic operations and memory cells. Numbers were entered and output as decimal floating point even though the internal working was in binary. The machine had a large repertoire of instructions including square root, MAX, MIN and sign. Conditional tests included tests for infinity. When delivered to ETH Zurich the machine had a conditional branch facility added and could print on a Mercedes typewriter. There were two program tapes where the second could be used to hold a subroutine (originally six were planned).

"In 1944 Zuse was working on the Z4 with around two dozen people, including several women. Some engineers who worked at the telecommunications facility of the OKW also worked for Zuse as a secondary occupation. To prevent it from falling into the hands of the Soviets, the Z4 was evacuated from Berlin in February 1945 and transported to Göttingen. The Z4 was completed in Göttingen in a facility of the Aerodynamische Versuchsanstalt (AVA, Aerodynamic Research Institute), which was headed by Albert Betz. But when it was presented to scientists of the AVA the roar of the approaching front could already be heard, so the computer was transported with a truck of the Wehrmacht to Hinterstein in Bad Hindelang, where Konrad Zuse met Wernher von Braun" (Wikipedia article on Z4, accessed 01-01-2015).

For the Z4 Zuse developed Plankalkül, the first "high-level" non-von Neumann programming language. Some of his earliest notes on the topic date to 1941. The language was well-developed by 1945. Because of war time secrecy, and Zuse's efforts to commercialize the Z3 computer and its sucessors, Zuse did not publish anything on Plankalkühl at the time he developed it. Zuse wrote a book on the subject in 1946 but this remained unpublished until it was edited many years later for Internet publication. In 1948 he published a summary paper,  "Über den Allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben", Archiv der Mathematik I (1948) 441-449. However, this did not attract much attention.

" . . . for a long time to come programming a computer would only be thought of as programming with machine code. The Plankalkül was eventually more comprehensively published in 1972 and the first compiler for it was implemented in 1998. Another independent implementation followed in the year 2000 by the Free University of Berlin" (Wikipedia article on Plankalkühl, accessed 12-04-2011).

Because of his Nazi affiliation Zuse was not allowed to get back into the computer industry until the 1950s. In 1958 he produced the Z22, the first commercial electronic digital computer produced in Germany. The Z22 used vacuum tubes—a relatively late date for that technology, as most American computer companies switched to solid state by 1957. Zuse's company, Zuse KG, became the first independent German electronic computer company. It was eventually purchased by Siemens.

Alonzo Church Proves Undecidability 1936

In 1936 American mathematician and logician Alonzo Church of Princeton published his logical proof of the undecidability of arithmetic, using his lambda calculus.

Alan Turing Publishes "On Computable Numbers," Describing What Came to be Called the "Turing Machine" November 30, 1936

In issues dated November 30 and December 23, 1936 of the Proceedings of the London Mathematical Society English mathematician Alan Turing published "On Computable Numbers", a mathematical description of what he called a universal machine— an astraction that could, in principle, solve any mathematical problem that could be presented to it in symbolic form. Turing modeled the universal machine processes after the functional processes of a human carrying out mathematical computation. In the following issue of the same journal Turing published a two page correction to his paper.

Undoubtedly the most famous theoretical paper in the history of computing, "On Computable Numbers" is a mathematical description an imaginary computing device designed to replicate the mathematical "states of mind" and symbol-manipulating abilities of a human computer. Turing conceived of the universal machine as a means of answering the last of the three questions about mathematics posed by David Hilbert in 1928: (1) is mathematics complete; (2) is mathematics consistent; and (3) is mathematics decidable.

Hilbert's final question, known as the Entscheidungsproblem, concerns whether there exists a defiinite method—or, in the suggestive words of Turing's teacher Max Newman, a "mechanical process"—that can be applied to any mathematical assertion, and which is guaranteed to produce a correct decision as to whether that assertion is true. The Czech logician Kurt Gödel had already shown that arithmetic (and by extension mathematics) was both inconsistent and incomplete. Turing showed, by means of his universal machine, that mathematics was also undecidable.

To demonstrate this, Turing came up with the concept of "computable numbers," which are numbers defined by some definite rule, and thus calculable on the universal machine. These computable numbers, "would include every number that could be arrived at through arithmetical operations, finding roots of equations, and using mathematical functions like sines and logarithms—every number that could possibly arise in computational mathematics" (Hodges, Alan Turing: The Enigma [1983] 100). Turing then showed that these computable numbers could give rise to uncomputable ones—ones that could not be calculated using a definite rule—and that therefore there could be no "mechanical process" for solving all mathematical questions, since an uncomputable number was an example of an unsolvable problem.

From 1936 to 1938 Mathematician Alan Turing spent more than a year at Princeton University studying mathematical logic with Alonzo Church, who was pursuing research in recursion theory. In August 1936 Church gave Turing's idea of a "universal machine" the name "Turing machine." Church coined the term in his relatively brief review of "On Computable Numbers." With regard to Turing's proof of the unsolvability of Hilbert's Entscheidungsproblem, Church acknowledged that "computability by a Turing machine. . . has the advantage of making the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately—i.e. without the necessity of proving elementary theorems." Church working independently of Turing, had arrived at his own answer to the Entscheidungsproblem a few months earlier. Norman, From Gutenberg to the Internet, Reading 7.2.

Independently of Alan Turing, mathematician and logician Emil Post of the City College of New York developed, and published in October 1936, a mathematical model of computation that was essentially equivalent to the Turing machine. Intending this as the first of a series of models of equivalent power but increasing complexity, he titled his paper Formulation 1. This model is sometime's called "Post's machine" or a Post-Turing machine.

In 1937 Turing and John von Neumann had their first discussions about computing and what would later be called “artificial intelligence” (AI). Always interested in practical applications of computing as well as theory, also while at Princeton, in 1937, believing that war with Germany was inevitable, Turing built in an experimental electromechanical cryptanalysis machine capable of binary multiplication in a university machine shop. After returning to England, on September 4, 1939, the day after Britain and France declared war on Germany, Turing reported to the Government Code and Cypher SchoolBletchley Park, in the town of Bletchley, England.

♦ In June 2013 it was my pleasure to purchase the famous copy of the offprint of "On Computable Numbers" along with the offprint of "On Computable Numbers . . . A Correction" that Turing presented to the English philosopher R. B. Braithwaite. One of very few copies in existence of the offprint, and possibly the only copy in private hands, the offprint sold for £205,000.  It was a price record for any offprint on a scientific or medical subject, for any publication in the history of computing, and probably the highest price paid for any scientific publication issued in the twentieth century.

Norman, From Gutenberg to the Internet, Reading 7.1. Hook & Norman, Origins of Cyberspace (2002) No. 394.

(This entry was last revised on 12-31-2014.)

Shannon's "Symbolic Analysis of Relay and Switching Circuits," "The Most Significant Master's Thesis of the 20th Century" August 10, 1937

Claude Shannon, in his master’s thesis entitled A Symbolic Analysis of Relay and Switching Circuits, submitted to MIT on August 10, 1937, showed that the two-valued algebra developed by George Boole could be used as a basis for the design of electrical circuits. It was first published in a revised and abridged version in Transactions of the American Institute of Electrical Engineers 57 (1938) 713-23.

This thesis became the theoretical basis for the electronics and computer industries that were developed after World War II. Shannon wrote the thesis while working at Bell Telephone Laboratories in New York City. As examples of circuits that could be built using relays, Shannon appended to the thesis theoretical descriptions of "An Electric Adder to the Base Two," and "A Factor Table Machine." The "Factor Table Machine" was not included in the published version.

Shannon's thesis was later characterized as "the most significant master's thesis of the 20th century."

♦ In October 2013 I was surprised to learn that as early as 1886 the American philosopher and logician Charles Sanders Peirce recognized that logical operations could be carried out by electrical switching circuits, and that circuit diagrams for a logic machine constructed from electrical circuits were produced for one of Peirce's students, Allan Marquand. Neither Peirce nor Marquand published on an electrical logic machine, and the concept seems not to have been pursued by either Peirce or Marquand beyond the drawing stage. Nor have I seen evidence of any further development of the concept until Shannon's thesis.

Highlights of Alan Turing and Colleagues' Cryptanalysis Work at Bletchley Park Circa September 1939 – 1945

On September 1, 1939 Germany invaded Poland, beginning World War II. Two days later, on September 3, Britain and France declared war on Germany. The following day Alan Turing appeared for work at the Code Code and Cypher School at Bletchley, England, with the goal of deciphering military communications encoded by means of Enigma machines.

As early as December 1932 the Biuro Szyfrów ("Cipher Bureau") in Warsaw, the Polish interwaragency charged with both cryptography  and cryptanalysis, had broken the German Enigma machine cipher.Over the next nearly seven years before World War II, the Polish "Cipher Bureau" overcame the growing structural and operating complexities of the plugboard-equipped Enigma, the main German cipher device during the Second World War.

Prior to the beginning of World War II, in October 1938 Polish Cipher Bureau mathematician and cryptologist Marian Rejewski designed the bomba, or bomba kryptologiczna  ("bomb" or "cryptologic bomb,") a special-purpose machine for breaking German Enigma machine  ciphers. On July 25, 1939 the Biuro Szyfrów revealed Poland's Enigma-decryption techniques and equipment, which it had achieved using the bomba device, to the French and British. Poland thereby made possible the western Allies' vitally important decryption of Nazi German   secret communications (Ultra) during World War II.

"Up to July 25, 1939, the Poles had been breaking Enigma messages for over six and a half years without telling their  French  and British allies. On December 15, 1938, two new rotors, IV and V, were introduced (three of the now five rotors being selected for use in the machine at a time). As Rejewski wrote in a 1979 critique of appendix 1, volume 1 (1979), of the official history of British Intelligence in the Second World War, 'we quickly found the [wirings] within the [new rotors], but [their] introduction [...] raised the number of possible sequences of drums from 6 to 60 [...] and hence also raised tenfold the work of finding the keys. Thus the change was not qualitative but quantitative. We would have had to markedly increase the personnel to operate the bombs, to produce the perforated sheets (60 series of 26 sheets each were now needed, whereas up to the meeting on July 25, 1939, we had only two such series ready) and to manipulate the sheets.'

"Harry Hinsley suggested in British Intelligence . . . that the Poles decided to share their Enigma-breaking techniques and equipment with the French and British in July 1939 because they had encountered insuperable technical difficulties. Rejewski refuted this: 'No, it was not [cryptologic] difficulties [. . .] that prompted us to work with the British and French, but only the deteriorating political situation. If we had had no difficulties at all we would still, or even the more so, have shared our achievements with our allies as our contribution to the struggle against Germany' ' (Wikipedia article on Bomba (cryptography), accessed 12-21-2008).

In the first few months after arriving at Bletchley Turing made a key deduction that led to his development of Banburismus, a cryptanalytic process used by Turing and his co-workers at Bletchley's Hut 8 to help break German Kriegsmarine (Naval) messages enciphered by Enigma.

"The process used sequential conditional probability to infer information about the likely settings of the Enigma machine. It gave rise to Turing's invention of the ban as a measure of the weight of evidence in favour of a hypothesis. This concept was later applied in Turingery and all the other methods used for breaking the Lorenz cipher.

"The aim of Banburismus was to reduce the time required of the electromechanical Bombe machines by identifying the most likely right-hand and middle wheels of the Enigma. Hut 8 performed the procedure continuously for two years, stopping only in 1943 when sufficient bombe time became readily available. Banburismus was a development of the "clock method" invented by the Polish cryptanalyst Jerzy Różyck

To develop Banburismus Turing

"deduced that the message-settings of Kriegsmarine Enigma signals were enciphered on a common G rundstellung (starting position of the rotors), and were then super-enciphered with a bigram and a trigram lookup table. These trigram tables were in a book called the Kenngruppenbuch (K book). However, without the bigram tables, Hut 8 were unable to start attacking the traffic. A breakthrough was achieved after the Narvik pinch in which the disguised armed trawler Polares, which was on its way to Narvik in Norway, was seized by HMS Griffin in the North Sea on 26 April 1940. The Germans did not have time to destroy all their cryptographic documents, and the captured material revealed the precise form of the indicating system, supplied the plugboard connections and Grundstellung for April 23 and 24 and the operators' log, which gave a long stretch of paired plaintext and enciphered message for the 25th and 26th.

"The bigram tables themselves were not part of the capture, but Hut 8 were able to use the settings-lists to read retrospectively, all the Kriegsmarine traffic that had been intercepted from 22 to 27 April. This allowed them do a partial reconstruction of the bigram tables and start the first attempt to use Banburismus to attack Kriegsmarine traffic, from 30 April onwards. Eligible days were those where at least 200 messages were received and for which the partial bigram-tables deciphered the indicators. The first day to be broken was 8 May 1940, thereafter celebrated as "Foss's Day" in honour of Hugh Foss, the cryptanalyst who achieved the feat.

"This task took until November that year, by which time the intelligence was very out of date, but it did show that Banburismus could work. It also allowed much more of the bigram tables to be reconstructed, which in turn allowed April 14 and June 26 to be broken. However, the Kriegsmarine had changed the bigram tables on 1 July. By the end of 1940, much of the theory of the Banburismus scoring system had been worked out.

"The First Lofoten pinch from the trawler Krebs on 3 March 1941 provided the complete keys for February - but no bigram tables or K book. The consequent decrypts allowed the statistical scoring system to be refined so that Banburismus could become the standard procedure against Kriegsmarine Enigma until mid-1943" (This and the earlier quotation are from the Wikipedia article on Banburismus, accessed 01-04-2015.)

About December 1940 Alan Turing and Gordon Welchman at Bletchley Park designed an improved Bombe cryptanalysis machine for deciphering Enigma messages.

Between 1940 and 1941 Max Newman and his team at Bletchley, including Turing, created the top-secret Heath Robinson cryptographic computer named after the cartoonist-designer of fantastic machines. This special-purpose relay computer successfully decoded messages encrypted by Enigma, the Nazis' first-generation enciphering machine.

In July 1942 Turing developed  the hand codebreaking method known as Turingery or Turing's Method (playfully dubbed Turingismus by Peter Ericsson, Peter Hilton and Donald Michie)  for use in cryptanalysis of the Lorenz cipher produced by the SZ40 and SZ42 teleprinter rotor stream cipher machines, one of the GermansGeheimschreiber (secret writer) machines. The British codenamed non-Morse traffic "Fish", and that from this machine "Tunny".

"Reading a Tunny message required firstly that the logical structure of the system was known, secondly that the periodically changed pattern of active cams on the wheels was derived, and thirdly that the starting positions of the scrambler wheels for this message—the message key—was established.The logical structure of Tunny had been worked out by William Tutte and colleagues over several months ending in January 1942. Deriving the message key was called "setting" at Bletchley Park, but it was the derivation of the cam patterns—which was known as "wheel breaking"—that was the target of Turingery.

"German operator errors in transmitting more than one message with the same key, producing a "depth", allowed the derivation of that key. Turingery was applied to such a key stream to derive the cam settings" (Wikipedia article on Turingery, accessed 01-04-2015).

In 1943 Alan Turing traveled to New York to consult with Claude Shannon and Harry Nyquist at Bell Labs concerning the encryption of speech signals between Roosevelt and Churchill.

In January 1944 the top-secret Colossus programmable cryptanalysis machine designed by Tommy Flowers and his team at the Post Office Research Station, Dollis Hill, in North West London, was installed at Bletchley Park to crack the higher level encryption of the Nazi Lorenz SZ40 machine. Colossus employed vacuum tubes and was between one hundred and one thousand times faster than Heath Robinson. "It exceeded all expectations and was able to derive many of the Lorenz settings for each message within a few hours, compared to weeks previously" (http://googleblog.blogspot.com/2012/03/remembering-colossus-worlds-first.html, accessed 03-0-2012). The Colossus machines have been called the first operational programmable electronic digital computers.

On June 1, 1944 the first improved Colossus Mark 2 with 2400 vacuum tubes was operational at Bletchley Park just in time for the Normandy Landings. By the end of the war there were ten Colossus computers operating. They enabled the decryption of 63,000,000 characters of high-grade German messages. Even though these machines incorporated features of special purpose electronic digital computers, and had incalculable influence on the outcome of WWII, they had little influence in the conventional sense on the development of computing technology because they remained top secret until about 1970.

"The Colossus computers were used to help decipher teleprinter  messages which had been encrypted using the Lorenz SZ40/42 machine — British codebreakers referred to encrypted German teleprinter traffic as "Fish" and called the SZ40/42 machine and its traffic as 'Tunny'. Colossus compared two data streams, counting each match based on a programmable Boolean function. The encrypted message was read at high speed from a paper tape. The other stream was generated internally, and was an electronic simulation of the Lorenz machine at various trial settings. If the match count for a setting was above a certain threshold, it would be sent as output to an electric typewriter" (Wikipedia article on Colossus computer, accessed 11-23-2008).

In March 2012 the Colossus Rebuild Project at the National Museum of Computing at Bletchley Park had completed an operating reconstruction of a Colossus II, after 10 years and over 6,000 man-days of volunteer effort. The Rebuild stands in its historically correct place, the room in H Block, in Bletchley Park, where Colossus No. 9 stood in WW II.

(This entry was last revised on 01-17-2015.)

The Design and Principles of John Atanasoff's ABC Machine, and What John Mauchly Knew About It August – December 1940

In August 1940 American physicist and inventor John Atanasoff at Iowa State University in Ames, Iowa, wrote a thirty-five-page memorandum describing the design and principles of the what came to be known as the Atanasoff-Berry Computer or ABC machine. This may be the earliest extant document describing the principles of an electronic digital computer. It remained unpublished until 1973.

In December 1940 John Mauchly met Atanasoff at the Philadelphia meeting of the American Association of the Advancement of Science. After corresponding with Atanasoff about electronic calculating, Mauchly visited Atanasoff in Ames, and read the 35-page memorandum on the ABC machine that Atanasoff had written in August. Mauchly would later incorporate some of Atanasoff's ideas into his design for the ENIAC.

Because of World War II, in 1942 Atanasoff abandoned work on his special purpose ABC machine when it was nearly operational. The machine was largely forgotten until interest in it was revived for the lawsuit over the ENIAC patent. As a reference on Atanasoff and the ENIAC patent case I recommend the Iowa State University Department of Computer Science website on Atanasoff. In December 2014 it was available at this link.

(This entry was last revised on 12-31-2014.)

McCulloch & Pitts Publish the First Mathematical Model of a Neural Network 1943

In 1943 American neurophysiologist and cybernetician of the University of Illinois at Chicago Warren McCulloch and self-taught logician and cognitive psychologist Walter Pitts published “A Logical Calculus of the ideas Imminent in Nervous Activity,” describing the McCulloch - Pitts neuron, the first mathematical model of a neural network.

Building on ideas in Alan Turing’s “On Computable Numbers”, McCulloch and Pitts's paper provided a way to describe brain functions in abstract terms, and showed that simple elements connected in a neural network can have immense computational power. The paper received little attention until its ideas were applied by John von Neumann, Norbert Wiener, and others.

Von Neumann Privately Circulates the First Theoretical Description of a Stored-Program Computer June 30, 1945

On June 30, 1945 mathematician and physicist John von Neumann of Princeton privately circulated copies of his First Draft on a Report on the EDVAC to twenty-four people connected with the EDVAC project. This document, written between February and June 1945, provided the first theoretical description of the basic details of a stored-program computer—what later became known as the Von Neumann architecture.

To avoid the government's security classification, and to avoid engineering problems that might detract from the logical considerations under discussion, von Neumann avoided mentioning specific hardware. Influenced by Alan Turing and by Warren McCulloch and Walter Pitts, von Neumann patterned the machine to some degree after human thought processes.

In November 2013 the text of von Neumann's report was available at this link

The Macy Conferences on Cybernetics Occur 1946 – 1953

At the initiative of Warren McCulloch, from 1946 to 1954 the Macy Conferences occurred in New York to set the foundations for a general science of the workings of the human mind. They resulted in breakthroughs in systems theory, cybernetics, and what eventually became known as cognitive science.

Key Developments in von Neumann's IAS Electronic Computer Project March 1946 – 1947

In March 1946 John von Neumann attempted to set up an electronic stored-program computer project at the Institute for Advanced Study (IAS) at Princeton. He tried to hire Pres Eckert, but Eckert refused the job, preferring to go into the computer business with John Mauchly as the Electronic Control Company.

In June 1946 engineer Julian Bigelow, who previously had collaborated with Norbert Wiener at MIT, joined von Neumann and Herman Goldstine at the Princeton IAS Electronic Computer Project. He was to a large extent responsible for implementing von Neumann's stored-program concepts.

At Princeton in June 1946 Arthur W. Burks, von Neumann, and Goldstine issued their Preliminary Discussion of the Logical Design of an Electronic Computing Instrument, discussing ideas to be incorporated into the stored-program computer at the IAS.

Around June 1947 Julian Bigelow and his team at Princeton redesigned the IAS machine to include error checking and parallel processing, essential features of what became known as the von Neumann architecture.

(This entry was last revised on 01-01-2015.)

The Moore School Lectures Take Place July 8 – 1946

From July 8 to August 30, 1946 the Moore School lectures on “The theory and techniques for design of electronic digital computers” occurred at the University of Pennsylvania. This series of lectures, attended by twenty-eight highly qualified experts, led to widespread adoption of the EDVAC-type design—including stored programs—for nearly all subsequent computer development.

Goldstine & von Neumann Write the First Theoretical Discussion of Programming a Stored-Program Computer April 1947 – August 16, 1948

The first part of Herman Goldstine and John von Neumann’s Planning and Coding Problems for an Electronic Computing Instrument was published at Princeton in April 1947. The remaining two parts appeared on April 15 and August 16, 1948. This was the first theoretical discussion of programming for stored program computers—none of which yet operated. (See Reading 9.2.)

Norbert Wiener Issues "Cybernetics", the First Widely Distributed Book on Electronic Computing 1948

"Use the word 'cybernetics', Norbert, because nobody knows what it means. This will always put you at an advantage in arguments."

In 1948 mathematician Norbert Wiener at MIT published Cybernetics or Control and Communication in the Animal and the Machine, a widely circulated and influential book that applied theories of information and communication to both biological systems and machines. Computer-related words with the “cyber” prefix, including "cyberspace," originate from Wiener’s book. Cybernetics was also the first conventionally published book to discuss electronic digital computing. Writing as a mathematician rather than an engineer, Wiener’s discussion was theoretical rather than specific. Strangely the first edition of the book was published in English in Paris at the press of Hermann et Cie. The first American edition was printed offset from the French sheets and issued by John Wiley in New York, also in 1948. I have never seen an edition printed or published in England.

Independently of Claude Shannon, Wiener conceived of communications engineering as a brand of statistical physics and applied this viewpoint to the concept of information. Wiener's chapter on "Time series, information, and communication" contained the first publication of Wiener's formula describing the probability density of continuous information. This was remarkably close to Shannon's formula dealing with discrete time published in A Mathematical Theory of Communication (1948). Cybernetics also contained a chapter on "Computing machines and the nervous system." This was a theoretical discussion, influenced by McCulloch and Pitts, of differences and similarities between information processing in the electronic computer and the human brain. It contained a discussion of the difference between human memory and the different computer memories then available. Tacked on at the end of Cybernetics were speculations by Wiener about building a chess-playing computer, predating Shannon's first paper on the topic.

Cybernetics is a peculiar, rambling blend of popular and highly technical writing, ranging from history to philosophy, to mathematics, to information and communication theory, to computer science, and to biology. Reflecting the amazingly wide range of the author's interests, it represented an interdisciplinary approach to information systems both in biology and machines. It influenced a generation of scientists working in a wide range of disciplines. In it were the roots of various elements of computer science, which by the mid-1950s had broken off from cybernetics to form their own specialties. Among these separate disciplines were information theory, computer learning, and artificial intelligence.

It is probable that Wiley had Hermann et Cie supervise the typesetting because they specialized in books on mathematics.  Hermann printed the first edition by letterpress; the American edition was printed offset from the French sheets. Perhaps because the typesetting was done in France Wiener did not have the opportunity to read proofs carefully, as the first edition contained many typographical errors which were repeated in the American edition, and which remained uncorrected through the various printings of the American edition until a second edition was finally published by John Wiley and MIT Press in 1961.

Though the book contained a lot of technical mathematics, and was not written for a popular audience, the first American edition went through at least 5 printings during 1948,  and several later printings, most of which were probably not read in their entirety by purchasers. Sales of Wiener's book were helped by reviews in wide circulation journals such as the review in TIME Magazine on December 27, 1948, entitled "In Man's Image." The reviewer used the word calculator to describe the machines; at this time the word computer was reserved for humans.

"Some modern calculators 'remember' by means of electrical impulses circulating for long periods around closed circuits. One kind of human memory is believed to depend on a similar system: groups of neurons connected in rings. The memory impulses go round & round and are called upon when needed. Some calculators use 'scanning' as in television. So does the brain. In place of the beam of electrons which scans a television tube, many physiologists believe, the brain has 'alpha waves': electrical surges, ten per second, which question the circulating memories.

"By copying the human brain, says Professor Wiener, man is learning how to build better calculating machines. And the more he learns about calculators, the better he understands the brain. The cyberneticists are like explorers pushing into a new country and finding that nature, by constructing the human brain, pioneered there before them.

"Psychotic Calculators. If calculators are like human brains, do they ever go insane? Indeed they do, says Professor Wiener. Certain forms of insanity in the brain are believed to be caused by circulating memories which have got out of hand. Memory impulses (of worry or fear) go round & round, refusing to be suppressed. They invade other neuron circuits and eventually occupy so much nerve tissue that the brain, absorbed in its worry, can think of nothing else.

"The more complicated calculating machines, says Professor Wiener, do this too. An electrical impulse, instead of going to its proper destination and quieting down dutifully, starts circulating lawlessly. It invades distant parts of the mechanism and sets the whole mass of electronic neurons moving in wild oscillations" (http://www.time.com/time/magazine/article/0,9171,886484-2,00.html, accessed 03-05-2009).

Presumably the commercial success of Cybernetics encouraged Wiley to publish Berkeley's Giant Brains, or Machines that Think in 1949.

♦ In October 2012 I offered for sale the copy of the first American printing of Cybernetics that Wiener inscribed to Jerry Wiesner, the head of the laboratory at MIT where Wiener conducted his research. This was the first inscribed copy of the first edition (either the French or American first) that I had ever seen on the market, though the occasional signed copy of the American edition did turn up. Having read our catalogue description of that item, my colleague Arthur Freeman emailed me this story pertinent to Wiener's habit of not inscribing books:

"Norbert, whom I grew up nearby (he visited our converted barn in Belmont, Mass., constantly to play frantic theoretical blackboard math with my father, an economist/statistician at MIT, which my mother, herself a bit better at pure math, would have to explain to him later), was a notorious cheapskate. His wife once persuaded him to invite some colleagues out for a beer at the Oxford Grill in Harvard Square, which he did, and after a fifteen-minute sipping session, he got up to go, and solemnly collected one dime each from each of his guests. So when *Cybernetics* appeared on the shelves of the Harvard Coop Bookstore, my father was surprised and flattered that Norbert wanted him to have an inscribed copy, and together they went to Coop, where Norbert duly picked one out, wrote in it, and carried it to the check-out counter--where he ceremoniously handed it over to my father to pay for. This was a great topic of family folklore. I wonder if Jerry Wiesner paid for his copy too?"

Edmund Berkeley's "Giant Brains," the First Popular Book on Electronic Computers 1949

In 1949 mathematician and actuary Edmund Berkeley issued Giant Brains or Machines that Think, the first popular book on electronic computers, published years before the public heard much about the machines. The work was published by John Wiley & Sons who were enjoying surprising commercial success with Norbert Wiener's much more technical book, Cybernetics.

Among many interesting details, Giant Brains contained a discussion about a machine called Simon, which has been called the first personal computer.

A Neurosurgeon Discusses the Differences between Computers and the Human Brain June 9, 1949

On June 9, 1949 Sir Geoffrey Jefferson, a neurological surgeon at Manchester, England, delivered a speech entitled The Mind of Mechanical Man in which he discussed the differences between computers and the human brain. (See Reading 11.1).

Jule Charney, Agnar Fjörtoff & John von Neumann Report the First Weather Forecast by Electronic Computer 1950

In 1950 meteorologist Jule Charney of MIT, Agnar Fjörtoff, and mathematician John von Neumann of Princeton published “Numerical Integration of the Barotropic Vorticity Equation,” Tellus 2 (1950) 237-254. The paper reported the first weather forecast by electronic computer. It took twenty-four hours of processing time on the ENIAC to calculate a twenty-four hour forecast.

"As a committed opponent of Communism and a key member of the WWII-era national security establishment, von Neumann hoped that weather modeling might lead to weather control, which might be used as a weapon of war. Soviet harvests, for example, might be ruined by a US-induced drought.

"Under grants from the Weather Bureau, the Navy, and the Air Force, he assembled a group of theoretical meteorologists at Princeton's Institute for Advanced Study (IAS). If regional weather prediction proved feasible, von Neumann planned to move on to the extremely ambitious problem of simulating the entire atmosphere. This, in turn, would allow the modeling of climate. Jule Charney, an energetic and visionary meteorologist who had worked with Carl-Gustaf Rossby at the University of Chicago and with Arnt Eliassen at the University of Oslo, was invited to head the new Meteorology Group.

"The Meteorology Project ran its first computerized weather forecast on the ENIAC in 1950. The group's model, like [Lewis Fry] Richardson's, divided the atmosphere into a set of grid cells and employed finite difference methods to solve differential equations numerically. The 1950 forecasts, covering North America, used a two-dimensional grid with 270 points about 700 km apart. The time step was three hours. Results, while far from perfect, justified further work" (Paul N. Edwards [ed], Atmospheric General Circulation Modeling: A Participatory History, accessed 04-26-2009).

As Charney, Fjörtoff, and von Neumann reported:

"It may be of interest to remark that the computation time for a 24-hour forecast was about 24 hours, that is, we were just able to keep pace with the weather. However, much of this time was consumed by manual and I.B.M. oeprations, namely by the reading, printing, reproducing, sorting and interfiling of punch cards. In the course of the four 24 hour forecasts about 100,000 standard I.B.M. punch cards were produced and 1,000,000 multiplications and divisions were performed. (These figures double if one takes account of the preliminary experimentation that was carried out.) With a larger capacity and higher speed machine, such as is now being built at the Institute for Advanced Study, the non-arithmetical operations will be eliminated and the arithmetical operations performed more quickly. It is estimated that the total computation time with a grid of twice the Eniac-grids density, will be about 1/2 hour, so that one has reason to hope that RICHARDSON'S dream (1922) of advancing the computation faster than the weather may soon be realized, at least for a two-dimensional model. Actually we estimate on the basis of the experiences acquired in the course of the Eniac calculations, that if a renewed systematic effort with the Eniac were to be made, and with a thorough routinization of the operations, a 24-hour prediction could be made on the Eniac in as little as 12 hours." (pp. 274-75).

Shannon Issues the First Technical Paper on Computer Chess March 1950

In March 1950 Claude Shannon of Bell Labs, Murray Hill, New Jersey, published "Programming a Computer for Playing Chess," Philosophical Magazine, Ser.7, 41, no. 314. This was the first technical paper on computer chess; however, the paper was entirely theoretical; it contained no references to Shannon programming an actual computer to play a game.

The Paris symposium, "Les Machines á calculer et la pensée humaine," Occurs January 8 – January 13, 1951

From January 8-13, 1951 the Paris symposium, Les Machines á calculer et la pensée humaine (Calculating Machines and Human Thought) took place at l'Institut Blaise Pascal. Unlike the other early computer conferences, no demonstration of a stored-program electronic computer occurred. Louis Couffignal demonstrated the prototype of his non-stored-program machine.

Hook & Norman, Origins of Cyberspace (2002) no. 526.

Alan Turing's Ambiguous Suicide June 8, 1954

On June 7, 1954 Turing probably committed suicide in Wilmslow, a town in Cheshire, England, by eating an apple laced with cyanide. He was only 42 years old. Had Turing lived a normal life span he would have contributed profoundly to further developments in computing, and it is even possible that as a result of those contributions, the English computing industry might have been more competitive with that in the United States. Some ambiguity remains about Turing's cause of death. In December 2013 the best summary of the issues was in the Wikipedia article on Alan Turing, from which I quote:

"On 8 June 1954, Turing's cleaner found him dead. He had died the previous day. A post-mortem examination established that the cause of death was cyanide poisoning. When his body was discovered, an apple lay half-eaten beside his bed, and although the apple was not tested for cyanide, it was speculated that this was the means by which a fatal dose was consumed. This suspicion was strengthened when his fascination with Snow White and the Seven Dwarfs was revealed, especially the transformation of the Queen into the Witch and the ambiguity of the poisoned apple. An inquest determined that he had committed suicide, and he was cremated at Woking Crematorium on 12 June 1954. Turing's ashes were scattered there, just as his father's had been.

'Hodges and David Leavitt have suggested that Turing was re-enacting a scene from the 1937 Walt Disney film Snow White, his favourite fairy tale, both noting that (in Leavitt's words) he took "an especially keen pleasure in the scene where the Wicked Queen immerses her apple in the poisonous brew". This interpretation was supported in an article in The Guardian written by Turing's friend, the author Alan Garner, in 2011.

"Professor Jack Copeland (philosophy) has questioned various aspects of the coroner's historical verdict, suggesting the alternative explanation of the accidental inhalation of cyanide fumes from an apparatus for gold electroplating spoons, using potassium cyanide to dissolve the gold, which Turing had set up in his tiny spare room. Copeland notes that the autopsy findings were more consistent with inhalation than with ingestion of the poison. Turing also habitually ate an apple before bed, and it was not unusual for it to be discarded half-eaten. In addition, Turing had reportedly borne his legal setbacks and hormone treatment (which had been discontinued a year previously) 'with good humour' and had shown no sign of despondency prior to his death, in fact, setting down a list of tasks he intended to complete upon return to his office after the holiday weekend. At the time, Turing's mother believed that the ingestion was accidental, caused by her son's careless storage of laboratory chemicals. Biographer Andrew Hodges suggests that Turing may have arranged the cyanide experiment deliberately, to give his mother some plausible deniability."

Werner Buchholz Coins the Term "Byte" July 1956

In July 1956 German born American computer scientist Werner Buchholz coined the term byte as a unit of digital information during the
early design phase for the IBM 7030 Stretch, IBM's first transistorized supercomputer. A byte was an ordered collection of bits, which were the smallest amounts of data that a computer could process ("bite").The Stretch incorporated addressing to the bit, and variable field length (VFL) instructions with a byte size encoded in the instruction. Byte was a deliberate respelling of bite to avoid accidental confusion with bit.

"Early computers used a variety of 4-bit binary coded decimal (BCD) representations and the 6-bit codes for printable graphic patterns common in the U.S. Army (Fieldata) and Navy. These representations included alphanumeric characters and special graphical symbols. These sets were expanded in 1963 to 7 bits of coding, called the American Standard Code for Information Interchange (ASCII) as the Federal Information Processing Standard which replaced the incompatible teleprinter codes in use by different branches of the U.S. government. ASCII included the distinction of upper and lower case alphabets and a set of control characters to facilitate the transmission of written language as well as printing device functions, such as page advance and line feed, and the physical or logical control of data flow over the transmission media. During the early 1960s, while also active in ASCII standardization, IBM simultaneously introduced in its product line of System/360 the 8-bit Extended Binary Coded Decimal Interchange Code (EBCDIC), an expansion of their 6-bit binary-coded decimal (BCDIC) representation used in earlier card punches. The prominence of the System/360 led to the ubiquitous adoption of the 8-bit storage size, while in detail the EBCDIC and ASCII encoding schemes are different" (Wikipedia article on Byte, accessed 01-15-2015).

The Premature Death of John von Neumann February 8, 1957

On February 8, 1957 mathematician and physicist John von Neumann died of cancer at the age of fifty-four. Like the death of Alan Turing at the age of 42, von Neumann's premature death was an enormous loss for computer science, as well as for mathematics and physics.

Machines Can Learn from Past Errors July 1959

In July 1959 Arthur Lee Samuel published "Some Studies in Machine Learning Using the Game of Checkers," IBM Journal of Research and Development 3 (1959) no. 3, 210-29. In this work Samuel demonstrated that machines can learn from past errors — one of the earliest examples of non-numerical computation.

Hook & Norman, Origins of Cyberspace (2002) no. 874.

Kleinrock Introduces the Concept Later Known as Packet Switching April 1962

In April 1962 Leonard Kleinrock published "Information Flow in Large Communication Nets" in RLE Quarterly Progress Reports. This was the first publication to describe and analyze an algorithm for chopping messages into smaller pieces, later to be known as packets. Kleinrock's MIT doctoral thesis, Message Delay in Communication Nets with Storage, filed in December 1962, elaborated on the impact of this algorithm on data networks. (See Reading 13.3.)

John Alan Robinson Introduces the Resolution Principle January 1965

In 1965 philosopher, mathematician and computer scientist John Alan Robinson, while at Rice University, published "A Machine-Oriented Logic Based on the Resolution Principle", Communications of the ACM, 5: 23–41. This paper introduced the resolution principle, a standard of logical deduction in AI applications.

The Cooley-Tukey FFT Algorithm April 1965

In April 1965 American mathematician James W. Cooley of IBM Watson Research Center, Yorktown Heights, New York,  and American statistician John W. Tukey published "An algorithm for the machine calculation of complex Fourier series", Mathematics of  Computation 19, 297–301. This paper enunciated the Cooley-Tukey FFT algorithm, the most common fast Fourier transform algorithm.

"The motivation for it [FFT algorithm] was provided by Dr. Richard L. Garwin at IBM Watson Research who was concerned about verifying a Nuclear arms treaty with the Soviet Union for the SALT talks. Garwin thought that if he had a very much faster Fourier Transform he could plant sensors in the ground in countries surrounding the Soviet Union. He suggested the idea of how Fourier transforms could be programmed to be much faster to both Cooley and Tukey. They did the work, the sensors were planted, and he was able to locate nuclear explosions to within 15 kilometers of where they were occurring" (Wikipedia article on James Cooley, accessed 03-06-2012).

Konrad Zuse Issues "Rechnender Raum," the First Book on Digital Physics 1969

In 1969 German engineer and computer designer Konrad Zuse published Rechnender Raum. This was translated into English in 1970 under the title, Calculating Space. It was the first book on digital physics.

"Zuse proposed that the universe is being computed in real time on some sort of cellular automata or other discrete computing machinery, challenging the long-held view that some physical laws are continuous by nature. He focused on cellular automata as a possible substrate of the computation, and pointed out (among other things) that the classical notions of entropy and its growth do not make sense in deterministically computed universes.

"Bell's theorem is sometimes thought to contradict Zuse's hypothesis, but it is not applicable to deterministic universes, as Bell himself pointed out. Similarly, while Heisenberg's uncertainty principle limits in a fundamental way what an observer can observe, when the observer is himself a part of the universe he is trying to observe, that principle does not rule out Zuse's hypothesis, which views any observer as a part of the hypothesized deterministic process. So far there is no unambiguous physical evidence against the possibility that "everything is just a computation," and a fair bit has been written about digital physics since Zuse's book appeared" (Wikipedia article on Calculating Space, accessed 05-16-2009).

The First Computer Employing RISC 1974

In 1974 IBM built the first prototype computer employing RISC (Reduced Instruction Set Computer) architecture. Based on an invention by IBM researcher John Cocke, the RISC concept simplified the instructions given to run computers, making them faster and more powerful. It was implemented in the experimental IBM 801 minicomputer. The goal of the 801 was to execute one instruction per cycle.

In 1987 John Cocke received the A. M. Turing Award for significant contributions in the design and theory of compilers, the architecture of large systems and the development of reduced instruction set computers (RISC); for discovering and systematizing many fundamental transformations now used in optimizing compilers including reduction of operator strength, elimination of common subexpressions, register allocation, constant propagation, and dead code elimination.

First Description of a Universal Quantum Computer 1985

In 1995 David Deutsch, a British physicist at Oxford University, described the first universal quantum computer or quantum Turing machine, and specified an algorithm designed to run on a quantum computer.

Deutsch,"Quantum theory, the Church-Turing principle and the universal quantum computer," Proceedings of the Royal Society A 400 (1818): pp. 97–117. Bibcode:1985RSPSA.400...97D. doi:10.1098/rspa.1985.0070.

Formulation of Shor's Algorithm for Quantum Computers 1994

In 1994 American applied mathematician Peter Shor, working at Bell Labs in Murray Hill, New Jersey, formulated Shor's algorithm, a quantum algorithm for integer factorization. Because Shor's algorithm shows that a quantum computer, or quantum supercomputer algorithm, with a sufficient number of qubits, operating without succumbing to noise or other quantum interference phenomena, could theoretically be used to break public-key cryptography schemes such as the widely used RSA scheme, its formulation in 1994 was a powerful motivator for the design and construction of quantum computers, and for the study of new quantum computer algorithms. It also stimulated research on new cryptosystems secure from quantum computers, collectively called post-quantum cryptography

"In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 × 5, using an NMR implementation of a quantum computer with 7 qubits. However, some doubts have been raised as to whether IBM's experiment was a true demonstration of quantum computation, since no entanglement was observed. Since IBM's implementation, several other groups have implemented Shor's algorithm using photonic qubits, emphasizing that entanglement was observed. In 2012, the factorization of 15 was repeated. Also in 2012, the factorization of 21 was achieved, setting the record for the largest number factored with a quantum computer" (Wikipedia article on Shor's algorithm, accessed 12-24-2013).

Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput. 26 (1996) 1484–1509, arXiv:quant-ph/9508027v2.

Is the Universe Made of Information? February 2007

The February 2007 issue of Wired

James Gleick

In the February 2007 issue of Wired James Gleick wrote:

"Is the universe actually made of information? Humans have talked about atoms since the time of the ancients, and ever-smaller fundamental particles of matter followed. But no one even conceived of bits until the middle of the 20th century. The bit is a fundamental particle, too, but of different stuff altogether: information. It is not just tiny, it is abstract - a flip-flop, a yes-or-no. Now that scientists are finally starting to understand information, they wonder whether it’s more fundamental than matter itself. Perhaps the bit is the irreducible kernel of existence; if so, we have entered the information age in more ways than one."

The First Master's Degree Offered through Massive Open Online Courses by a Major University August 17, 2013

On August 17, 2013 The New York Times reported that Georgia Tech, which operates one of the country’s top computer science programs, plans to offer in January 2014 a massive open online course (MOOC) master’s degree in computer science for \$6,600 — far less than the \$45,000 on-campus price.

"Zvi Galil, the dean of the university’s College of Computing, expects that in the coming years, the program could attract up to 10,000 students annually, many from outside the United States and some who would not complete the full master’s degree. 'Online, there’s no visa problem,' he said.

"The program rests on an unusual partnership forged by Dr. Galil and Sebastian Thrun, a founder of Udacity, a Silicon Valley provider of the open online courses.

"Although it is just one degree at one university, the prospect of a prestigious low-cost degree program has generated great interest. Some educators think the leap from individual noncredit courses to full degree programs could signal the next phase in the evolution of MOOCs — and bring real change to higher education."

"From their start two years ago, when a free artificial intelligence course from Stanford enrolled 170,000 students, free massive open online courses, or MOOCs, have drawn millions and yielded results like the perfect scores of Battushig, a 15-year-old Mongolian boy, in a tough electronics course offered by the Massachusetts Institute of Technology" (http://www.nytimes.com/2013/08/18/education/masters-degree-is-new-frontier-of-study-online.html?hp, accessed 08-18-2013).