Periodicity and Immortality in Reversible Computing

Preprint English OPEN
Kari , Jarkko; Ollinger , Nicolas;
(2008)
  • Publisher: HAL CCSD
  • Subject: [ INFO.INFO-OH ] Computer Science [cs]/Other [cs.OH] | immortality | [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] | counter machines | undecidability | turing machines | cellular automata
    arxiv: Computer Science::Formal Languages and Automata Theory

Additional material available on the web at http://www.lif.univ-mrs.fr/~nollinge/rec/gnirut/; We investigate the decidability of the periodicity and the immortality problems in three models of reversible computation: reversible counter machines, reversible Turing machin... View more
  • References (11)
    11 references, page 1 of 2

    1. Landauer, R.: Irreversibility and heat generation in the computing process. IBM Journal of Research and Development 5 (1961) 183-191

    2. Lecerf, Y.: Machines de turing r´eversibles. C. R. Acad. Sci. Paris 257 (1963) 2597-2600

    3. Bennett, C.B.: Logical reversibility of computation. IBM Journal of Research and Development 17(6) (1973) 525-532

    4. Minsky, M.: Computation: Finite and Infinite Machines. Prentice Hall, Englewoods Cliffs (1967)

    5. Morita, K.: Universality of a reversible two-counter machine. Theor. Comput. Sci. 168(2) (1996) 303-320

    6. Kari, J.: Theory of cellular automata: a survey. Theor. Comput. Sci. 334 (2005) 3-33

    7. Hooper, P.K.: The undecidability of the turing machine immortality problem. J. Symb. Log. 31(2) (1966) 219-234

    8. Collins, P., van Schuppen. J. H.: Observability of hybrid systems and turing machines. In: 43rd IEEE Conference on Decision and Control. Volume 1., IEEE Press (2004) 7 - 12

    9. K˚urka, P.: On topological dynamics of turing machines. Theor. Comput. Sci. 174(1-2) (1997) 203-216

    10. Blondel, V.D., Cassaigne, J., Nichitiu, C.M.: On the presence of periodic configurations in turing machines and in counter machines. Theor. Comput. Sci. 289(1) (2002) 573-590

  • Metrics
    No metrics available
Share - Bookmark