Abstract & Keywords 
SRL is a total programming language with distinctive features: (i) every program that mentions n registers defines a bijection Znâ†’Zn, and (ii) the generation of the SRLprogram that computes the inverse of that bijection can be automatic. Containing SRL a very essential set of commands, it is suitable for studying strengths and weaknesses of reversible computations. We deal with the fixed points of SRLprograms. Given any SRLprogram P, we are interested in the problem of deciding if a tuple of initial register values of P exists which remains unaltered after its execution. We show that the existence of fixed points in SRL is undecidable and complete in Î£10. We show that such problem remains undecidable even when the number of registers mentioned by P is limited to 12. Moreover, if we restrict to the linear programs of SRL, i.e. to those programs where different registers control nested loops, then the problem is already undecidable for the class of SRLprograms that mention no more than 3712 registers. Last, we show that, except for trivial cases, finding if the number of fixed points has a given cardinality is also undecidable.
Keywords: Reversible computing, Fixed points, Decidability

@article{matos2020tcs,
volume = {813},
author = {Armando B. Matos and Luca Paolini and Luca Roversi},
issn = {03043975},
keywords = {Reversible computing, Fixed points, Decidability},
url = {http://www.sciencedirect.com/science/article/pii/S0304397519306280},
abstract = {SRL is a total programming language with distinctive features: (i)
every program that mentions n registers defines a bijection
Znâ†’Zn, and (ii) the generation of the SRLprogram that computes
the inverse of that bijection can be automatic. Containing SRL a
very essential set of commands, it is suitable for studying
strengths and weaknesses of reversible computations. We deal with
the fixed points of SRLprograms. Given any SRLprogram P, we are
interested in the problem of deciding if a tuple of initial
register values of P exists which remains unaltered after its
execution. We show that the existence of fixed points in SRL is
undecidable and complete in Î£10. We show that such problem
remains undecidable even when the number of registers mentioned by
P is limited to 12. Moreover, if we restrict to the linear
programs of SRL, i.e. to those programs where different registers
control nested loops, then the problem is already undecidable for
the class of SRLprograms that mention no more than 3712
registers. Last, we show that, except for trivial cases, finding
if the number of fixed points has a given cardinality is also
undecidable.},
title = {The fixed point problem of a simple reversible language},
pages = {143  154},
journal = {Theoretical Computer Science},
doi = {https://doi.org/10.1016/j.tcs.2019.10.005},
year = {2020},
}
This document was generated by bib2html 3.3.
(Modified by Luca Paolini, under the GNU General Public License)