{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T14:10:54Z","timestamp":1791295854570,"version":"4.1.0"},"reference-count":11,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1992,6]]},"abstract":"<jats:p>The limit set of a celullar automaton consists of all the configurations of the automaton that can appear after arbitrarily long computations. It is known that the limit set is never empty\u2014it contains at least one homogeneous configuration. A CA is called nilpotent if its limit set contains just one configuration. The present work proves that it is algorithmically undecidable whether a given one-dimensional cellular automaton is nilpotent. The proof is based on a generalization of the well-known result about the undecidability of the tiling problem of the plane. The generalization states that the tiling problem remains undecidable even if one considers only so-called NW-deterministic tile sets, that is, tile sets in which the left and upper neighbors of each tile determine the tile uniquely. The nilpotency problem is known to be undecidable for d-dimensional CA for $d \\geq 2$. The result is the basis of the proof of Rice\u2019s theorem for CA limit sets, which states that every nontrivial property of limit sets is undecidable.<\/jats:p>","DOI":"10.1137\/0221036","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:38:23Z","timestamp":1109227103000},"page":"571-586","source":"Crossref","is-referenced-by-count":120,"title":["The Nilpotency Problem of One-Dimensional Cellular Automata"],"prefix":"10.1137","volume":"21","author":[{"given":"Jarkko","family":"Kari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","first-page":"72","volume":"66","author":"Berger Robert","year":"1966","journal-title":"Mem. Amer. Math. Soc. No."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0218057"},{"key":"R3","first-page":"69","volume":"1","author":"Hurd Lyman P.","year":"1987","journal-title":"Complex Systems"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1017\/S0143385700006738"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80025-X"},{"key":"R6","unstructured":"J. Kari,  Rice's theorem for limit sets of cellular automata, to appear"},{"key":"R7","volume-title":"Sequential Machines. Selected Papers","author":"Moore E. E.","year":"1964"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01418780"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107325630"},{"key":"R10","volume-title":"Theory and applications of cellular automata","author":"Wolfram S.","year":"1986"},{"key":"R11","first-page":"133","volume":"31","author":"Podkolzin A. S.","year":"1976","journal-title":"Probl. kibernetiki"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0221036","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:49:18Z","timestamp":1787338158000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0221036"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["10.1137\/0221036"],"URL":"https:\/\/doi.org\/10.1137\/0221036","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}