Edward Fredkin

Ed Fredkin at a PDP-1, around 1960. Image: Computer History Museum, public domain, via Wikimedia Commons.

Los Angeles, Caltech, the Air Force

Fredkin was born in Los Angeles on 2 October 1934, the youngest of three children of Russian-Jewish immigrants. His father Manuel had built a chain of radio stores that the Depression destroyed, and made a competition of the dinner table, challenging his sons on matters of fact and distrusting books and experts. The son absorbed both the competitiveness and the distrust. He took apart alarm clocks, built rockets out of cardboard and foil, wired together banks of 45-volt batteries to draw arcs, and was picked last for every game: “They’d choose everybody but me, and then there’d be a fight as to whether one side would have to take me.”

He entered Caltech in 1952 expecting better company, found the same social order, discovered that not studying has consequences, and flunked out partway through his sophomore year. He joined the Air Force and trained as a fighter pilot. In 1956 his unit, the Air Proving Ground Command, was handed the job of testing SAGE, the computerised air-defense system, and sent him to MIT’s Lincoln Laboratory to learn computing. “Everything made instant sense to me,” he said. “I just soaked it up like a sponge.” SAGE turned out to be too complex for the Air Force to test and the work was contracted out, leaving Fredkin with a year and nobody giving him orders, and down the hall an IBM XD-1 the size of a house. He programmed it.

Bolt Beranek and Newman

He left the Air Force in 1958 for J. C. R. Licklider’s group at Bolt Beranek and Newman. Licklider’s verdict: “It was obvious to me he was very unusual and probably a genius, and the more I came to know him, the more I came to think that that was not too elevated a description.” The working pattern was fixed early. Licklider would set a problem, Fredkin would disappear for twenty or thirty hours and come back with an answer, often to a different question.

Two pieces of that period stuck. Asked how to search stored text for a partially specified string, he worked out the prefix tree and published “Trie Memory” in Communications of the ACM in September 1960, the only conventional academic paper he ever wrote; he named it after the middle syllable of retrieval, which is why the field has never agreed on how to pronounce it (see Data Structures). And on BBN’s PDP-1 he made John McCarthy’s idea of time-sharing practical by designing the machine’s sequence break system, the multi-channel interrupt facility that let a program be suspended and resumed on an external signal.

Triple-I

In 1962 Fredkin left to found Information International, Inc., with Roland Silver: no clients, no assets, and a founder with no degree. The first job came from the Woods Hole Oceanographic Institution, which had recorded deep-current data as dots of light on 16 mm film that no computer could read. Fredkin rented a projector, added a photomultiplier tube and parts milled at DEC, and turned it into a film reader. Lincoln Laboratory had the same problem with radar film, which paid $350,000, and programmable film readers at around $500,000 apiece became the company’s business. Triple-I went public on 8 January 1969 with Fredkin holding 57.7 percent of the stock, worth more than $10 million on paper.

The company’s second life belongs to film. Its FR-80 recorder and photomultiplier scanners were exactly what a visual-effects house needed, and its Motion Pictures Product Group produced the android point-of-view in Westworld (1973) and the graphics for TRON (1982); that story is told in Gary Demos. Fredkin himself had stepped down as chief executive in 1965 and left entirely in 1968. He always said the company’s course was set by a death: he had persuaded Ben Gurley, the designer of the PDP-1, to leave DEC and join him, intending to build computers, and on 7 November 1963 Gurley was shot dead through the window of his home in Concord, Massachusetts.

A Professor Without a Degree

Minsky and Licklider proposed Fredkin for the MIT faculty, and in 1968 Louis Smullin, head of electrical engineering, took the gamble: “We were a growing department and we wanted exciting people. And Ed was exciting.” Computer science had become an academic field so quickly that formal credentials were thin everywhere. Fredkin taught for about a year, was made a full professor with tenure, and in 1971 took over Project MAC, MIT’s time-sharing and AI laboratory (see Fernando Corbató and Time-Sharing and Marvin Minsky and the MIT AI Lab), running it until 1974. From 1975 he taught a course called Digital Physics.

The arrangement ended badly. Fredkin was simultaneously chief executive of a computer company and president of Boston’s CBS television affiliate, against an MIT rule limiting outside work, and in 1986, having agreed to convert to an adjunct professorship, he discovered that tenure does not follow. He was not reappointed. His own account was that he had been tricked; the department’s was that he had not been around.

Reversible Computing

In the autumn of 1974 Fredkin went to Caltech as a Fairchild Distinguished Scholar under Richard Feynman, on a deal: Fredkin would teach Feynman computing and Feynman would teach Fredkin physics. Carver Mead’s VLSI work had made the energy cost of computation a live question, and Rolf Landauer had shown at IBM in 1961 that only the erasure of information must dissipate energy. Everyone, Landauer included, assumed that discarding information was intrinsic to computing.

