Editing Open Problems (section)

= Relating space-bounded, logically reversible Turing machines with CRNs =

=== Overview ===
The overarching problem here is to understand how reversible CRNs
relate to other reversible computing models, particularly space
bounded reversible Turing machines (TMs).  If you want to develop a deeper
understanding of reversible computational complexity classes and work
on an interesting problem with a level of technical difficulty that is
amenable to making good progress within a week, then this might be the
problem for you.

===Context===
There is a rich history of research on reversible space
bounded Turing machines. Following his seminal results on
time-bounded, logically reversible TMs, Bennett (1973) asked whether
TM-SPACE$(s) =$ reversible-TM-SPACE$(s)$. Fifteen years later he made some
progress towards this, showing that TM-SPACE$(s) \subseteq
$ reversible-TM-SPACE$(s^2)$. Many others worked to improve Bennett's
result; finally Lange, McKenzie and Tapp (2000) answered Bennett's
1973 question in the affirmative.  More recently, Thachuk et
al. described what it means for a DNA strand displacement system (DSD)
to use space (or equivalently volume) efficiently. Roughly, just as
memory-efficient TMs reuse memory, space-efficient DSDs "recycle"
strands by running reactions in both the forward and reverse
directions.  We also introduced restricted CRN models that can be
compiled into DSDs in a space-preserving way.

While our CRN models have plausible physical realizations as DSD's, it
is not clear that logically reversible, space-bounded reversible TMs
have such physical realizations that preserve space. Roughly, the
problem is that such TMs may "run" all of their transitions in the
"forward" direction (rather than in both the forward and backwards
directions, as do our recycling CRNs and DSDs), and so when one tries
a straightforward approach to "compile" these space-bounded TMs into
DSDs, the space (or volume) blows up exponentially. Can this
exponential space blow-up be avoided?

=== Concrete problem ===
One concrete first step to tackling this would be to
study Bennett's 1989 construction. The description is at a fairly high level; it has an elegant and simple recursive structure that should be easily amenable to analysis. Is there a lower-level description, or "implementation" at the TM transition level, in which it is clear that transitions run alternately in the forwards and backwards direction? Progress on this should provide a nice strengthening of traditional complexity-theoretic results on space-bounded logically reversible computation and link this traditional work with current work on CRNs.

References.

Bennett 1989. 
Time/Space trade-offs for reversible computation
http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2013W/Bennett_Tradeoffs.pdf

Bennett 1973.
Logical Reversibility of Computation
http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2013W/Bennett_Reversibiity.pdf

Condon et al. 2012.
Less haste, less waste: On recycling and its limits in strand
displacement systems
http://rsfs.royalsocietypublishing.org/content/early/2012/02/08/rsfs.2011.0106.short

Thachuk, C., & Condon, A.  2012.
Space and energy efficient computation with DNA strand displacement systems.
http://www.cs.ubc.ca/~condon/papers/dna-pspace.pdf

=== Interested Participants ===

* [[User:Condon | Anne Condon ]]
* [[User:Doty | Dave Doty ]]
* [[User:dsolov | David Soloveichik ]]
* [[User:Thachuk | Chris Thachuk ]]
* [[User:Woods | Damien Woods ]]