history
karl robold
Ed Fredkin
> what is the history of the Fredkin-Gate?
In 1974, I decided to quit as director of MIT's Laboratory for
Computer Science. I wanted to work full time on my ideas about
computational models of physics. Feynman suggested that I come to
Caltech for a year where I would teach him about computer science and
he would teach me about Quantum Mechanics. So Feynman arranged for me
to be invited to Caltech as a Fairchild Distinguished Scholar, along
with Stephen Hawking. Before arriving at Caltech, I decided that I
would tackle the problem of reversible computation. At Caltech, I had
a dual appointment (and 2 offices) one in Physics and the other in
Computer Science, but I quickly decided to spend all my time in
Physics. As part of my preparation I read what I could find about
Carnot. I was impressed to learn that his discovery of the Carnot
cycle (a reversible heat engine) was made during a time when the
Caloric theory was in vogue (that Heat was a conserved quantity).
When Joule and others discovered that heat was not a conserved
quantity, Carnot's argument was considered flawed since Carnot assumed
that the caloric theory was correct. It was only much later that it
was realized that Carnot's argument was so basic and fundamental that
it transcended the question as to whether or not the Caloric theory
was correct!
I took this lesson to heart and decided to consider circuits where
everything was conserved -- both the information (for reversibility)
and the signaling quantities (the 1's and 0's), since that seemed more
physically correct, and since my goal was to find a bridge between
classical physics and computation.
I had earlier had great success in showing universality in cellular
automata by finding models capable of constructing wires and digital
logic gates as opposed to a Turing machine. So I decided to find a
system of gates and wires that were universal while conserving the
signaling quantities. Once I had these ideas in my head I decided to
look for the simplest and most symmetric such gate. It then took
about 15 minutes to reject all 2 input 2 output gates and to discover
that a simple 3 input 3 output gate was sufficient. I called it
"Conservative Logic" -- others called them "Fredkin Gates".
When I returned to MIT various people tried to get me to write a paper
on Conservative Logic, but I wasn't in the habit of writing papers. I
thought up the Billiard Ball model in response to critics at MIT who
tried to discredit my ideas by claiming that there could not be a
physically correct model of Fredkin gates. The BBM succeeded in
quieting that particular criticism. Finally Tom Toffoli agreed to
write the paper, "Conservative Logic," for me.
Ed F
charliew2
Ed Fredkin <edfr...@yahoo.com> wrote in message
news:c91c8a19.04041...@posting.google.com...
> "karl robold" <k.ro...@t-online.de> wrote in message
news:<c5sbf0$57fig$1...@ID-225840.news.uni-berlin.de>...
> > what is the history of the Fredkin-Gate?
>
(cut of an excellent history lesson from Ed Fredkin)
Since I'm a neophyte in this area, I'm hoping that everyone will demonstrate
a bit of patience. What are the potential applications of Fredkin gates?
Frank Buss
> Since I'm a neophyte in this area, I'm hoping that everyone will
> demonstrate a bit of patience. What are the potential applications of
> Fredkin gates?
If you can build a Fredkin gate in real, you could possible build computers
with a fraction of power consumption than today computers, because you
don't destroy information like normal gates do:
http://c2.com/cgi/wiki?ReversibleLogic
--
Frank Buß, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Ed Fredkin
While there are proposed near term applications for Fredkin gates or
other forms of reversible logic, the big issue has to do with the
future. We are studying futuristic CPU designs of molecular computers
where could be more than 10^20 circuit elements per cc. If all
sources of heat other than that due to local loss of information
(Landauer dissipation) are eliminated, the necessary power dissipation
for a 1 cm. cube of computer circuits could be hundreds of kilowatts.
These designs are compact 3-D structures with no obvious way to get
the heat out. There are other tricks to deal with this problem, but
there is really very little incremental cost associated with going to
reversible logic.
Ed F
Frank Buss
> These designs are compact 3-D structures with no obvious way to get
> the heat out. There are other tricks to deal with this problem, but
> there is really very little incremental cost associated with going to
> reversible logic.
I don't know much details about building chips, is it possible to build
reversible gates with conventional silicon chips? I mean, of course you can
use normal transistors for building Convervative Logic, but the transistors
of the gates are not reversible and produce heat, I think. If you need to
use another material and procedures the incremental cost compared to today
chips will be high.
charliew2
> "charliew2" <char...@ev1.net> wrote in message
> news:<1088a8e...@corp.supernews.com>...
>> Ed Fredkin <edfr...@yahoo.com> wrote in message
>> news:c91c8a19.04041...@posting.google.com...
>>> "karl robold" <k.ro...@t-online.de> wrote in message
>> news:<c5sbf0$57fig$1...@ID-225840.news.uni-berlin.de>...
>>>> what is the history of the Fredkin-Gate?
>>>
>>
>> (cut of an excellent history lesson from Ed Fredkin)
>>
>> Since I'm a neophyte in this area, I'm hoping that everyone will
>> demonstrate a bit of patience. What are the potential applications
>> of Fredkin gates?
>
> While there are proposed near term applications for Fredkin gates or
> other forms of reversible logic, the big issue has to do with the
> future. We are studying futuristic CPU designs of molecular computers
> where could be more than 10^20 circuit elements per cc. If all
> sources of heat other than that due to local loss of information
> (Landauer dissipation) are eliminated, the necessary power dissipation
> for a 1 cm. cube of computer circuits could be hundreds of kilowatts.
So the "Fredkin gate" design avoids the high energy dissipation issue?
By the way, isn't it "neat" that biological "circuits" are many cubic
centimeters, but require the dissipation of only approximately 100 watts?
charliew2
> edfr...@yahoo.com (Ed Fredkin) wrote:
>
>> These designs are compact 3-D structures with no obvious way to get
>> the heat out. There are other tricks to deal with this problem, but
>> there is really very little incremental cost associated with going to
>> reversible logic.
>
> I don't know much details about building chips, is it possible to
> build reversible gates with conventional silicon chips? I mean, of
> course you can use normal transistors for building Convervative
> Logic, but the transistors of the gates are not reversible and
> produce heat, I think. If you need to use another material and
> procedures the incremental cost compared to today chips will be high.
So reversible logic, by its very nature, avoids heat generation?
Ed Fredkin
Michael Frank did his MIT doctoral theses on this topic:
http://www.aeiveos.com/~bradbury/Authors/Computing/Frank-MP/
There are reasons why reversible logic might make sense implemented in
Silicon.
The use of reversible logic only eliminates some sources of heat. For
example if your circuits use ordinary wires, then there is the I^2 R
loss due to the resistance in the wires. In contemporary CPU chips
such as Intel or Power PC, the heat generated due to information loss
(Landauer dissipation) is trivial -- almost too small to measure.
However it is obvious that Landauer dissipation may someday become the
dominant factor. The formula for Landauer dissipation is Log(2) k t
per bit. k is Boltzman's constant
k = 1.380 6503(24) в 10^-23 J/k
and t is the temperature in degrees Kelvin.
A modern CPU loses about 100,000 bits per floating point instruction.
At 10 Giga FLOPS, and 140 degrees Fahrenheit (333 Kelvin) we have
Log(2) k 333/second=3x10^-11 Watts. Not much!
But if Moore's law holds, then before the end of the century, we will
have to solve this problem or each CPU will need its own nuclear
powerplant. In any case, there's no need to hurry.
Ed F
Tom Knight
> I don't know much details about building chips, is it possible to build
> reversible gates with conventional silicon chips? I mean, of course you can
> use normal transistors for building Convervative Logic, but the transistors
> of the gates are not reversible and produce heat, I think. If you need to
> use another material and procedures the incremental cost compared to today
> chips will be high.
Yes, it is possible to build asymptotically zero energy dissipation
logic from completely conventional silicon CMOS technology, as
predicted (in principle) by Landauer. See the MIT thesis by Saed Younis:
``Asymptotically Zero Energy Computing Using Split-Level Charge
Recovery Logic,'' July, 1994
You might also want to look at these two papers:
Frank MP, Vieri C, Ammer MJ, and Knight TF, ``A Scalable Reversible
Computer in Silicon,'' Unconventional Models of Computation, New
Zealand, January, 1998.
Vieri C, Ammer MJ, Wakefield A, Svenson L, Athas W, and Knight TF,
``Designing Reversible Memory,'' Unconventional Models of Computation,
New Zealand, January, 1998.