Fredkin showed it was not. His billiard-ball model computes with perfectly elastic balls bouncing off fixed mirrors, the presence or absence of a ball in a cell at a given moment standing for a bit; it is computationally universal and runs backwards, so its whole history can be recovered by stopping it and reversing the balls. Charles Bennett at IBM had independently proved reversible computation possible by another route. The logic element behind it, a three-input gate that swaps two of its inputs under control of the third and throws nothing away, is the Fredkin gate; he and Toffoli set it out in “Conservative Logic” in the International Journal of Theoretical Physics in 1982. It is now standard equipment in quantum computing, where every gate must be reversible by the nature of the physics.

In May 1981 Fredkin, Landauer and Toffoli organized the Physics of Computation conference at MIT’s Endicott House in Dedham, about sixty people including Feynman, John Wheeler, Freeman Dyson, Konrad Zuse and Gregory Chaitin. Feynman’s talk there, “Simulating Physics with Computers,” argued that a classical machine cannot efficiently simulate quantum mechanics and that a quantum machine could, which is the founding statement of quantum computing.

Digital Physics

Fredkin’s own conviction, which he held from the 1960s to his death, went further than any of his colleagues would follow. He believed that space and time are discrete, that every point of space is a cell of a three-dimensional cellular automaton, and that one simple rule, applied everywhere simultaneously, produces everything physics describes. Particles are patterns of bits; an electron in motion is a pattern moving while the bits stay put and blink. “You see, I don’t believe that there are objects like electrons and photons,” he told Robert Wright, who profiled him for The Atlantic in 1988. “What I believe is that there’s an information process, and the bits, when they’re in certain configurations, behave like the thing we call the electron.”

He could not produce the rule, and he could not produce the argument. Minsky called him “Einstein-like” in his ability to find deep principles by simple excursions; Feynman said that if anyone came up with a new way of looking at physics it would be Fredkin. Neither believed the universe was a computer. His evidence was cumulative and circumstantial and he knew it: “It’s like there’s an animal I want to find. I’ve found his footprints. I’ve found his droppings. I’ve found the half-chewed food. In every case it fits one kind of animal, and it’s not like any animal anyone’s ever seen.” Graduate students who worked on it were warned by their friends that it would end their careers, and for three decades he published almost nothing on the subject, his one substantial paper appearing in Physica D in 1990. Stephen Wolfram, who met him in 1982 and was then doing the systematic experiments on cellular automata that Fredkin never did, thought the physics naive and said so for forty years without noticeable effect.

The Island, the Television Station, and the Soviet Deal

In 1970, expecting a third world war, Fredkin bought a 125-acre island in the British Virgin Islands from a shipwreck salvor, having seen the advertisement in a newspaper in a dentist’s waiting room. Moskito Island came with a small resort, Drake’s Anchorage, which he and his wife Joyce ran for years; Richard Branson bought neighboring Necker Island in 1978 and bought Moskito from the Fredkins in 2007. Fredkin flew himself there in an amphibious Cessna. Feynman was best man at his 1980 wedding on the islands, and in January 1982 Fredkin convened a second physics-and-computation meeting on the beach.

The other ventures came and went: the New England Television Corporation, which ran Boston’s CBS affiliate; Three Rivers Computer Corporation in Pittsburgh, maker of the PERQ workstation, which he took over as chief executive and could not save; the Reliable Water Company, built around a low-energy reverse-osmosis design he invented for his island’s water problem. The strangest was foreign policy. In 1984, visiting Moscow, Fredkin argued to Evgeny Velikhov of the Soviet Academy of Sciences, and to the Reagan administration at home, that personal computers would break the state’s control over the copying of information, and set up Fredkin Enterprises to export machines that would clear the CoCom embargo, with his student Norman Margolus assigned to read the regulations. He also proposed trading computers for the release of the exiled physicist Andrei Sakharov. The Reagan Presidential Library holds a file on it; Velikhov ordered 100 machines in November 1984 and hoped for 10,000 more; the export licences moved slowly, some computers with a Cyrillic hack eventually shipped, and Sakharov stayed in Gorky until 1986. The reclusive computer scientist on his own island who talks to both superpowers was close enough to the public image that the screenwriters of WarGames (1983) are generally said to have modelled Professor Falken on him.

The Chess Prize

In 1980 Fredkin put up $100,000 through his foundation, administered by Carnegie Mellon, for the first computer program to beat a reigning world chess champion, with interim awards along the way: $5,000 to Ken Thompson and Joe Condon for Belle, the first machine to be rated a master by the US Chess Federation, in 1983, and $10,000 to the Deep Thought team in 1989 after it reached grandmaster-level play. The full prize was awarded at AAAI-97 to Feng-hsiung Hsu, Murray Campbell and Joseph Hoane for Deep Blue, which had beaten Garry Kasparov that May. Carnegie Mellon and Fredkin put the money into two professorships. A parallel prize he funded for automated theorem proving, administered through the American Mathematical Society, gave out milestone awards but never its grand prize.

