Was ist an der Methode "Save the Input" des reversiblen Rechnens fehlerhaft?

9

Ich bin ein Student, der gerade anfängt, über reversibles Rechnen zu lesen. Ich weiß, dass irreversible Berechnungen aufgrund des Landauer-Prinzips Wärme abführen (und reversible nicht). Ich sprach es mit meinem Professor an, der noch nie von Reversible Computing gehört hatte, und er hatte Schwierigkeiten zu verstehen, warum die Theorie des Reversible Computing nicht trivial war.

Sein Punkt war nur, dass Sie die Eingabe immer speichern können, dh für jede Funktion , die Sie umkehrbar machen möchten, definieren Sie eine neue Funktion (oder und Sie geben einfach s für die letzten Bits der Eingabe ein), was die Ausgabe in den ersten Bits und die Eingabe in den anderen Bits zurückgibt . Um dann zu invertieren, verwerfen Sie einfach die Ausgabe und geben die von Ihnen gespeicherte Eingabe zurück.f:{0,1}n{0,1}nfreversible:{0,1}n{0,1}2n{0,1}2n{0,1}2n0nnnfreversible

Mein unmittelbarer Einwand war, dass dies mehr Speicher benötigt als die ursprüngliche Funktion - allerdings nur um einen konstanten Faktor. Die Beschränkung der Ausgabe auf Bits scheint jedoch die Interessantheit des Problems wiederherzustellen. Ist dies normalerweise mit reversiblem Rechnen gemeint?n

Ein weiterer Einwand schien zu sein, dass wir, wenn wir die Ausgabe verwerfen, etwas Irreversibles tun, das Wärme abführen wird. Aber wir haben den Ausgangszustand korrekt wiederhergestellt. Wie könnte er also irreversibel sein? Ich weiß nicht genug Physik, um zu verstehen, ob es für die gesamte Berechnung wichtig ist, dass die gesamte Berechnung reversibel ist, oder ob jeder Schritt auch reversibel sein muss oder ob diese Idee nur auf dem falschen Baum steht .

Eli Rose - WIEDERHERSTELLEN VON MONICA
quelle

Antworten:

12

In Ihrer Diskussion über reversibles Rechnen fehlen zwei wichtige Merkmale des reversiblen Rechnens:

  1. Eine reversible Funktion muss eine Bijektion sein, und
  2. Die Reversibilität wird auf der Ebene der lokalen Gates definiert, nicht nur auf der globalen Ebene.

Insbesondere für Ihre Erweiterung von in Durch Kopieren stellen Sie keine Bijektion sicher, da Sie nicht erklären, was passiert, wenn die letzten Eingabebits für Ihre Funktion nicht .{0,1}n{0,1}n{0,1}2n{0,1}2nn0n

Was den zweiten Punkt betrifft, so ist dies aus physikalischer Sicht wirklich der wesentliche Teil des reversiblen Rechnens. Der physikalische Prozess kann die Erwärmung auf globaler Ebene nicht einfach "rückgängig machen", daher muss jedes Gate reversibel sein, damit die Schaltung im physikalisch relevanten Sinne reversibel ist.

Schließlich ist die Theorie des reversiblen Rechnens nicht unangemessen kompliziert, aber definitiv nicht trivial. Insbesondere gibt es einige Schaltungen, die mit strikt weniger Registern / Drähten nicht reversibel als reversibel implementiert werden können. Die Explosion beim Übergang von nicht reversibel zu reversibel ist jedoch nicht schlecht.

Im Allgemeinen höre ich selten, dass in klassischen CS-Kursen reversibles Rechnen auftaucht, da es für das klassische Rechnen selten relevant ist. Es ist jedoch ein wichtiges Thema im Quantencomputer, da alle Quantenschaltungen reversibel sind und man sorgfältig damit umgehen muss, was sich auf Ihren Junk-Drähten befindet, um unnötige Verwicklungen zu vermeiden.

Artem Kaznatcheev
quelle
Aha. Wie lautet also die formale Aussage "Jedes Tor muss reversibel sein" - muss die Übergangsfunktion der Turing-Maschine injektiv sein?
Eli Rose - WIEDERHERSTELLEN MONICA
2
@EliRose Reversible Computing wird im Gate-Modell definiert, nicht im TM-Modell. Ich bin mir nicht sicher, ob das TM-Modell eine vernünftige Definition enthält, aber es würde wahrscheinlich zumindest erfordern, dass die endliche Kontrolle reversibel ist. Umkehrbare Tore bedeuten also so etwas wie das Toffoli-Tor .
Artem Kaznatcheev
1
@ArtemKaznatcheev: Was ist mit den von Bennett eingeführten reversiblen Turingmaschinen (PDF-Link)?
Niel de Beaudrap
Kombinatorische Schaltungen können leicht mit reversibler Logik gehandhabt werden, aber alle nützlichen Computergeräte erfordern eine Rückmeldung. Man könnte ein Toffoli-Gate verwenden, um "A und nicht B" zu berechnen, und zwei solche Gates könnten verwendet werden, um einen Latch zu bauen, aber sobald die Rückmeldung eingerichtet ist, geht die Reversibilität aus dem Fenster.
Supercat
Was ist mit Quanten-TMs, deren zulässige Amplituden nur 0 oder 1 sein können? Dies scheint ein vernünftiger Weg zu sein, um ein reversibles TM zu definieren.
Marcos Villagra