{"entities":{"Q2201790":{"pageid":2212533,"ns":120,"title":"Item:Q2201790","lastrevid":57775671,"modified":"2026-04-02T11:49:54Z","type":"item","id":"Q2201790","labels":{"en":{"language":"en","value":"On the conjugacy problem of cellular automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7248650"}},"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":"Q2201790$A78A1107-C2AC-4930-9F00-4A9CF2DE54FD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3c951cbc0a93d43bb72e9237547a63573ede40aa","datavalue":{"value":{"text":"On the conjugacy problem of cellular automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2201790$C3BC3D86-22B8-4F7F-99BC-2097C0518E2F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9e6300d07ebe802d4e964861f97f2792841a5a49","datavalue":{"value":"1459.37013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2201790$B1E3781E-BF17-4A17-9B36-E6FAFD69FD77","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec05c44c183292612aec723b071e60a3e130ddd2","datavalue":{"value":{"entity-type":"item","numeric-id":1656686,"id":"Q1656686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$28980465-C79A-46C4-8D82-AEEB4FF65681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ff7efbe0112319e24c5eb2c5dfdf398d54a454e6","datavalue":{"value":{"entity-type":"item","numeric-id":309660,"id":"Q309660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$928361AF-1ACF-4D72-B92C-79B8DB4C3656","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$B95197AB-708A-43D3-ACB4-99349F75B7E6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c7b654844b81166f884849fbb386fac59a7d85c1","datavalue":{"value":{"time":"+2020-09-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2201790$DC6B8C1A-D10C-45EE-A79F-80A290005FC8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a0cbfafd597cc35ca5551185e38cebb22362d3d0","datavalue":{"value":"https://arxiv.org/abs/1906.00796","type":"string"},"datatype":"url"},"type":"statement","id":"Q2201790$1FA4E895-6F25-4797-8854-AE257B33A9F1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c985527eea86ba298656726224fd8eee27cc3904","datavalue":{"value":"It is well known that a natural notion of isomorphism in topological dynamics is topological conjugacy. Let \\(f : A ^{\\mathbb{Z}}\\rightarrow A^{\\mathbb{Z}}\\) be a one-dimensional cellular automaton. In [Topological conjugacies between cellular automata. Dresden: Fakult\u00e4t Mathematik und Naturwissenschaften der Technischen Universit\u00e4t (PhD Thesis, 2017)], \\textit{J. Epperlein} proved that if \\(T_1 , \\dots, T_n\\) are tori, there are cellular automata \\(g,h : A ^{\\mathbb{Z}}\\rightarrow A^{\\mathbb{Z}}\\) such that \\(g\\) is surjective while \\(h\\) is not surjective and such that \\(f_{T_k} , g_{T_k}\\) and \\(h_{T_k}\\) are pairwise conjugate for all \\(k \\in \\{1, \\dots , n\\}\\).   In this paper, the authors investigate the conjugacy problem of two-dimensional cellular automata, i.e., the problem of deciding whether two cellular automata are conjugate or not. Firstly they prove the following result:   Theorem. The following two sets of pairs of one-dimensional one-sided cellular automata are recursively inseparable:   (i) pairs where the first cellular automaton has entropy strictly higher  than the second one, and   (ii) pairs that are strongly conjugate and both have zero topological entropy.  Taking into account the above theorem, the authors present the same inseparability result for reversible two-dimensional two-sided cellular automata. They prove the following result:   Theorem. The following two sets of pairs of reversible two-dimensional cellular automata are recursively inseparable:   (i) pairs where the first cellular automaton has entropy strictly higher  than the second one, and   (ii) pairs that are strongly conjugate and both have zero entropy.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2201790$C9C09206-FC5B-487E-B9AA-2F1D78CBDBAE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d1b9364d9e6fda7e34b22c9ee86f645a14aee9b1","datavalue":{"value":{"entity-type":"item","numeric-id":548132,"id":"Q548132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$179EBD16-BC26-462E-AB1F-A70753C5116B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e9f75a1ea6a1b050032188834d6ec5de5f473dd3","datavalue":{"value":"37B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2201790$940EF89A-5E3B-43D9-99B7-4A8F14060CDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0e33651934d3b1e59a1a7d4fe8982881bc51718e","datavalue":{"value":"37C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2201790$BAA54911-220D-4728-8FF6-C7851F9751A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2201790$139606A6-7BD2-4BC8-8793-2DBD5E8EFDA1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7a9c7657a5b99336eefe6d46645b9d2da51fd5ff","datavalue":{"value":"7248650","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2201790$02F6FD66-6114-43CB-AA40-F2519795B657","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc4b5d63289db850b148e760ad6fea530c4e5631","datavalue":{"value":"cellular automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q2201790$9FE8856D-AF62-4C36-883E-80692C5F7F75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fccb19bde191b3d4cb60ffaaf1d6345fcbcda2e4","datavalue":{"value":"conjugacy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2201790$A1543922-258D-4A28-A46D-D2C026EA04D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a813fd0e4aef1fda5e8e7d4b77b02104337d96e6","datavalue":{"value":"undecidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2201790$0BA69F53-94A2-4F07-99AC-54A0CB6F30BD","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":"Q2201790$CC3C0369-45D2-464A-8583-C85D0A10F35F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"63a3a7142c1ff9d635a1ef4865df4c4dcfc8da9c","datavalue":{"value":"W2947207802","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2201790$092F6A61-843E-46C4-AC60-F38B5A76E348","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce37008f02992dffed4d982ed3d60d7a06d51e8c","datavalue":{"value":{"entity-type":"item","numeric-id":5426860,"id":"Q5426860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$514BB82D-B117-4B9C-86B1-6A7D7EA177FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25d601597348c4eaeef99976dca28fd049a4918b","datavalue":{"value":{"entity-type":"item","numeric-id":5572921,"id":"Q5572921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$E32F3FA4-CCB2-44E3-B2DA-4A22A2668188","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03c45906f075d58855a2376ea03d0c4ba062c00e","datavalue":{"value":{"entity-type":"item","numeric-id":4016914,"id":"Q4016914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$41492675-3106-4833-AD98-082CDD8CA022","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2deba89bc6cbf176b95792137b080c001d119ae0","datavalue":{"value":{"entity-type":"item","numeric-id":1318474,"id":"Q1318474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$E722485E-F2B5-4A1D-9E7C-87CA81D0C42E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e5b595c763bf3f57e788fcf38906e5f0650ba05","datavalue":{"value":{"entity-type":"item","numeric-id":5127182,"id":"Q5127182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$1D7343A9-FB14-48E1-9C55-46B4A320E03D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43b35b7817e69a8ebee98802f8358e46c1bc969a","datavalue":{"value":{"entity-type":"item","numeric-id":698668,"id":"Q698668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$64697E75-6D1A-420F-9EEA-30FF3A275F57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea132d317dcdbef3507645010bd4498eaf6044d2","datavalue":{"value":{"entity-type":"item","numeric-id":4337811,"id":"Q4337811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$4E01AC19-5FA8-4003-BDC0-207F1C093B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cafc014c2215535df068957c9b0115c621289a9f","datavalue":{"value":{"entity-type":"item","numeric-id":4449875,"id":"Q4449875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$8C333203-B03A-43E2-BD7E-C7F8E9E605DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b20f44006eae2a28bfd692ba79724f2382a59f3f","datavalue":{"value":{"entity-type":"item","numeric-id":4055979,"id":"Q4055979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$21A32FDA-6376-4C1C-A1B1-7138ED0A99C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"346aa670fc2ad105bcc1e656f336502f7eab8b29","datavalue":{"value":{"entity-type":"item","numeric-id":3528760,"id":"Q3528760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$CA97681A-0E01-49D4-8310-BA0DFA493A1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50be72f655cf4b2d0274d4ad826a3434424e5b4c","datavalue":{"value":{"entity-type":"item","numeric-id":4698566,"id":"Q4698566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$4D51D7B2-3438-4F8E-95AF-9BDEDE001A02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d0501d3269e3b56e7eaa218c1b97664ba523e6c","datavalue":{"value":{"entity-type":"item","numeric-id":2011658,"id":"Q2011658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$33177E12-1B85-42D2-AA53-A8812E148EDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4043fc07bff8a9d09a0cee0edfeeead8800ddd3","datavalue":{"value":{"entity-type":"item","numeric-id":3599146,"id":"Q3599146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$91E614A6-09A8-4DC7-A943-1826788EB5CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c8bd749eeac0eb56237120f2b29267c861f04d8","datavalue":{"value":{"entity-type":"item","numeric-id":2561573,"id":"Q2561573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$5AC5B249-F12D-421C-BF31-DE1AB7968FCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cc62eac6bb7107c4dd54cbb1c917602eef6c2ff","datavalue":{"value":{"entity-type":"item","numeric-id":1401422,"id":"Q1401422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$8F9409B2-047F-4646-A914-96576FCF75BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77cc76425a8f97433fd86644509281ac1e170d2e","datavalue":{"value":{"entity-type":"item","numeric-id":4451022,"id":"Q4451022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$510BF19C-896E-452D-9D27-845841C0ED64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58402d78396d9437e2e121c4cfedb756a20148f8","datavalue":{"value":{"entity-type":"item","numeric-id":385957,"id":"Q385957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$C483EC1A-C2CB-49D3-818E-DDE11821EEDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"003961228078b0c11edfaf7a8dc0ec4da8ff739f","datavalue":{"value":{"entity-type":"item","numeric-id":1844005,"id":"Q1844005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$701385D5-578C-4B16-8035-FD167517824F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a1f13456cf4790d4237cd758f113cf94047c4e7","datavalue":{"value":{"entity-type":"item","numeric-id":3033336,"id":"Q3033336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2201790$8256B5F4-0BE8-4F0B-8804-8ED7B833FD46","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9a2d7f66322759040d56abf382cb3c839cb9c268","datavalue":{"value":"10.1016/J.IC.2020.104531","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2201790$8350B7CE-474A-4B0D-82AD-0FEFEE8A2B3F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d6603be10b5fda199d9f22ff209208854b9dc9a","datavalue":{"value":{"entity-type":"item","numeric-id":5127182,"id":"Q5127182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e41a4529e8da2b4c6da82d62fea8994eb638df9","datavalue":{"value":{"amount":"+0.909574806690216","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2201790$492FA073-A12F-4EF7-BAE8-B18968D4972E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef68ecf58141220bde59ebbb4084dd43dd3d8615","datavalue":{"value":{"entity-type":"item","numeric-id":1318474,"id":"Q1318474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f09d42aea897eb7076ebcc4dfe4a9cd93e4b7ae4","datavalue":{"value":{"amount":"+0.8024634122848511","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2201790$71BE2403-5B12-46B9-AF1C-9A857A0ACFBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f9afa1c2a91452f98ccb6f20fb0475c16af9a9b","datavalue":{"value":{"entity-type":"item","numeric-id":5446402,"id":"Q5446402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c7c1901baf4217a29fbd4be618492fc742b69a5","datavalue":{"value":{"amount":"+0.8009963631629944","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2201790$15ABF3D7-C5D2-4AA0-8EFD-71467FD18B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"601d966ad21aa18207cf694169340b05ae421025","datavalue":{"value":{"entity-type":"item","numeric-id":5500616,"id":"Q5500616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e42b2ceb25c407e6634da1824416ba373846c01","datavalue":{"value":{"amount":"+0.7873131036758423","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2201790$D84F361D-C3E4-4EF8-9542-775062BC3C6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"102465b48cc1fdb17ac140ac904f5ddf092e5458","datavalue":{"value":{"entity-type":"item","numeric-id":537911,"id":"Q537911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6a12a1ce4917a22806bfb46b55ae45be464b102","datavalue":{"value":{"amount":"+0.7796482443809509","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2201790$0F8C7ACD-4353-4B41-9174-BBEB10A71872","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2201790","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2201790"}}}}}