Content deleted Content added
Line 53:
=== Reversible version ===
The Reversible Structured Program Theorem<ref>{{cite journal |last1=Yokoyama |first1=Tetsuo |last2=Axelsen |first2=Holger Bock |last3=Glück |first3=Robert |title=Fundamentals of reversible flowchart languages |journal=Theoretical Computer Science |date=January 2016 |volume=611 |pages=87–115 |doi=10.1016/j.tcs.2015.07.046|doi-access=free}}</ref> is an important concept in the field of [[reversible computing]]. It posits that any computation achievable by a reversible program can also be accomplished through a reversible program using only a structured combination of control flow constructs such as sequences, selections, and iterations. Any computation achievable by a traditional, irreversible program can also be accomplished through a reversible program, but with the additional constraint that each step must be reversible and some extra output.<ref>{{cite journal |last1=Bennett |first1=C. H. |title=Logical Reversibility of Computation |journal=IBM Journal of Research and Development |date=November 1973 |volume=17 |issue=6 |pages=525–532 |doi=10.1147/rd.176.0525}}</ref> Furthermore, any reversible unstructured program can also be accomplished through a structured reversible program with only one iteration without any extra output. This theorem lays the foundational principles for constructing reversible algorithms within a structured programming framework.
For the Structured Program Theorem, both local<ref name="BohmJacopini"/> and global<ref>{{cite journal |last1=Cooper |first1=David C. |title=Böhm and Jacopini's reduction of flow charts |journal=Communications of the ACM |date=August 1967 |volume=10 |issue=8 |pages=463 |doi=10.1145/363534.363539}}</ref> methods of proof are known. However, for its reversible version, while a global method of proof is recognized, a local approach similar to that undertaken by Böhm and Jacopini<ref name="BohmJacopini">{{cite journal |last1=Böhm |first1=Corrado |last2=Jacopini |first2=Giuseppe |title=Flow diagrams, turing machines and languages with only two formation rules |journal=Communications of the ACM |date=May 1966 |volume=9 |issue=5 |pages=366–371 |doi=10.1145/355592.365646}}</ref> is not yet known. This distinction is an example that underscores the challenges and nuances in establishing the foundations of reversible computing compared to traditional computing paradigms.
| |||