{"entities":{"Q1198089":{"pageid":1208838,"ns":120,"title":"Item:Q1198089","lastrevid":66851475,"modified":"2026-04-12T13:16:58Z","type":"item","id":"Q1198089","labels":{"en":{"language":"en","value":"Computation-universality of one-dimensional one-way reversible cellular automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 92139"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198089$1D51F9B7-DF9A-44D4-8894-EAAAD9523598","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2550a10a12cfe815a517903efd14483c03cda484","datavalue":{"value":{"text":"Computation-universality of one-dimensional one-way reversible cellular automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198089$51DCD945-0F29-4A07-92A2-74088702B49E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aa0d10c514c101c3f5b871a7d008262093e0e8f6","datavalue":{"value":"0779.68064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198089$9A65381B-9C08-4C8B-9A20-AC150FF23EA4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"295eccbd29249cfde58ad5ac143a939ec5222593","datavalue":{"value":"10.1016/0020-0190(92)90231-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198089$83C99CCD-CAE0-4397-808C-42B5F5C6AFEA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"182d2a53e16892f59ea178d1cc15214afb3283bc","datavalue":{"value":{"entity-type":"item","numeric-id":235713,"id":"Q235713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198089$DAFFDDCD-56A0-4657-8812-F094E46F923B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198089$F379083B-33C4-418B-B768-46EE761D37AF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198089$5EFC501F-5F10-44C3-934C-37D936A167AE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"84add4263fd8ac7db9fd12b6d1d806427ec23f90","datavalue":{"value":"A reversible (or injective) cellular automaton (RCA) is a ``backward deterministic'' CA, i.e., every configuration of it has at most one predecessor. In the one-dimensional case, it has been shown by \\textit{K. Morita} and \\textit{M. Harao} [Computation universality of one-dimensional reversible (injective) cellular automata, Trans IEICE Japan, 758-762 (1989)] that a three-neighbor RCA is computation-universal. In this paper, we investigate the computing ability of a one-dimensional two- neighbor (i.e., one-way) RCA. We first investigate a one-dimensional partitioned cellular automaton (PCA), a special subclass of a CA, and show that three neighbor-RPCA can be simulated by a two-neighbor RPCA. From this and the previous result that three-neighbor RPCA can simulate a universal Turing machine [Morita and Harao, loc. cit.], computation- universality of a two-neighbor RPCA and a two-neighbor RCA is derived.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198089$B058CC50-71A9-41DB-A204-CEA12DC01B8F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198089$794A2E4D-3795-4395-B6BA-898EC8F0B03C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198089$9817B604-31CF-41EB-83C3-325610B37C89","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"771a4bdfb16bbd9ef2549f8bc2fcd3da25ee5ccf","datavalue":{"value":"92139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198089$845B360B-635F-43F3-8A36-938A14797061","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"888011ba599a37fb0e9f8f56995815877721cb43","datavalue":{"value":"reversible cellular automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198089$93F45AF7-DEA6-4F73-B2E5-619DEF7EE079","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f8c4295302f5494dc6707c1d8ab9a1dc39208c3","datavalue":{"value":"partitioned cellcular automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198089$755B2DA7-B927-4F3D-9C9A-38356DB9F3DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"681e2bbdd86bcac9c255454bb469fe88abba43dd","datavalue":{"value":"three neighbor-RPCA","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198089$CE9B89DE-62C9-4BDB-AF18-1338588C5C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92aeb73e4fdd63eb4a6f5fe3583aae19257ec92e","datavalue":{"value":"computation-universality","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198089$A99DB419-49D2-41DD-BF82-D53722560603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f2df51b3ebb52617a573feba2209156b4520397","datavalue":{"value":"two-neighbor RCA","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198089$3B014092-C081-4169-9E55-02AED02B783E","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198089$F9BCAF66-A0BD-49CF-B660-1B94110B33C5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1366bd2322a8359118d05135af2e7062ee0ec3e","datavalue":{"value":{"entity-type":"item","numeric-id":5684240,"id":"Q5684240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198089$51504E77-3AF1-4DD6-B3B2-2629E1BD95C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6754391c9dc579f404772022aba1e12d6e49f6a","datavalue":{"value":{"entity-type":"item","numeric-id":1170163,"id":"Q1170163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198089$8C96FE14-5B1F-41A0-A01F-64A8335E14CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"571698bad3a63c2bacc95c86c8c0a7a0a28aced4","datavalue":{"value":{"entity-type":"item","numeric-id":3677179,"id":"Q3677179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198089$A4849F16-D398-4301-A05D-FD817DA08973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3be98c9771b642e657b2f29f2ed44379d0d37d7d","datavalue":{"value":{"entity-type":"item","numeric-id":1241491,"id":"Q1241491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198089$892EE7F3-F99C-486A-8EA4-8F2405DBD65E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"babcbf921e4c2d42e3fd963bf69177335f7ec099","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90231-j","type":"string"},"datatype":"url"},"type":"statement","id":"Q1198089$BBE02399-B9DC-479A-AD39-08CC817A0044","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6a81c8333ab0829ae9a0f124e1e7ee8d0ccc3a39","datavalue":{"value":"W2018470239","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198089$91F9AF72-F610-4A97-9E5E-2D6879646BED","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f8cee3cac62f4322e24fbed4e005ae23bd17232","datavalue":{"value":{"entity-type":"item","numeric-id":4986312,"id":"Q4986312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3d30070cfc309d7c93a160b3da592305751bc22","datavalue":{"value":{"amount":"+0.9423282","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198089$34AD5B4B-5DFF-4917-A2B8-F349947B688A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"442cd98a7e3fefcf7ec0ae9da2b87226ead72b3a","datavalue":{"value":{"entity-type":"item","numeric-id":5446408,"id":"Q5446408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d2344782f2b25ad609ffd9cbacb71d7cb777932","datavalue":{"value":{"amount":"+0.9372073","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198089$18D26D39-C529-4081-9499-452F17A46AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93fd6c2a32d7d078a13527e88db91a5be65cdfa2","datavalue":{"value":{"entity-type":"item","numeric-id":5048944,"id":"Q5048944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"055d1df6dd18d4c48cffe0519960644d3021621b","datavalue":{"value":{"amount":"+0.93511224","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198089$AFD655C3-10A3-44AB-B42D-B1B77D9D7ED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b1bd7dd36f4f80a670ddfb754b3a831f3ab9ae9","datavalue":{"value":{"entity-type":"item","numeric-id":3212314,"id":"Q3212314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93a65e4856385d01277cd4493be0920505d0ca64","datavalue":{"value":{"amount":"+0.93312085","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198089$D36E9B99-5576-48A1-A892-79BF7AFC90F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"146cafced7b5fc1848de4f9936fc758dff73709f","datavalue":{"value":{"entity-type":"item","numeric-id":4931277,"id":"Q4931277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5658f666c6b67376d5611820736b3d33e4cec32d","datavalue":{"value":{"amount":"+0.9303849","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198089$0CC00BAE-998E-4941-A88D-A09E432A8852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bf79067e9f1d7276c577cfcc1eb3461ca9f7074","datavalue":{"value":{"entity-type":"item","numeric-id":3186479,"id":"Q3186479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afb5612f290139a4797261de29bc9f97c789cfee","datavalue":{"value":{"amount":"+0.9293202","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198089$F7A017F6-C39F-4396-85CC-C47CAB511BC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48cd3cd16567db8dd57d7cc266f2ebc4751e6cce","datavalue":{"value":{"entity-type":"item","numeric-id":1181328,"id":"Q1181328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"431f1503474b82e1fcf55a48715b36f0f5ede89b","datavalue":{"value":{"amount":"+0.9283994","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198089$C30E6C1C-8C9F-4F23-B7FA-1A46383A2194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a4f357185298549966c3a87bebdc84978df19d2","datavalue":{"value":{"entity-type":"item","numeric-id":672388,"id":"Q672388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35c5c8bb8a4dc175f42b1cf762b5c600291fa9a8","datavalue":{"value":{"amount":"+0.923616","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198089$0956F1D3-B2BF-4032-B8BF-4F94660F924A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d466f30c611a73920529a16fbe943431c8d56a2","datavalue":{"value":{"entity-type":"item","numeric-id":2869782,"id":"Q2869782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06d1b17fa608ef2fd6b12312bbe96747c2953860","datavalue":{"value":{"amount":"+0.91975653","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198089$657FE684-EC6C-4946-BDAF-1F1DDC0CF619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9e1b94ca527e23f1bc57462fa84fc1132e5942a","datavalue":{"value":{"entity-type":"item","numeric-id":1775091,"id":"Q1775091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c61474fa6ab1a7e8cb360f9f235235ffe4b77ab","datavalue":{"value":{"amount":"+0.9146405","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198089$8ED74806-8B9A-46EB-970F-D84C314AB7D1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computation-universality of one-dimensional one-way reversible cellular automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computation-universality_of_one-dimensional_one-way_reversible_cellular_automata"}}}}}