3
$\begingroup$

We are able to perform universal computations with the reversible model. Basically, during the computations, no information should be erased, so that no involved entropy increase would occur.

Are reversible computations alone sufficient to create a complete computer? The machine should be able to:

  • load programs,
  • handle user input,
  • provide an output.

I suspect that, for example reading user's input requires information deletion which cannot be avoided.

Improve this question
$\endgroup$
3
  • $\begingroup$ IMHO This isn't a research level question. $\endgroup$
    – Pratik Deoghare
    Commented Feb 1, 2012 at 6:25
  • 2
    $\begingroup$ @Pratik Deoghare This is actually a very non-trivial question. Peter Shor provides the outline of a possible answer below (they key part is "reversible operations between the user and the comptuer"), but the devil is in the details: modeling I/O is, as far as I know, an unsolved problem in reversible computing. $\endgroup$
    – funkstar
    Commented Feb 1, 2012 at 9:31
  • $\begingroup$ @funkstar Well, that reflects my naivety. :D Thanks! $\endgroup$
    – Pratik Deoghare
    Commented Feb 1, 2012 at 10:21

2 Answers 2

Reset to default
9
$\begingroup$

You need workspace (registers set to 0) to read the user's input. Once you've read it, and completed the program, the user needs to erase the input and the output in order to restore the workspace. However, if you assume that the user wants to keep a copy of the input and the output, this is possible to do reversibly.

Similarly for the program, to erase the program from the computer there needs to be another copy stored somewhere.

If you don't allow any reversible operations between the user and the computer, and you insist that everything be done reversibly, then you can't load input into the computer, and you have a useless machine.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ After reading this answer, I cannot help imagining a fastest computer in the world whose only issue is that it cannot receive input from user or produce output to user. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 30, 2012 at 3:58
  • 5
    $\begingroup$ Maybe it exists. Somewhere in the world there may be a diamond crystal in which the spins of the impurities interact in such a way that they just happen to form a universal quantum computer ... $\endgroup$
    – Peter Shor
    Commented Jan 30, 2012 at 14:33
-3
$\begingroup$

The above answer seems wrong to me: the basic idea is that logically reversible and physically reversible are distinct.

Consider a quantum computer (reversible by nature), in the memory you store qbits, after you do an operation, you store the qbits that are important, those qbits that are no longer useful after the operation can be expelled from the memory and discarded. (lost in the endless space of the universe) Although the operations are logically reversible, it is no longer necessary to store all the qbits and we deliberately lose some (thus not physically reversible).

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.