@inproceedings{10.1007/978-3-540-85238-4_34,
    Abstract = {We investigate the decidability of the periodicity and the immortality problems in three models of reversible computation: reversible counter machines, reversible Turing machines and reversible one-dimensional cellular automata. Immortality and periodicity are properties that describe the behavior of the model starting from arbitrary initial configurations: immortality is the property of having at least one non-halting orbit, while periodicity is the property of always eventually returning back to the starting configuration. It turns out that periodicity and immortality problems are both undecidable in all three models. We also show that it is undecidable whether a (not-necessarily reversible) Turing machine with moving tape has a periodic orbit.},
    Address = {Berlin, Heidelberg},
    Author = {Kari, Jarkko and Ollinger, Nicolas},
    BookTitle = {Mathematical Foundations of Computer Science 2008},
    Editor = {Ochma{\'{n}}ski, Edward and Tyszkiewicz, Jerzy},
    File = {Periodicity and Immortality in Reversible Computing - mfcs - a - r.pdf},
    ISBN = {978-3-540-85238-4},
    Pages = {419--430},
    Publisher = {Springer Berlin Heidelberg},
    Title = {Periodicity and Immortality in Reversible Computing},
    Year = {2008},
    date-added = {2020-12-17 08:05:30 +0100},
    date-modified = {2020-12-17 08:05:30 +0100},
    doi = {10.1007/978-3-540-85238-4_34}
}

@inproceedings{10.1007/978-3-540-85238-4_34, Abstract = {We investigate the decidability of the periodicity and the immortality problems in three models of reversible computation: reversible counter machines, reversible Turing machines and reversible one-dimensional cellular automata. Immortality and periodicity are properties that describe the behavior of the model starting from arbitrary initial configurations: immortality is the property of having at least one non-halting orbit, while periodicity is the property of always eventually returning back to the starting configuration. It turns out that periodicity and immortality problems are both undecidable in all three models. We also show that it is undecidable whether a (not-necessarily reversible) Turing machine with moving tape has a periodic orbit.}, Address = {Berlin, Heidelberg}, Author = {Kari, Jarkko and Ollinger, Nicolas}, BookTitle = {Mathematical Foundations of Computer Science 2008}, Editor = {Ochma{\'{n}}ski, Edward and Tyszkiewicz, Jerzy}, File = {Periodicity and Immortality in Reversible Computing - mfcs - a - r.pdf}, ISBN = {978-3-540-85238-4}, Pages = {419--430}, Publisher = {Springer Berlin Heidelberg}, Title = {Periodicity and Immortality in Reversible Computing}, Year = {2008}, date-added = {2020-12-17 08:05:30 +0100}, date-modified = {2020-12-17 08:05:30 +0100}, doi = {10.1007/978-3-540-85238-4_34} }