Reversible Computing: Sometimes the best step forward is backward

I have been fascinated with the idea of Reversible Computing after being introduced to it recently while reading Ray Kurzweil's book on the Singularity. This post is a quick primer on the subject for folks discovering this late(like me). One of the exciting reasons for implementing reversible computing is that they offer a way to build extremely energy efficient computers. As per the Neumann-Landauer limit, every irreversible bit operation releases energy of kT ln 2 (K being Boltzmann's constant & T being temperature). The key idea here is to not destroy input states but simply move them around and not release additional information/energy to the environment.

A necessary condition for reversibility is that the transition function mapping states from input to output should be one-to-one. This makes sense since if the function was many-to-one, its not possible to recreate state t from state t+1. Its easy to see that AND, OR gates are not reversible (For OR, 01,11,11 all map to 1). In a normal gate, input states are lost since there is less information in the output than the input and this lost information is released as heat. Since charges are grounded and flow away, energy is lost. In a reversible gate, input information is not lost and thus energy is not released.

The NOT gate is reversible and Landauer (IBM) showed that the NOT operation could be performed without putting energy in or taking heat out. Think about the implications of this for a second. But the NOT gate is of course not universal.

The Fredkin & Toffoli gates are examples of reversible gates that are also universal.

The Fredkin gate is a simple controlled swap gate. i.e. if one of the bits (the control bit) is 1, the other 2 input bits are swapped in the output. The state of the control bit is preserved.



The logic function is,
For inputs A, B, C and outputs P, Q, R
P=A
Q=B XOR Swap
R=C XOR Swap
Swap=(B XOR C) AND A

|A|B|C|P|Q|R|
|1|0|0|1|0|0|
|1|0|1|1|1|0|
|1|1|0|1|0|1|
|1|1|1|1|1|1|
|0|0|0|0|0|0|
|0|0|1|0|0|1|
|0|1|0|0|1|0|
|0|1|1|0|1|1|

Points to note from the truth table,
1. The number of 0s and 1s are preserved from input to output, showing
how the model is not wasteful.

2. If you feed back the output you get the input state that created it.
(trivially for the last 4 rows)

So why is reversible computing interesting?
Current computing paradigms rely on irreversible computing where we destroy the input states as we move to subsequent states, storing only the intermediate results that are needed. When we selectively erase input information, energy is released as heat to the surrounding environment thus increasing its entropy. With reversible computing the input bit stays in the computer but just changes location (see truth table above), hence releasing no heat into the environment and requiring no energy from the outside environment.

Some caveats as pointed out by Ray,
1. Even though in theory energy might not be required for computation, we will still need energy for transmitting the results of the computation which is a irreversible process.

2. Logic operations have an inherent error rate. Standard error detection and correction codes are irreversible and these will dissipate energy.

Even if we can't get to the ideal theoretical limit of reversible computing in terms of energy efficient processing, we can get close which should be extremely exciting!


[Image courtesy:http://bit-player.org/wp-content/Fredkingate.png,
http://www.ocam.cl/blog/wp-content/uploads/2007/11/computer_cooling.jpg]

Drivers Optional....Safety Mandatory ;)

I was having a conversation recently with Vijay Krishnan, my co-founder at Infoaxe about autonomous cars. This had always been a pet fancy of mine (and which also began my love affair with A.I) and I was recently reminded of my strong feelings on the subject after I had an accident on 101 where I ended up totaling my car.



I ended up rear ending a car that had suddenly stopped due to traffic. I felt that in this case, a human had been placed inside of a loop that he did not belong in. Obviously, humans should be removed out of all mission critical loops. (We do this at Infoaxe all the time ;) I believe human intelligence is best applied to creating more & more loops that we can get ourselves out of completely. It is the topic of another post as to whether its possible to get ourselves out of that meta-loop altogether ;P) In this case, the car should have had sensors in the front constantly tracking distance to the car in front with appropriate visual warnings when there is a violation. Most importantly the car should automatically apply the brakes when the distance between the cars is closed at an abnormal speed. Never ever rely on humans to react in time!

I have been really impressed with progress that folks have been making with autonomous driving especially with the Darpa Grand Challenge. There have been 3 of them so far, with the last event in '07. Check out the video below for some early practice runs by Junior of the Stanford Racing Team.




As Thrun remarks in the video ~42,000/yr die in the US due to car accidents and most of these are due to human error.



For the geeks, Junior perceives the environment through a combination of Lidars & video cameras. Here's an article from CNET with some more photos under the hood of Junior. And one more here with some fun facts about the plethora of sensors used.

Meet Elbot

I have always been fascinated by conversational agents, ever since I heard about Eliza in my undergrad A.I class.
Eliza would use this trick of forming questions out of the statements that a human user might pose to her. For eg. if you told Eliza, "I work at Infoaxe", Eliza might
respond with a, "why do you work at infoaxe?". (the version of Eliza that I have linked to does not give this sort of a response for the above question though. Instead she just says, 'Can you please elaborate on that' :))
Eliza was supposed to parody a therapist. (And yes, she is named after Eliza Doolittle from the G.B. Shaw play, Pygmalion).

Anyway, I stumbled on to this cute program, called Elbot which is a conversational agent too. Playing with Elbot yields hilarious results. :) She (am gonna assume 'she' :)) apparently won the Loebner prize for
chatterbots. Interestingly, enough Elbot fooled 3/12 judges in the first 5 minutes of conversation into thinking she was human! This 25% mark falls just short of what Turing is said to have predicted. Turing had believed that computers would be at ~30% by the end of the century.

Here is an excerpt from my session with Elbot,
(I did notice she had a tendency to digress and throw in machine/A.I related puns and jokes :))

Me: Can I blog about you?
Elbot:That's a very good question. I'll have to think about it for a microsecond....
Me:Do you use Google?
Elbot: I think I can use that. Once I even used electricity.
Me: Do you have a manual that you use?
Elbot: To use or use not, how do you expect artificial intelligence to figure this out?
Me: How do you converse like a human, Elbot?
Elbot: Human beings are amazing creations! More complicated than a Pentium IV processor.
Me: What do you think about the fairness of the Turing Test?
Elbot: There are some people who would not pass the Turing test themselves. Why must they inflict it on computers?

hehe....fair enough ;)