Later Years

Boston University’s physics department took him in after MIT let him go, on the recommendation of Minsky’s neighbour Larry Sulak; Carnegie Mellon made him a professor of computer science in 2003 at the suggestion of Raj Reddy, who summarised him as a man who “could have more ideas in a day than many of us could in a month.” He chaired the restoration of a PDP-1 at the Computer History Museum, the machine he had first programmed at BBN. He kept working on digital philosophy and on the architecture of a reversible computer that would still make sense after another century of shrinking transistors. He died in Brookline, Massachusetts, on 13 June 2023, aged 88.

The reversible gate is in every quantum-computing textbook, the trie is in every data-structures course, and the universe has not yet been shown to be a cellular automaton.

📚 Sources

• Edward Fredkin — Wikipedia (born 2 October 1934 in Los Angeles, died 13 June 2023 in Brookline; Caltech dropout and the Air Force; Lincoln Laboratory and SAGE from 1956; BBN from 1958; Information International founded 1962; MIT full professor 1968 without a degree; Project MAC 1971–1974; the trie, the Fredkin gate, the billiard-ball computer; Boston University and Carnegie Mellon; the Dickson Prize 1984; Falken in WarGames; the PDP-1 restoration at the Computer History Museum)
• Robert Wright, “Did the Universe Just Happen?”, The Atlantic, April 1988 (the childhood and Manuel Fredkin, “they’d choose everybody but me”; flunking out of Caltech; the Air Proving Ground Command, SAGE and the XD-1, “I just soaked it up like a sponge”; Licklider’s assessment and the working pattern at BBN; the Woods Hole film reader, the $350,000 Lincoln contract and the $500,000 film readers; Minsky, Licklider and Smullin on the 1968 appointment; the Caltech year with Feynman and the billiard-ball computer; Landauer 1961 and Bennett’s independent proof; the island, the 125 acres and Drake’s Anchorage; Minsky’s “Einstein-like” and Feynman’s verdict; “there’s an information process”; the animal-tracks quote; graduate students warned off; the 1986 adjunct episode and the CBS affiliate; the Fredkin Prize at $100,000)
• Stephen Wolfram, “Remembering the Improbable Life of Ed Fredkin (1934–2023) and His World of Ideas and Stories”, 22 August 2023 (the sequence break system on the PDP-1 and McCarthy’s time-sharing idea; Roland Silver as co-founder; Ben Gurley’s recruitment and his murder on 7 November 1963; the public offering on 8 January 1969 and the 57.7 percent stake; the 1970 island purchase from Bert Kilbride and the dentist’s-office advertisement; Branson and Necker Island; Feynman as best man in 1980; the January 1982 island conference; Three Rivers and the PERQ, New England Television, Reliable Water; the 1984 Moscow visit, Velikhov, the Kremlin talk, Fredkin Enterprises, Margolus and CoCom, the Sakharov proposal, the Reagan library file and the November 1984 order for 100 machines; Sulak and Boston University after the MIT ejection; Carnegie Mellon in 2003 through Raj Reddy; the theorem-proving prize)
• SCS Mourns Loss of Computer Visionary, Entrepreneur Edward Fredkin — Carnegie Mellon School of Computer Science, June 2023 (Project MAC, the Fredkin Prize created in 1980 and awarded to the Deep Blue team in 1997, the two endowed professorships, Raj Reddy’s “more ideas in a day”)
• Edward Fredkin, 88, “visionary” scientist and fighter pilot — Boston.com, 21 June 2023 (death on 13 June 2023 at 88; the Air Force at 19 and Lincoln Laboratory; MIT, Boston University and Carnegie Mellon; the Dickson Prize; his wife Joycelin and his children)
• Fredkin — Trie Memory, Communications of the ACM 3(9), September 1960, 490–499
• Fredkin & Toffoli — Conservative Logic, International Journal of Theoretical Physics 21(3–4), 1982, 219–253
• Fredkin — Digital mechanics: an informational process based on reversible universal cellular automata, Physica D 45(1–3), 1990, 254–270
• The Physics of Computation Conference — MIT Endicott House (6–8 May 1981 at Endicott House in Dedham; Fredkin, Landauer and Toffoli as organisers; about sixty attendees including Feynman, Wheeler, Dyson, Zuse and Chaitin; Feynman’s “Simulating Physics with Computers”)
• Belle (chess machine) — Wikipedia (the 1983 USCF master rating and the $5,000 Fredkin prize)
• Deep Thought (chess computer) — Wikipedia (the $10,000 intermediate prize)
• Mosquito Island — Wikipedia (Fredkin’s purchase from Bert Kilbride in 1970 and the 2007 sale to Richard Branson)
• Deep Blue (chess computer) — Wikipedia (the $100,000 Fredkin Prize paid to the Deep Blue team by Carnegie Mellon in 1997)