The fixed point problem of a simple reversible language.

SRL is a total programming language with distinctive features: (i) every program that mentions n registers defines a bijection Z n → Z n , and (ii) the generation of the SRL -program 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 SRL -programs. Given any SRL -program 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 Σ 1 0. 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 SRL -programs 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. [ABSTRACT FROM AUTHOR]