{"entities":{"Q2114796":{"pageid":2125539,"ns":120,"title":"Item:Q2114796","lastrevid":57731052,"modified":"2026-04-01T03:47:19Z","type":"item","id":"Q2114796","labels":{"en":{"language":"en","value":"Universal gates with wires in a row"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7490064"}},"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":"Q2114796$7BAAC11D-3D00-4920-B290-92CF64F76FB1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c23e278fa2d84237fcf7cb3f6f8960f754d8825b","datavalue":{"value":{"text":"Universal gates with wires in a row","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2114796$C5A224F7-7A46-4987-B82B-EBA079D4C0C5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"47a4e39dd54125985e32b98a1a706621ffaad37d","datavalue":{"value":"1494.37011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2114796$D1DA6E9B-1369-4255-A251-AF8C4A626ABC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$4E0292ED-9AF9-44E6-9DEA-5CE57C686EEC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b5e010d4525286f928f56a14a06a3a3ef373d646","datavalue":{"value":{"entity-type":"item","numeric-id":162910,"id":"Q162910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$0D0D0DF7-37C2-4959-BB64-A88A827DCB6D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1470e37d0b940c5d9b54c63ce5027a99aca98db7","datavalue":{"value":{"time":"+2022-03-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2114796$9172822C-1208-46AB-B556-023D3BACE215","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ac81a40c51c85466bc8adacd62331646a196c8b9","datavalue":{"value":"https://arxiv.org/abs/1809.08050","type":"string"},"datatype":"url"},"type":"statement","id":"Q2114796$4EF9C708-3FBE-41D3-8A8E-2A031E8865C2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6a68432a0af4306eb175b7cc4a7d98306ca3d604","datavalue":{"value":"Consider the Cantor set \\(X=\\{0,1\\}^{\\mathbb Z}\\) with elements \\((x_i)_i\\), and the group \\(G\\) acting on \\(X\\) and generated by the shift map \\(\\sigma(x)=(x_{i+1})_i\\) and all homeomorphisms \\(f\\colon X\\to X\\) with \\textit{bounded support} in the sense \\(f(x)_i=x_i\\) whenever \\(|i|>r(f)\\). Such homeomorphisms are called \\textit{invertible gates}, and a set of gates \\(F\\) is \\textit{universal} if \\(G=\\langle F,\\sigma\\rangle\\).  The interpretation as gates is naturally motivated by electronics. For example, \\(s(x)_i=\\{x_{1-i}\\text{ if }i\\in\\{0,1\\},x_i\\text{ else}\\}\\) is the \\textit{swap} of two wires \\(0,1\\), and \\(c^k(x)_i=\\{1-x_0\\text{ if }i=0\\wedge x_1=\\cdots=x_k=1,x_i\\text{ else}\\}\\) is the \\textit{\\(k\\)-th controlled NOT}. A set of gates \\(F\\) is universal precisely when every circuit relying on inputs arranged in a line may be expressed using \\(F\\) and its shifts.  The author proves a collection of impressive results in two directions: firstly, about the group \\(G\\) itself. This is generated by \\(\\{s,c^0,c^2,\\sigma\\}\\), meaning that  \\(\\{s,c^0,c^2\\}\\) is universal; and it is even generated by \\(\\{f,\\sigma\\}\\) for some specific gates \\(f\\) such as ``rule 57'' (\\(e^{57}(x)_0=1-x_0\\) unless \\(x_{-1}=0\\ne x_1\\), and no other input is changed).  Secondly, he shows that these results on infinite groups have consequences for finite circuits with inputs arranged in a cycle. Let \\(G_n\\) denote the alternating group \\(\\operatorname{Alt}(\\{0,1\\}^n)\\); then there is no homomorphism \\(G\\to G_n\\), but nevertheless for every \\(f\\in G\\) there is for all \\(n\\gg0\\) a well-defined corresponding element \\(f_n\\in G_n\\), which is asymptotically an injective homomorphism, mapping \\(\\sigma\\) to the cyclic permutation \\(\\sigma_n\\) of \\(n\\) bits. Said more compactly, the \\((G_n)_n\\), with the partially-defined map \\(f\\mapsto f_n\\), confirms the fact that \\(G\\) is a \\textit{LEF group}: every finite subset may be embedded into a finite group.  Theorem~1 then shows that for \\(F\\) universal we have \\(G_n=\\langle F_n,\\sigma_n\\rangle\\) for all \\(n\\ge n(F)\\). In particular, \\(G_n=\\langle e^{57}_n,\\sigma_n\\rangle\\) for all \\(n\\ge4\\); this solves a conjecture by \\textit{M. Macauley} et al. [J. Algebr. Comb. 33, No. 1, 11--35 (2011; Zbl 1211.37014)] and \\textit{M. Vielhaber} [in: 18th international workshop on cellular automata and discrete complex systems and 3rd international symposium Journ\u00e9es Automates Cellulaires, La Marana, Corsica, September 19--21, 2012. Proceedings. Waterloo: Open Publishing Association (OPA). 166--176 (2012; Zbl 1459.68132)].  The proofs mainly follow from careful and elementary considerations; though in some places they are based on the output of a computer calculation (provided in the appendix).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2114796$24CF3590-BDC0-44FC-8045-17C09E714AFC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"903cde450ed67c23d8b942c8f48fe9eafde5d207","datavalue":{"value":{"entity-type":"item","numeric-id":245335,"id":"Q245335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$452B93C0-CE20-422F-BC0A-1B014F8C3D5C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e9f75a1ea6a1b050032188834d6ec5de5f473dd3","datavalue":{"value":"37B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2114796$B8C8C035-07BF-4FA5-A8C8-3AE6FE20BBB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2114796$D9C88384-8D5B-4C3E-9EC8-AE0EE22AD5D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0c11e1636e28bd1a59d5342c1523bca4bf56a601","datavalue":{"value":"68Q06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2114796$C169887F-A4ED-4B7C-8A8A-1C888E06914D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7af17f227fda8daecc6b4cd26e5d774fa965085f","datavalue":{"value":"81P68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2114796$53004F3C-964B-479F-86DD-B4920AF8865A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"602d7e96b613d2f356db81712453cadad0417631","datavalue":{"value":"08A40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2114796$D0D45FCC-3D76-42C9-9BC6-621873DB1E81","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"80ccfcc2c5428448667647e84bc2a591711dc41e","datavalue":{"value":"7490064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2114796$65404437-57CD-4476-BFC0-09EBAEE3E4EF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0c1e837c94ed348203cf4e5ba4b4374db893e72","datavalue":{"value":"reversible gates","type":"string"},"datatype":"string"},"type":"statement","id":"Q2114796$AA5536C4-2CFD-402C-B61B-BA5B41FD8FF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59b8ad8d5c31bd121e840ef336ff3767b50a9361","datavalue":{"value":"LEF groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q2114796$32E465EA-693B-412D-AB71-FFC539C1CD2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5479a2c9b5c7bdf5ffc6cad72ceb5bf6947a5449","datavalue":{"value":"rule 57","type":"string"},"datatype":"string"},"type":"statement","id":"Q2114796$DBB1E211-D646-4C90-BFE6-00B6CBF67663","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":"Q2114796$E6C796B9-3FD8-43F7-B6FB-1B5B3A282AF6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ded7dfcfb8fe0093d9b97cab03dbc02ead7d2864","datavalue":{"value":"W3204048216","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2114796$F9C1F067-0A74-43AF-84B3-1C4459D2486D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b84d571d3c112e4b33b71ca899d98fd64089c45b","datavalue":{"value":{"entity-type":"item","numeric-id":4638073,"id":"Q4638073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$850CBDB2-BCD7-4696-BD5E-BEE231D4CA8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b7fc2a0909e00d54e25556254cd76eda66f9fca","datavalue":{"value":{"entity-type":"item","numeric-id":3186472,"id":"Q3186472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$451AC4CF-0EC1-41C6-8A37-B658190EDDBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"816a2b6e14f42afa2c7c83df22754d432369cbc4","datavalue":{"value":{"entity-type":"item","numeric-id":5212300,"id":"Q5212300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$46112CDD-C856-4EFF-A000-E9C7C2F8B8B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b46f18d82c3583b2fde6a3ac977bc5ca5aee2bd","datavalue":{"value":{"entity-type":"item","numeric-id":3186604,"id":"Q3186604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$24F93270-7F7B-4FED-BF60-BA0267A1832A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4363adb8fe36d099e1faf3d99505e099a03ceb4d","datavalue":{"value":{"entity-type":"item","numeric-id":3583434,"id":"Q3583434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$373ED4E8-A257-4120-9DAE-BC63E9A0B27B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f12a5c539fe0cea13c45e5b9d2a225e323cb3b01","datavalue":{"value":{"entity-type":"item","numeric-id":3974526,"id":"Q3974526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$03AEF1A8-71C7-4A8F-BA93-1B556A3C0A90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e77b96e5be8eb5e64d04ecd963c90577f4f1ca","datavalue":{"value":{"entity-type":"item","numeric-id":617317,"id":"Q617317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$5DED929E-D166-4236-B21B-18E5BD36ACCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c04ecdad8aab598efa9dd54cd22803737ffdbcc","datavalue":{"value":{"entity-type":"item","numeric-id":3646415,"id":"Q3646415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$B5B18185-7DBD-40FC-853F-0C4B47666FDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c72c7ddcffb0ec4f5c45b6adda4a5a394cf6d25","datavalue":{"value":{"entity-type":"item","numeric-id":4986314,"id":"Q4986314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$7C3DF0E3-2B04-4A50-92CA-93EA5C1BC543","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f253e8d1647a719f4cd686675c398f8b0fa269e2","datavalue":{"value":{"entity-type":"item","numeric-id":1410965,"id":"Q1410965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$92556E8E-B546-4A8A-A372-A9F78FAC8A37","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e2b4943323824261c4278343b5cd03a3084b60e8","datavalue":{"value":"10.1007/S10801-021-01053-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2114796$1B21F8BC-BEA2-4481-84CD-ACF3983F0CF9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75db9e683aa19cebab668f55610d9583a999a67b","datavalue":{"value":{"entity-type":"item","numeric-id":1682853,"id":"Q1682853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4123383e831d2d8faa37ef76948c05562b9f3751","datavalue":{"value":{"amount":"+0.7381333112716675","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":"Q2114796$AF9EBAF5-ADA1-462A-A9F8-800117364944","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48bdbb60239a41aec5219889f576ec746677c537","datavalue":{"value":{"entity-type":"item","numeric-id":3186604,"id":"Q3186604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0fdea14d3c34e3a9238117d05af4b5df67c5f643","datavalue":{"value":{"amount":"+0.7347425818443298","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":"Q2114796$F7E6255C-296B-494F-9165-561CB79E397B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a68f2fd0cb892b347e35c99f4ee16afdb7e7e08","datavalue":{"value":{"entity-type":"item","numeric-id":5090173,"id":"Q5090173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbdf1aff5410fc34cec6d5019d0807e8a7036f0e","datavalue":{"value":{"amount":"+0.721466600894928","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":"Q2114796$20513DA0-0822-4DF7-8696-33BC09AEC418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63dd4838705789ad7333a8cedef4ba8d205d16d6","datavalue":{"value":{"entity-type":"item","numeric-id":4638073,"id":"Q4638073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"417a16b79d431daa74a35de67bee9e0bd3a05580","datavalue":{"value":{"amount":"+0.6940045356750488","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":"Q2114796$E04EB87F-E14C-4C69-9B74-322D10E8C231","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d53729cf7ed97f8320ede08c88c1b6a0206c49bc","datavalue":{"value":{"entity-type":"item","numeric-id":418784,"id":"Q418784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f6d77c09180a3079dd87e25996c0ba646f65a40","datavalue":{"value":{"amount":"+0.6904647350311279","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":"Q2114796$6F101D81-70CD-47D7-92B2-8912DB11CB7A","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2114796$A2C1E687-DB45-48AB-AE91-D5327397D775","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2114796","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2114796"}}}}}