Logic Machines

views updated

LOGIC MACHINES

Because logic underlies all deductive reasoning, one might say that all computers are logic machines. In a wider sense, any mechanical device is a logic machine (for example, an eggbeater spins clockwise "if and only if" its crank turns clockwise). Generally, however, the term is restricted to machines designed primarily or exclusively for solving problems in formal logic. Although a digital computer, or even a punch-card data-processing machine, can be programmed to handle many types of logic, it is not considered a logic machine in the strict sense.

The rotating circles of Ramón Lull, thirteenth-century Spanish mystic, cannot be called logic machines even though they were used as reasoning aids. The first true logic machine was a small device called a "demonstrator," invented by Charles Stanhope, third Earl Stanhope, an eighteenth-century English statesman. By sliding two panels (one of gray wood, the other of transparent red glass) behind a rectangular opening, he could test the validity of traditional syllogisms, as well as syllogisms with such quantified terms as "Most of a " and "8 of 10 of a. " Stanhope also used his device for solving elementary problems in what he called the logic of probability.

Jevons's Machine

The first logic machine capable of solving a complicated problem faster than a human could solve it without the aid of a machine was the "logical piano" invented by the nineteenth-century economist and logician William Stanley Jevons. The machine was built for him by a clockmaker at Salford in 1869 and first demonstrated by Jevons in 1870 at a meeting of the Royal Society of London. The device (now owned by the Oxford Museum of the History of Science) resembles a miniature upright piano, about three feet high, with a keyboard of 21 keys. On the face of the piano are openings through which one can see the 16 possible combinations of 4 terms and their negatives. A statement in logic is fed to the machine by pressing keys according to certain rules. Internal levers and pulleys eliminate from the machine's face all combinations of terms inconsistent with the statement. When all desired statements have thus been fed to the machine the face is inspected to determine what term combinations, if any, are consistent with the statements.

Jevons believed that this machine, designed to handle Boolean algebra, provided a convincing demonstration of the superiority of George Boole's logic over the traditional logic of Aristotle and the Schoolmen. John Venn's system of diagramming follows essentially the same procedure as Jevons's machine. In both cases the procedure gives what are today called the valid lines of a truth table for the combined statements under consideration. Neither the Venn diagrams nor Jevons's machine is capable of reducing these lines to a more compact form. This criticism of the machine was stressed by the English philosopher F. H. Bradley in his Principles of Logic (1883).

Other Mechanical Devices

Jevons's logical piano was greatly simplified by Allan Marquand, who built his first model in 1881, when he was teaching logic at Princeton University. Like Jevons's, Marquand's machine is limited to 4 terms, but the 16 possible combinations are exhibited on its face by 16 pointers, each with a valid and an invalid position, arranged in a pattern that corresponds to Marquand's chart for 4 terms (see the entry "Logic Diagrams," Figure 5). The number of keys is reduced to 10, and the device is about a third the height of Jevons's machine. Both Marquand and Jevons interpreted Boolean algebra primarily in class terms, but their machines operate just as efficiently with the propositional calculus.

A third machine of the Jevons type was invented in 1910 by Charles P. R. Macaulay, an Englishman living in Chicago. It is a compact, ingenious boxlike device with interior rods operated by tilting the box a certain way while pins on the side are pressed to put statements into the machine. Consistent combinations of four terms and their negatives appear in windows on top of the box.

A curious contrivance for evaluating the 256 combinations of syllogistic premises and conclusions was constructed in 1903 by Annibale Pastore, a philosopher at the University of Genoa. It consists of three wheels, representing a syllogism's three terms, joined to one another by an arrangement of endless belts appropriate to the syllogism being tested. If the syllogism is valid, all three wheels turn when one is cranked.

Grid Cards

