Reversify any sequential algorithm

The Logic in Computer Science Column by Yuri Gurevich, Yuri Gurevich


To reversify an arbitrary sequential algorithm A, we gently instrument A with bookkeeping machinery. The result is a step-for-step reversible algo- rithm that mimics A step-for-step and stops exactly when A does.

Without loss of generality, we presume that algorithm A is presented as an abstract state machine that is behaviorally identical to A. The existence of such representation has been proven theoretically, and the practicality of such representation has been amply demonstrated.

Full Text:



  • There are currently no refbacks.