{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T05:14:18Z","timestamp":1724303658097},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1995,12]]},"abstract":"<jats:p> The issue of testing invertibility of cellular automata has been often discussed. Constructing invertible automata is very useful for simulating invertible dynamical systems, based on local rules. The computation universality of cellular automata has long been positively resolved, and by showing that any cellular automaton could be simulated by an invertible one having a superior dimension, Toffoli proved that invertible cellular automaton of dimension d\u22652 were computation-universal. Morita proved that any invertible Turing Machine could be simulated by a one-dimensional invertible cellular automaton, which proved computation-universality of invertible cellular automata. This article shows how to simulate any Turing Machine by an invertible cellular automaton with no loss of time and gives, as a corollary, an easier proof of this result. <\/jats:p>","DOI":"10.1142\/s0129054195000202","type":"journal-article","created":{"date-parts":[[2004,11,12]],"date-time":"2004-11-12T06:59:25Z","timestamp":1100242765000},"page":"395-402","source":"Crossref","is-referenced-by-count":13,"title":["HOW TO SIMULATE TURING MACHINES BY INVERTIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA"],"prefix":"10.1142","volume":"06","author":[{"given":"JEAN-CHRISTOPHE","family":"DUBACQ","sequence":"first","affiliation":[{"name":"D\u00e9partement de Math\u00e9matiques et d\u2019Informatique, \u00c9cole Normale Sup\u00e9rieure de Lyon, 46, all\u00e9e d\u2019Italie, 69364 Lyon Cedex 07, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054195000202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:31:05Z","timestamp":1565177465000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054195000202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":0,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1995,12]]}},"alternative-id":["10.1142\/S0129054195000202"],"URL":"https:\/\/doi.org\/10.1142\/s0129054195000202","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}