Logic grid cards are cards that can be superposed so that valid deductions from logical premises are seen through openings on the cards. A set of syllogism grid cards invented by the Englishman Henry Cunynghame, a contemporary of Jevons, was depicted by Jevons in Chapter 11 of Studies in Deductive Logic (London, 1884). A differently designed set is shown in Martin Gardner's "Logic Machines" (in Scientific American 186 [March 1952]: 68–73). A more elaborate set, indicating the nature of the fallacy when a syllogism is invalid, can be found in Gardner's Logic Machines and Diagrams (New York, 1958) and Richard Lampkin's Testing for Truth (Buffalo, NY, 1962). Triangular-shaped grid cards, for binary relations in the propositional calculus, are described in Gardner's book and in H. M. Cundy and A. P. Rollett's Mathematical Models (2nd ed., Oxford, 1961; see pp. 256–258). Gardner described a simple way to make punch cards that can be sorted in such a manner as to solve logic problems in "Mathematical Games" (in Scientific American 203 [December 1960]: 160–168).

Electrical Machines

Marquand sketched an electrical circuit by which his machine could be operated, but the electrical version was probably never built. Benjamin Burack, a psychologist at Roosevelt College, Chicago, was the first actually to construct an electrical logic machine, in 1936. His device tested all syllogisms, including hypothetical and disjunctive forms. Since then many different kinds of electrical syllogism machines have been constructed.

In 1910, in a review in a Russian journal, Paul Ehrenfest pointed out that because a wire either carries a current or does not, it would be possible to translate certain types of switching circuits into Boolean algebra. Work along such lines was done by the Russian physicist V. I. Šestakov in 1934–1935, but his results were not published until 1941. Similar views were set forth independently in 1936, in a Japanese journal, by Akira Nakasima and Masao Hanzawa. It was the mathematician Claude E. Shannon, however, who impressed the engineering world with the importance of this isomorphism by his independent work, first published in 1938.

Shannon's paper inspired William Burkhart and Theodore A. Kalin, then undergraduates at Harvard University, to design the world's first electrical machine for evaluating statements in the propositional calculus. The Kalin-Burkhart machine was built in 1947. Statements with as many as twelve terms are fed into it by setting switches. The machine scans a truth table for the combined statements, and a set of twelve small bulbs indicates the combination of true and false terms for each truth-table row as it is scanned. If the combination is consistent with the statements, this is indicated by another bulb. The machine is thus an electrical version of Jevons's device but handles more complex statements and presents valid truth-table rows in serial time sequence rather than simultaneously.

A three-term electrical machine was built in England in 1949 without knowledge of the Kalin-Burkhart machine. Advances in switching components made possible more sophisticated logic machines in the United States and elsewhere during the early 1950s. Of special interest is a ten-term machine built at the Burroughs Research Center in Paoli, Pennsylvania, using the parenthesis-free notation of Jan Łukasiewicz.

Digital Computers

While the special machines were being developed it became apparent that statements in Boolean algebra could easily be translated into a binary notation and analyzed on any general-purpose digital computer. As digital computers became more available, as well as faster and more flexible, interest in the design of special-purpose logic machines waned. Since 1955 almost all machine-aided investigations in logic have been conducted with digital computers. In 1960, Hao Wang described how he used an IBM 704 computer to test the first 220 theorems of the propositional calculus in Principia Mathematica. The machine's total running time was under three minutes.

The similarity between switching circuits and the nets of nerve cells in the brain suggests that the brain may think by a process that could be duplicated by computers. Much work is being done in programming computers to search for proofs of logic theorems in a manner similar to the heuristic reasoning of a logician—that is, by an uncertain strategy compounded of trial and error, logical reasoning, analogies with remembered experience, and sheer luck. The work is closely related to all types of learning machines. Such work may prove useful in exploring logics for which there is no decision procedure—or no known decision procedure—but no special machines have yet been built for such a purpose. Work is also under way on the more difficult problem of designing a machine, or programming a digital computer, to find new, nontrivial, and interesting theorems in a given logic.

