Reversible programs with finite execution steps are well studied. For example, a Turing machine whose transitions are reversible and halts can be executed backwards consuming its tape in the reverse order. A variant of Turing machines with distinct input, output, and work tapes can be similarly executed in reverse to consume its output and regenerate its input, assuming it halted with an empty work tape in the forward execution (to avoid the possibility of stashing input information in the work tape).

Is there any work for the equivallent concepts in the setting of interactive programs (in the spirit of https://en.wikipedia.org/wiki/Interactive_computation)? In the three-tape Turing machine model described, it is clearly possible to have infinite interactive runs consuming an infinite input stream and emitting an infinite output stream while storing intermediate results in the work tape. Some of these programs are clearly reversible in an analogous way to the finite programs, but cannot be covered by that formalism if they are non-halting. How can we characterize reversible interactive programs in this model? We need to exclude programs that simply stash away their input in the work tape, but unlike the finite case, we can't simply require that the program ends with an empty work tape.

Is there any work on such reversible interactive programs?

  • $\begingroup$ Wondering if you found anything. $\endgroup$ – Lance Pollard Jul 2 '18 at 0:39
  • 1
    $\begingroup$ Unfortunately no, and I am still interested in this. $\endgroup$ – Akuri Jul 3 '18 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.