{"entities":{"Q801685":{"pageid":803533,"ns":120,"title":"Item:Q801685","lastrevid":64442541,"modified":"2026-04-11T19:53:47Z","type":"item","id":"Q801685","labels":{"en":{"language":"en","value":"On two-tape real-time computation and queues"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3880120"}},"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":"Q801685$24F8362D-5363-4615-84C8-83BF96D9CFF6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ada6d831d895f7910202c107a6772053d459abdf","datavalue":{"value":{"text":"On two-tape real-time computation and queues","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q801685$403CBFA7-CB59-425B-875A-BCC2FDFDDE83","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"081b3a9042b4760c1581d1b4f7241b67279bc38e","datavalue":{"value":"0552.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801685$44911AE4-0B6C-47BE-A96B-8338E18693AE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"688eb7b369229e34037198687233123e02fb15c0","datavalue":{"value":"10.1016/0022-0000(84)90001-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801685$5946A249-D492-4815-9170-43041E4BC1CF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"60b2337bc50810374b4ca0c66cb11407509a5fbe","datavalue":{"value":{"entity-type":"item","numeric-id":354146,"id":"Q354146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801685$27BFE4D4-EAB6-4403-95ED-3C7D6BF137A3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801685$AC44AB25-820A-4E98-8A13-922D790ADC06","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":"Q801685$30EE9922-F457-4F51-BF1E-C5C533A548B7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3d3b2db0b37ea3904c6d93ed4cb8e98cdf02f1df","datavalue":{"value":"https://ir.cwi.nl/pub/6570","type":"string"},"datatype":"url"},"type":"statement","id":"Q801685$4797A2DA-2B31-40CA-BBEA-CD565D6DD51B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1e850f1ff084729c8ba33de616c0aaf7ae1a49dc","datavalue":{"value":"A Turing machine with two storage tapes cannot simulate a queue in both real-time and with at least one storage tape head always within o(n) squares from the start square. This fact may be useful for showing that a two-head tape unit is more powerful in real-time than two one-head tape units, as is commonly conjectured.","type":"string"},"datatype":"string"},"type":"statement","id":"Q801685$88C4B581-4DE8-4B57-ABFD-392878026097","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801685$8F37D8A7-57BB-4A88-B035-0A4C840B245A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801685$4E75560F-5D2F-4625-8465-E9C9B1C38E23","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bf94c0263d09d878e711f3655a7bf59f58446ae0","datavalue":{"value":"3880120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801685$AFD1BD3D-83A2-41CA-8697-F67724AD9402","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"709c0f1970b625c924543cd42f8a54c7ce976554","datavalue":{"value":"Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q801685$89DDD7F9-3D58-4E7A-8300-6DE94B4B678A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d5a9e445983e65fa6e5ae8fb7de4044656bacd6","datavalue":{"value":"queue","type":"string"},"datatype":"string"},"type":"statement","id":"Q801685$58A0622E-0E42-46EE-9C5E-BBF5FD3E5F80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4daa5e2050004f436ae0cb281fafb4830c61d547","datavalue":{"value":"two-head tape unit","type":"string"},"datatype":"string"},"type":"statement","id":"Q801685$B629D8CC-151E-48C8-828E-7CBDEF9AAFA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8ccdfbe81c93aadb186d6c32d13b9e77abebeee","datavalue":{"value":"one-head tape units","type":"string"},"datatype":"string"},"type":"statement","id":"Q801685$36230F5B-DC57-4044-A064-B8BDB01D2F88","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":"Q801685$06300894-936F-49E1-B1A8-27458B86C25A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7a1e459732e9f0878dc392f66354bb1da750e9b1","datavalue":{"value":"W2024671403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801685$D248788A-611F-46B6-8AF8-37161A9A8ADB","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":"Q801685$FBA950A5-B32B-4929-81CC-795E4DF6CEA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"573f9451c18cb73fe59719b8f8cf8f07593917b3","datavalue":{"value":{"entity-type":"item","numeric-id":4137091,"id":"Q4137091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801685$08345E56-362B-4E40-9105-A40F063CC1FB","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":"Q801685$F9DE91CD-2B9B-4663-8A15-97B4934FABA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2c5f4a456f9910b4c4f2a1d73e4561be8a5dbc2","datavalue":{"value":{"entity-type":"item","numeric-id":3214803,"id":"Q3214803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801685$4F901D5E-C99A-4CA9-AA18-4D07718AC4DB","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":"Q801685$4C04360C-4A1B-4345-896C-D2F320BA5880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f784fed1af1400bbd1a75108ed44085f78e30f5","datavalue":{"value":{"entity-type":"item","numeric-id":1156484,"id":"Q1156484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801685$42B2EFA9-E7D7-47B9-BDFB-F444B00F6A89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e61503bf3e00baa669bf5e7642a44d7f25174d9","datavalue":{"value":{"entity-type":"item","numeric-id":792093,"id":"Q792093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801685$42D017AC-973F-426B-8E5A-AA57C93B720D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"938bca41e7809cafc24981e9a1a62381c68e7f76","datavalue":{"value":{"entity-type":"item","numeric-id":3321474,"id":"Q3321474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801685$D17D25AB-7B01-4971-BCC3-33331C0A1F7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6f110f1fdd1b1965a6a71deaa20a3ec523c9cbf","datavalue":{"value":{"entity-type":"item","numeric-id":2526723,"id":"Q2526723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801685$E7D0617C-8F7D-49A2-8598-8EA3040CBD26","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":"Q801685$AB239A03-535D-4364-9626-D386E40B96AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc361f0cac72d4df2e2fe4cbb37d4d1b1c354d90","datavalue":{"value":{"entity-type":"item","numeric-id":5672881,"id":"Q5672881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801685$E99CB6E9-8EB8-4F51-B382-E3E0616D319A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8692fa559fea4a62f9d4176a584cc0bc7752375e","datavalue":{"value":{"entity-type":"item","numeric-id":3886865,"id":"Q3886865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801685$F8177286-95E9-4E3F-B31E-50AF455DDA38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c3926725253ef4ab031c42140743ad86ac5bbf1","datavalue":{"value":{"entity-type":"item","numeric-id":3933743,"id":"Q3933743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801685$482D30A2-C86B-4735-89E6-5EB1D74B18C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f3f4891ae0332dd2e03bc75000d38fd64a75fab","datavalue":{"value":{"entity-type":"item","numeric-id":5470725,"id":"Q5470725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3201fb3b3c0b304f85a355278c3c79b81a2653f0","datavalue":{"value":{"amount":"+0.8406689763069153","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":"Q801685$D0BAAC1A-1816-4803-B83D-FA39746E7032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61f4aaface313214d2a90d42cc007de2ff3991ad","datavalue":{"value":{"entity-type":"item","numeric-id":685436,"id":"Q685436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42c4a83242efb90e3b7cd32e129a37025cee452b","datavalue":{"value":{"amount":"+0.8343716263771057","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":"Q801685$5FF860CC-9DF1-48A5-A6C3-3970FDA0B08B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43dfab877acf82f2b5b43ba33c8587f4298c5b5a","datavalue":{"value":{"entity-type":"item","numeric-id":4035658,"id":"Q4035658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eddce9b487e6b1d5f610a8c6db87fdb7eb84d193","datavalue":{"value":{"amount":"+0.8300127983093262","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":"Q801685$686691B7-D57A-4CAB-9262-A3E55653ED56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a52b1f826f4fa6055ca46f4d934c13937973e72a","datavalue":{"value":{"entity-type":"item","numeric-id":3347301,"id":"Q3347301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eddce9b487e6b1d5f610a8c6db87fdb7eb84d193","datavalue":{"value":{"amount":"+0.8300127983093262","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":"Q801685$6BC96285-E1D6-4E83-B1FA-11043358CCE1","rank":"normal"},{"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":"fff89d9140561e6c88d8d19d02f1e28420530ba0","datavalue":{"value":{"amount":"+0.8034493923187256","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":"Q801685$BF4868B9-E2CA-4A93-A490-4EC3D2C417B2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On two-tape real-time computation and queues","badges":[]}}}}}