{"entities":{"Q1736474":{"pageid":1747215,"ns":120,"title":"Item:Q1736474","lastrevid":56688261,"modified":"2026-03-18T20:42:50Z","type":"item","id":"Q1736474","labels":{"en":{"language":"en","value":"Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042094"}},"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":"Q1736474$28CB8B17-2496-4BD9-8C70-EEC8B2A08D5E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"60f6aac79fbafd613b5fd1f37a5884e092a834e9","datavalue":{"value":{"text":"Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736474$C035534C-2993-45B6-86B8-B078E5A10B57","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f7a3759ab1ea9df01c5df6a3c8f912b6cba22223","datavalue":{"value":"1461.68126","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736474$4792F0E0-CE99-41B2-9191-E93FD2952109","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"62c8eeddb49a70aa9a0d020d61613d278c307b25","datavalue":{"value":{"entity-type":"item","numeric-id":671371,"id":"Q671371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736474$1952276C-CCBD-4CF1-A4BA-562FB59AD421","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a2c4c7ae1f50bfe7f1bca836289deac895d73aee","datavalue":{"value":{"entity-type":"item","numeric-id":1736473,"id":"Q1736473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736474$2E0AA154-CB1C-4E20-859F-3897C7B5C15B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736474$9CD8D03E-76CC-4E0F-8069-881CB071A60D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736474$1B2B7875-2D96-4008-A014-A6D064E825FE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f43b5a8cbcf38857e1d1f50e97a1fe971f59727c","datavalue":{"value":"Summary: Chris Langton proposed a model of an artificial life that he named ``ant'': an agent -- called ant -- that is over a square of a grid moves by turning to the left (or right) accordingly to black (or white) color of the square where it is heading, and the square then reverses its color. Bunimovich and Troubetzkoy proved that an ant's trajectory is always unbounded, or equivalently, there exists no repeatable configuration of the ant's system. On the other hand, by introducing a new type of color where the ant goes straight ahead and the color never changes, repeatable configurations are known to exist. In this paper, we prove that determining whether a given finite configuration of generalized Langton's ant is repeatable or not is PSPACE-hard. We also prove the PSPACE-hardness of the ant's problem on a hexagonal grid.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736474$E6669712-8967-49D1-8242-16197818B304","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736474$303B2944-9215-4930-A7C7-A6D67A6679CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e9f75a1ea6a1b050032188834d6ec5de5f473dd3","datavalue":{"value":"37B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736474$02AE8900-267F-4C67-80B9-7730593508DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736474$E6836FC3-86E6-469B-BBA5-FCA035185634","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"883be7bbcf0db67ed489b650396903b5497f8e37","datavalue":{"value":"7042094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736474$904AA70E-48F2-4E98-8AA7-96876986D3F3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc4b5d63289db850b148e760ad6fea530c4e5631","datavalue":{"value":"cellular automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736474$E9FB6DE4-67C3-4BEB-887E-9AC0E637D08E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736474$F6EFDFDF-BF9C-40FA-BF2A-3C0BF1ED6F4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa7b591f5da6e817b259c5c2168ff2047d5bb2d2","datavalue":{"value":"Langton's ant","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736474$64F763AA-7E95-4D29-BE17-1153E3E8CF43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64ac598c55b6a19263b4ab43e0b8e876b1cbc8a6","datavalue":{"value":"Lorentz lattice gas","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736474$2D563B35-4439-4D7A-8607-7294670879FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16284ece4670b3d7275c2ce344fa55e4a47741a5","datavalue":{"value":"PSPACE-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736474$9C8D583E-F5FE-4D09-AC6E-BFA9A5924DDD","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":"Q1736474$45A0BCF7-C23B-435C-9BE4-3A6006FC83F9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f6bc220cb54f0191357b06b1ed782a206fa21bab","datavalue":{"value":"https://doi.org/10.3390/a4010001","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736474$359CF45F-DC7E-44ED-A797-D8E4EB8F37EA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cc004a26122846dcb62e2f57c2a09376dcc2d47c","datavalue":{"value":"W2154560238","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736474$494F277B-B533-4748-84AB-43757A1AE6C4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f61ade9d794ea27f7e1da77c8da4e9a52a95705","datavalue":{"value":{"entity-type":"item","numeric-id":4398784,"id":"Q4398784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736474$A0D9B52B-145D-43E2-80E4-0E1D932776E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60a76276f7e94158a362f249d67f7aae7f482769","datavalue":{"value":{"entity-type":"item","numeric-id":3137260,"id":"Q3137260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736474$E62E363B-BE19-4365-9BB5-CD8C2510C1D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1a096a3334a7925e16e1a552a815ff48976e922","datavalue":{"value":{"entity-type":"item","numeric-id":1203252,"id":"Q1203252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736474$36B904A5-CEEA-4A0D-959B-9C7A176A8EBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60da812b6a07b3280f9868889a88d48d442172af","datavalue":{"value":{"entity-type":"item","numeric-id":2500094,"id":"Q2500094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736474$354319B6-3BAD-4E36-B893-B2C0414264F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c8cd7ef235966ae141a5a149ad8693a1d54198b","datavalue":{"value":{"entity-type":"item","numeric-id":1292122,"id":"Q1292122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736474$6A8E8B50-5A1A-473A-83B3-C68111E92488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f184a5f135583b6b43356e0b9dc8781bdb439e7","datavalue":{"value":{"entity-type":"item","numeric-id":1348376,"id":"Q1348376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736474$FDEBC972-D299-4ECA-B211-D903FBE083B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736474$6567CC10-9C04-4078-AB6D-A243E510598C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"84fb1a34b3368cf105e44edfea5b7e8d1ddb077c","datavalue":{"value":"10.3390/A4010001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736474$263F8CA5-7B09-405D-9822-C66018E15C63","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa289e388ffc0d5c41c6b3525720ecb1d0a646f0","datavalue":{"value":{"entity-type":"item","numeric-id":1348376,"id":"Q1348376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e52e34a2bc8076861159e2c3e9d3c73ebf82112","datavalue":{"value":{"amount":"+0.7966316938400269","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":"Q1736474$C56BF8C3-D83F-4C7B-BC55-5670AC8D4289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c45ccb9f9c63eaa85599093a2f36618d519133b0","datavalue":{"value":{"entity-type":"item","numeric-id":2762789,"id":"Q2762789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db1a2e16b42cb4a626520d424503d08e86c21d79","datavalue":{"value":{"amount":"+0.7525917291641235","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":"Q1736474$4A7500A1-77FF-4DE9-B5B0-DFF6B5E7D793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"848a8f2b9fe599ef00d110cc4e0f9c4936bee993","datavalue":{"value":{"entity-type":"item","numeric-id":3531257,"id":"Q3531257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"780e7832adfc6f5cb323f5a56f44262d58e66e5d","datavalue":{"value":{"amount":"+0.7110008597373962","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":"Q1736474$19D504A2-B6B8-44E2-8151-EBCFDAB34A2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe92d26db1e006236e0d9b49a47da504d6ccab0f","datavalue":{"value":{"entity-type":"item","numeric-id":5010155,"id":"Q5010155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b818f4fc081ade5ad91ac103a03aecd1845d67f7","datavalue":{"value":{"amount":"+0.7066705822944641","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":"Q1736474$8C6B5672-1BDA-4F0E-B6B3-A91704ED2DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"337a21b88223cfbec782010cf4e0267cb256be45","datavalue":{"value":{"entity-type":"item","numeric-id":1104752,"id":"Q1104752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71c4c029d03baddb05b655ffeee4df4beda2217d","datavalue":{"value":{"amount":"+0.6866477727890015","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":"Q1736474$8CABD08C-4DD6-4544-80D4-C36C39EA8731","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":"Q1736474$68ACF687-6BB4-4495-94D6-94DEEE309B52","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736474","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736474"}}}}}