Attempts have been made to design machines capable of reducing a statement in Boolean algebra to simpler form. A primitive minimizing machine was constructed by Daniel Bobrow, a New York City high school student, in 1952. At about the same time, Shannon and Edward F. Moore built a relay circuit analyzer that makes a systematic attempt to simplify circuits, a problem closely related to the logic minimizing problem.

No special machines are known to have been constructed for handling many-valued logics, but many papers have been published explaining how such machines could be built, as well as how digital computers could be programmed to handle such logics. Kurt Gödel's undecidability proof has ruled out the possibility of an ultimate logic machine capable of following a systematic procedure for testing any theorem in any possible logic, but whether the human brain is capable of doing any kind of creative work that a machine cannot successfully imitate is still an open, much debated question.

Bibliography

For a history of logic machines, see Martin Gardner, Logic Machines and Diagrams (New York: McGraw-Hill, 1958), and Rudolf Tarján, "Logische Maschinen," in Digital Information Processors, edited by Walter Hoffmann (New York: Interscience, 1962), which includes a bibliography of 119 references. Stanhope's machine is discussed in Robert Harley, "The Stanhope Demonstrator," Mind 4 (1879): 192–210.

Jevons described his logical piano in "On the Mechanical Performance of Logical Inference" (1870), reprinted in his Pure Logic and Other Minor Works (London: Macmillan, 1890); a briefer discussion appears in his Principles of Science (London: Macmillan, 1874; reprinted, New York, 1958). Marquand discussed his machine in "A New Logical Machine," Proceedings of the American Academy of Arts and Sciences 21 (1885): 303–307. Marquand's machine was praised by C. S. Peirce in "Logical Machines," American Journal of Psychology 1 (November 1887): 165–170. Pastore wrote an entire book about his device, Logica formale, dedotta della considerazione di modelli meccanici (Turin, 1906). The book was reviewed at length by André Lalande in Revue philosophique de la France et de l'étranger 63 (1907): 268–275.

Wolfe Mays, "The First Circuit for an Electrical Logic-Machine," in Science 118 (1953): 281–282, and George W. Patterson, "The First Electric Computer, a Magnetological Analysis," in Journal of the Franklin Institute 270 (1960): 130–137, describe Marquand's sketches. A description of Macaulay's device is in his U.S. patent, No. 1,079,504, issued in 1913.

Burack first described his 1936 machine in "An Electrical Logic Machine," Science 109 (1949): 610–611. Shannon's historic paper on the isomorphism of Boolean algebra and certain types of switching circuits is "A Symbolic Analysis of Relay and Switching Circuits," in Transactions of the American Institute of Electrical Engineers 57 (1938): 713–723. The Kalin-Burkhart machine is described in Edmund C. Berkeley, Giant Brains (New York: Wiley, 1949). The English three-term machine is discussed in Wolfe Mays and D. G. Prinz, "A Relay Machine for the Demonstration of Symbolic Logic," Nature 165 (1950): 197. The Burroughs machine is discussed in A. W. Burks, D. W. Warren, and J. B. Wright, "An Analysis of a Logical Machine Using Parenthesis-Free Notation," Mathematical Tables and Other Aids to Computation 8 (1954): 53–57, and in William Miehle, "Burroughs Truth Function Evaluator," Journal of the Association for Computing Machinery 4 (1957): 189–192.

Hao Wang's description of his use of the IBM 704 is in "Toward Mechanical Mathematics," IBM Journal of Research and Development 4 (1960): 2–22, reprinted in The Modeling of Mind, edited by Kenneth Sayre and Frederick J. Crosson (Notre Dame, IN: University of Notre Dame Press, 1963). On computer simulation, see Allen Newell and H. A. Simon, "Computer Simulation of Human Thinking," in Science 134 (1961): 2011–2017, and references cited there. On the Shannon-Moore relay circuit analyzer, see Shannon and Moore's "Machine Aid for Switching Circuit Design," in Proceedings of the Institute of Radio Engineers 41 (1953): 1348–1351.