**From:** Larry (*entropy@farviolet.com*)

**Date:** Fri Jan 05 2007 - 11:58:53 MST

**Next message:**Gary F. York: "Re: the end of fermi's paradox?"**Previous message:**Philip Goetz: "Re: the end of fermi's paradox?"**In reply to:**Philip Goetz: "Re: the end of fermi's paradox?"**Next in thread:**Chris Hibbert: "Re: the end of fermi's paradox?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

On Fri, 5 Jan 2007, Philip Goetz wrote:

*> On 1/5/07, Larry <entropy@farviolet.com> wrote:
*

*>>
*

*>> Interestingly some useful problems can be stated in a fashion that doesn't
*

*>> require discarding of bits, and theoritically can harness this should
*

*>> we manage to build decent quantum computers.
*

*>
*

*> Say you have a computer with n bits, and they all have some value.
*

*> You want to compute a result of m < n bits.
*

*> We know this value isn't present in the n bits at the start (because
*

*> otherwise you wouldn't need to compute it).
*

*> It must be present in the n bits at the end of computation.
*

*> How can you put those m bits into the set of n bits without erasing m of
*

*> them?
*

The trick is reversible logic gates, three bits in, three bits out, and

self inverse. One example is a controlled exchange of two bits, passing

through the control bit.

C is the control bit, A & B get exchanged

A B C | A' B' C'

0 0 0 | 0 0 0

0 0 1 | 0 0 1

0 1 0 | 0 1 0

0 1 1 | 1 0 1

1 0 0 | 1 0 0

1 0 1 | 0 1 1

1 1 0 | 1 1 0

1 1 1 | 1 1 1

You can compute something, then unwind it back to the original by

reversing all the operations. You've not had to discard any information.

Any one state completely defines both the next and the previous state.

All algorithms can be implemented with these gates, as this gate can

be used to make any of the standard logic gates. However most useful

algorithms as normally implemented will have a requirement for

bits that grows without bounds. In a normal computer you dump these

surplus bits over board ultimately through the heat sink and into

the cosmic /dev/null, as a result a normal computer cannot be run

backward, the information has been discarded.

**Next message:**Gary F. York: "Re: the end of fermi's paradox?"**Previous message:**Philip Goetz: "Re: the end of fermi's paradox?"**In reply to:**Philip Goetz: "Re: the end of fermi's paradox?"**Next in thread:**Chris Hibbert: "Re: the end of fermi's paradox?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*
This archive was generated by hypermail 2.1.5
: Wed Jul 17 2013 - 04:00:57 MDT
*