{"entities":{"Q1104752":{"pageid":1115501,"ns":120,"title":"Item:Q1104752","lastrevid":66725931,"modified":"2026-04-12T12:26:13Z","type":"item","id":"Q1104752","labels":{"en":{"language":"en","value":"Intractable problems in reversible cellular automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4057014"}},"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":"Q1104752$C12F39BC-C2E9-44DD-9F5D-9AB5611C4536","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"592796168d6207969b0dc891b39f39e0fd26e426","datavalue":{"value":{"text":"Intractable problems in reversible cellular automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104752$6026F1FC-351D-4CA7-9D10-85DDD8BA44B7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"370b7dc3bd731655eaf02f0f446eb1fa7900ada8","datavalue":{"value":"0647.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104752$2149C912-B8A2-4F1A-94EC-C1265878A538","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"00bec49758680c5f4222941e46797e15645fe854","datavalue":{"value":"10.1007/BF00669293","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104752$A8067072-6E12-4607-8386-A3EB917DCB1D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5722f936a01ab1be38fbd038711c5d1914d38f37","datavalue":{"value":{"entity-type":"item","numeric-id":243819,"id":"Q243819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104752$792D4C2C-3902-4D56-BB63-574B21BD8CE3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"82a3be88549eb59571e2dd1afecf617032b59ace","datavalue":{"value":{"entity-type":"item","numeric-id":168494,"id":"Q168494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104752$0B9997A4-81E8-4A01-9925-230AD3700A76","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1104752$8F260194-D420-4C54-890F-2C9208236145","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"feecb3c5b1c803dd6ceb8481d46ce60ab2b78a24","datavalue":{"value":"The billiard ball model, a classical mechanical system in which all parameters are real variables, can perform all digital computations. An eight-state, 11-neighbor reversible cellular automaton (an entirely discrete system in which all parameters are integer variables) can simulate this model. One of the natural problems for this system is to determine the shape of a container so that the initial specific distribution of gas molecules eventually leads to a predetermined distribution. This problem is PSPACE-complete. Related intractable and decidable problems are discussed as well.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104752$A5DC3E39-3861-4545-A03E-F2E9D1A12A32","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104752$8D4A5925-CAFC-4E3D-899D-0DB88FFCE19F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104752$E0AB9DE4-6A60-4123-B5AA-A1B1FE0FCCC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104752$3E8E21FA-54D0-4978-9C23-91DD066225E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a859ab5ac9af0959920513e5dfac470bd12008b","datavalue":{"value":"76N99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104752$250FA0B1-C4AC-4A13-A7C6-33F21A32E19C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"69715f9d545971e6613430e405f85adbf4ee3577","datavalue":{"value":"4057014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104752$28164EF9-55C9-4174-A016-EBA12259CA86","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"45fff9e809959d64baffe9cf84f463ce1c4e52f4","datavalue":{"value":"billiard ball","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104752$A1D32F72-94D7-499F-8BB3-DE14562F9173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1673d1ceb075449d8cb89372af6fc616f50953a","datavalue":{"value":"reversible cellular automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104752$87937398-B31F-4157-8976-DF9836110B56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a3b70c5440e5dc6b56bb9b484bf49d6ed5b0ea7","datavalue":{"value":"distribution of gas molecules","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104752$1C0B1E8D-3B36-4EA6-BE99-C76B2033ACA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a05cfd9da536bc8387292ab9359d3f7e9902a360","datavalue":{"value":"PSPACE-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104752$18B47E97-96AB-4C4C-896A-4D0AF46B38C7","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":"Q1104752$2A1B0600-71EF-415D-9787-D90C72CE7AF7","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":"Q1104752$B9D24BAA-386E-4D7B-A254-882CA0A179F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"728964734428e8655cb87cece2fff202f92850f3","datavalue":{"value":{"entity-type":"item","numeric-id":3944542,"id":"Q3944542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104752$E5E916EB-A140-44C6-9BCD-FE3C6C8A5733","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c1df837fb2036e20c0a1e828ff03c22e6d5eb26","datavalue":{"value":{"entity-type":"item","numeric-id":1226471,"id":"Q1226471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104752$BB6A7BB8-4096-45F3-9EFE-0EDB9BE76350","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":"Q1104752$BB6708BE-796A-4322-B698-374A5201CE38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104752$B81B45B0-E0C0-407F-AC7E-79E6697CDD4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bf5d30377b1d88f6fded624586a0306b8b2d38d","datavalue":{"value":{"entity-type":"item","numeric-id":3629225,"id":"Q3629225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104752$09739C2A-BC2F-487A-90FD-310A6C510568","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":"Q1104752$F5551517-F906-4BBD-A86B-DAC00BB301D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44ad6a5c77511c7234455b9ff4292d79c61acae2","datavalue":{"value":{"entity-type":"item","numeric-id":4077942,"id":"Q4077942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104752$0298F1E3-D0C0-4004-A43F-2639209A9E8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cb51a152c03c8796f14da4e0dec1531580e1039","datavalue":{"value":{"entity-type":"item","numeric-id":2555840,"id":"Q2555840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104752$B004DB66-C86C-4051-9F46-B92FACD24AEC","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":"Q1104752$86A76E02-85B2-4542-BB6D-9E4FB24CA2C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e765defd67c38104ae6ea2d9349d44fca9f333ba","datavalue":{"value":{"entity-type":"item","numeric-id":3886867,"id":"Q3886867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104752$DA7359AF-4043-41E2-B467-96D2AB806043","rank":"normal"}],"P1643":[{"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":"ca9e673f40633afd2dddbae5615c6aaf6b4df547","datavalue":{"value":{"amount":"+0.7867461442947388","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":"Q1104752$3C8D1058-91C9-4662-8944-1F511F3ACF24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e21c6f587f3beb0dafdf8745f5e4e90646ea342","datavalue":{"value":{"entity-type":"item","numeric-id":3793734,"id":"Q3793734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"350416ea441a12c24dd4a045cb646b2f04f7e3df","datavalue":{"value":{"amount":"+0.784400224685669","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":"Q1104752$B360BA24-ACC7-4167-90F7-1A84E985ED0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c66e52f9900a6a3077d3b97cad53e25172075be0","datavalue":{"value":{"entity-type":"item","numeric-id":807043,"id":"Q807043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"962f1ce078b07ad3380e1bdcc01573a4f181e08e","datavalue":{"value":{"amount":"+0.7831296920776367","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":"Q1104752$30BF4464-137A-46EF-A061-F6DC7AB693D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa65175243d754d5f4323896749c2df4aa75424b","datavalue":{"value":{"entity-type":"item","numeric-id":4544346,"id":"Q4544346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa7c1c1c236124df2148145553ca9118284b7870","datavalue":{"value":{"amount":"+0.7700424194335938","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":"Q1104752$4E8D01B4-3D8C-412B-9996-9421FF7FECFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a04224e0624ea1b2fb26fb16632ee3248568f75","datavalue":{"value":{"entity-type":"item","numeric-id":5439069,"id":"Q5439069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa7c1c1c236124df2148145553ca9118284b7870","datavalue":{"value":{"amount":"+0.7700424194335938","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":"Q1104752$72C31513-A409-4855-84D5-07472971D438","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Intractable problems in reversible cellular automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Intractable_problems_in_reversible_cellular_automata"}}}}}