{"entities":{"Q792093":{"pageid":793941,"ns":120,"title":"Item:Q792093","lastrevid":64372968,"modified":"2026-04-11T19:25:19Z","type":"item","id":"Q792093","labels":{"en":{"language":"en","value":"On heads versus tapes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3852436"}},"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":"Q792093$A60FE2C2-7335-4B18-B988-83C3BB55C328","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"718decb8169b8c7ca2620763f800c8ca0febaae2","datavalue":{"value":{"text":"On heads versus tapes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q792093$07F7ADE3-9564-4846-A7E9-444F41CDDD62","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e2d114be2af964d1684658fc3c37076ebd71d2d3","datavalue":{"value":"0536.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792093$3FF30EA0-3A02-4342-A14C-345F01CE06C0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6ed7ff78c4647db03181d162200008eff86e4a7","datavalue":{"value":"10.1016/0304-3975(83)90063-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792093$CE2F44EC-07C3-473C-9D9A-43311DC5881B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792093$0C1B7E4C-A529-4750-9A99-C84DFE53ACDD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q792093$9749B8D6-37B8-4AB3-AE81-DDEA394F5948","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"10f94ca009045fdfb5c3e7180c8106527be60136","datavalue":{"value":"The author proves the following theorem: For all k and \\(d\\geq 2\\), d- dimensional k-tape Turing machines (with any number of additional linear tapes) cannot simulate in real time Turing machines with k heads on one d-dimensional tape. For \\(k=2\\) the theorem cannot be improved. For the proof the author develops a theory of descriptional complexity of rectangular figures, using such tools as Kolmogorov complexity, and Chaitin randomness. Part of the theory is implicit in the article by \\textit{W. J. Paul, J. I. Seiferas} and \\textit{J. Simon} [Proc. 12th ACM Symp. Theory of Computing, 357-367 (1980)]. The author also compares his theorem with known simulation results due to \\textit{P. C. Fischer, A. R. Meyer} and \\textit{A. L. Rosenberg} [J. Assoc. Comput. Mach. 19, 590-607 (1972; Zbl 0261.68027)], \\textit{B. L. Leong} and \\textit{J. I. Seiferas} [ibid. 28, 166-180 (1981; Zbl 0454.68033)], \\textit{W. Schnitzlein} [Abt. Naturw. Univ. Konstanz (1981; Zbl 0507.68025)] and \\textit{H.-J. Sto\u00df} [Computing 6, 309-317 (1970; Zbl 0222.02036)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q792093$9569B248-A270-46A1-8925-A0A7AF5FDE4D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792093$1D2576C8-1C00-4CA8-A14C-05782BC290CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792093$ADBEC800-A88D-4260-8F77-79A1152BE3A5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ea6d197ebf63538ef8895fb05bae538a03222319","datavalue":{"value":"3852436","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792093$C08890C7-6718-4B83-9C89-5237876062C1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b04b0c12ba853bc6991c30e0d7b78a10ae28b65","datavalue":{"value":"real-time computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q792093$2EF4C9F9-3EB0-40F0-9934-83E7D4B313EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c51c5dfaab9c1b6e4d23fc83c6f2cce17411e84","datavalue":{"value":"real-time simulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q792093$0F75EA7E-E91E-4D58-893D-01DAACDDC170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c74dd19c2922364f90da3e85f97d0cab3727c80","datavalue":{"value":"d-dimensional Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q792093$EBB69C9F-3DD7-4A1B-8268-3EA639038EEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4af9aaf03901eb942b772c2bc160f7d0c1f75689","datavalue":{"value":"descriptional complexity of rectangular figures","type":"string"},"datatype":"string"},"type":"statement","id":"Q792093$A6322AC7-F784-4377-8FFF-430289EFE451","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce524b0c7940e9706063c12430e952a441c4e370","datavalue":{"value":{"entity-type":"item","numeric-id":290241,"id":"Q290241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792093$7F8009F8-CBCC-461D-8B82-9123443960E7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e860208dea0a8f07f1622b3764a2f40159457c4c","datavalue":{"value":{"entity-type":"item","numeric-id":186051,"id":"Q186051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792093$B47831D9-69C3-48D6-B2D2-072591450A57","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":"Q792093$0174CB34-12DF-45D3-88FB-A5B6CA945C29","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0b07928ccb7a6e6b55461bacba3d189e50509560","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90063-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q792093$1EE0E5D9-F156-40DF-B57C-D2B0DE7F6DAC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"07f728d54bcdd18db69e1e396a5af5be62ec3c31","datavalue":{"value":"W2029121016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792093$A869061F-A1D6-4466-A186-443740E94427","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"248ec5667ec5a52c84f7c9aad98d22c2ca290e71","datavalue":{"value":{"entity-type":"item","numeric-id":4077448,"id":"Q4077448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792093$5A6EB858-7BB8-4901-A8CF-9574AB74C213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c03f59f732fadb25d73374711a8debe463dae270","datavalue":{"value":{"entity-type":"item","numeric-id":5677074,"id":"Q5677074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792093$F089EF34-9272-43D2-BE2E-4458E56FE4E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"609827d615096bb66d710b3f486ba33c91600d45","datavalue":{"value":{"entity-type":"item","numeric-id":3902483,"id":"Q3902483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792093$EFB8E118-1279-4E45-89E5-E0A45588E367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db962262028c64058844e2dc42405557ebfe2709","datavalue":{"value":{"entity-type":"item","numeric-id":2547545,"id":"Q2547545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792093$A48744F1-9613-459E-9056-C85DABDF8D9B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f960b66639c6ad8cb0413b9e610c7901a072bb05","datavalue":{"value":{"entity-type":"item","numeric-id":4377274,"id":"Q4377274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"921058d7a7d7be62342349d3c2e7d82e61089cde","datavalue":{"value":{"amount":"+0.82780033","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":"Q792093$37DC5307-E0DD-4F4F-869C-F2FC8A7E72CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4add3e0175cdd77b2ce13fbf8c8c87fd27d839be","datavalue":{"value":{"entity-type":"item","numeric-id":2817660,"id":"Q2817660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2dcd55713f32a9d61467a368b9ab774342908470","datavalue":{"value":{"amount":"+0.8278003","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":"Q792093$9CD3566D-CE08-486C-9A78-F60FBC7F998F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1daad9cd11516cde9ca1269ff80c341146d5e78d","datavalue":{"value":{"entity-type":"item","numeric-id":1314683,"id":"Q1314683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a482d7a0a39e3911123334fcfd159768adf7b5a","datavalue":{"value":{"amount":"+0.74195313","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":"Q792093$87B43832-7113-4EC6-87C0-A9DA403C46D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a378f23a264fedc09026c68cd254d5af1f0764b7","datavalue":{"value":{"entity-type":"item","numeric-id":1329224,"id":"Q1329224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73abb866de64db8aabcfdc35aca6c0fec2a78838","datavalue":{"value":{"amount":"+0.7274331","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":"Q792093$78B4F5F4-C92F-4A9A-9729-AAD9E748BF4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8c08ffceeb83a02193e2400a33f2dedfa3f53a3","datavalue":{"value":{"entity-type":"item","numeric-id":6483286,"id":"Q6483286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf75b83182ae12cb011662d745076055fd2645d5","datavalue":{"value":{"amount":"+0.72236574","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":"Q792093$88439D61-CEF3-4AA5-807E-21424F1A330E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ba23e3e152fbbc1c3379f7e90a8db7887d944ad","datavalue":{"value":{"entity-type":"item","numeric-id":5937334,"id":"Q5937334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf75b83182ae12cb011662d745076055fd2645d5","datavalue":{"value":{"amount":"+0.72236574","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":"Q792093$806D3495-107E-4EB1-9364-52209DB22D81","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On heads versus tapes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_heads_versus_tapes"}}}}}