{"entities":{"Q3347301":{"pageid":3358009,"ns":120,"title":"Item:Q3347301","lastrevid":110460584,"modified":"2026-11-17T02:50:12Z","type":"item","id":"Q3347301","labels":{"en":{"language":"en","value":"Two Tapes are Better than One for Nondeterministic Machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3890737"}},"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":"Q3347301$49E7D6C9-32C5-4BD6-93F3-D563B9E479FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"46265264928c070eb31ba1ffb669ae092fc015a8","datavalue":{"value":{"text":"Two Tapes are Better than One for Nondeterministic Machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3347301$FEB0B6BC-1F7E-4322-BB17-518ADD9AABD7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c7bf26b03cbb7f7d60c776f3830344dfc3ea79fe","datavalue":{"value":"0558.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3347301$844FBBB5-DACF-4457-98F5-50A467E0BC3E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b163c28aeb6f52cfde6bc00a442eda4948673768","datavalue":{"value":"10.1137/0213016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3347301$34FC76FE-690E-4F5C-A28E-F5DA81FE4466","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3efab329f274df7b952f3315a3cb6e7ad39df8e3","datavalue":{"value":{"entity-type":"item","numeric-id":596323,"id":"Q596323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3347301$CD9F9238-9685-4A2B-8950-4914F1088B3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e427d06588e0f5e6a2a228b1ad8e00160bd43819","datavalue":{"value":{"entity-type":"item","numeric-id":673782,"id":"Q673782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3347301$97C184F5-3BE7-4887-91DA-60FF72633BE7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3347301$DB824BA0-1AAA-44A4-8008-66872021E70C","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":"Q3347301$856E19C9-3C4A-469C-97C6-D7330F60186B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3347301$688D6188-D526-4A80-8CB3-F355CFE72220","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"06c50f0f121e86c9a5a1bcda6e5c9ece3705f35b","datavalue":{"value":"3890737","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3347301$461EFEEF-67FC-444A-BCD7-72D45C1501AD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffdc65612c6e2ba8f251c1e80276b03e6a71632c","datavalue":{"value":"computational power of real-time nondeterministic Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q3347301$F235268C-9997-4778-89F0-133A4756D359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d476188a8c41716ce79df0228a6a064a9883766","datavalue":{"value":"two working tapes","type":"string"},"datatype":"string"},"type":"statement","id":"Q3347301$CADEF7E5-39B0-4810-8A71-60FEAF3CEB52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c5e489f233706b2c4c5f624cd56cec8a1e178d0","datavalue":{"value":"single working tape","type":"string"},"datatype":"string"},"type":"statement","id":"Q3347301$B5C1F0B6-9B70-40EA-9B18-D36307ECA67E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99c40f8874ea49718c8d94e84dc64b2618c1ee8a","datavalue":{"value":"reversal-bounded machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q3347301$F6F31436-D742-4C98-8784-0BD0DB69A2BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6cc6bd59ca608fb63bf697221d1fbdafd24e5a10","datavalue":{"value":"two pushdown stores","type":"string"},"datatype":"string"},"type":"statement","id":"Q3347301$1B5A8545-7BED-48D9-A4AB-99D464C81472","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":"Q3347301$A6331CCA-76BD-4A24-957C-704BD0F39A45","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e352cf7853b85e71395542c4a28c5675eada2ed0","datavalue":{"value":"https://doi.org/10.1137/0213016","type":"string"},"datatype":"url"},"type":"statement","id":"Q3347301$A879C02B-9628-4490-93C9-EE060772F3B6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b2985294ae0328d8a215cd0fd4639288c04a6b60","datavalue":{"value":"W1981106003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3347301$6E4CD5B8-7546-42EF-BE0A-C97CDBE41991","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2031cf7011509c3fe907a55f938b57f5faf73af2","datavalue":{"value":{"entity-type":"item","numeric-id":1111386,"id":"Q1111386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e06a4a1e166a1dbc5b90784ca58421d6f9963a74","datavalue":{"value":{"amount":"+0.8432027697563171","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":"Q3347301$22650045-0021-4980-AAC9-5025CDBF8E0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"674ac0e7af44c6d5fef6df73de8c10783efe0d0a","datavalue":{"value":{"entity-type":"item","numeric-id":801685,"id":"Q801685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6f00d83c2520bc2b9b57ce27847d4ef6d9eda9b","datavalue":{"value":{"amount":"+0.7953180074691772","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":"Q3347301$6CA6B133-B0D7-4D79-A46C-2467379B4175","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c699c99bbab2b0955362dfb2fe4a4799ad276109","datavalue":{"value":{"entity-type":"item","numeric-id":1113670,"id":"Q1113670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b09910cdd52d375e0a8810e81c51dea14fdaec7","datavalue":{"value":{"amount":"+0.7940258383750916","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":"Q3347301$9B0DA9B5-B765-4D72-AEC6-7E941349FC1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01abaf6620ffcfe344566312f8a89e9780160201","datavalue":{"value":{"entity-type":"item","numeric-id":4465338,"id":"Q4465338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84aa9295464aff9848d9d20d2813472086f24f0f","datavalue":{"value":{"amount":"+0.7895453572273254","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":"Q3347301$80D1B51A-1CAF-48FE-9569-3A109EA78971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df7e7a2f818446e98ed17e47305dbaa8ac1be22e","datavalue":{"value":{"entity-type":"item","numeric-id":3747727,"id":"Q3747727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"788ba0c0841f1e6236804faa493937e162886e9e","datavalue":{"value":{"amount":"+0.7866885662078857","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":"Q3347301$DFA656AE-1E98-439E-AEBC-C49BA0C0D414","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a764c783a6e72b9b40dc614c0dc90dcaec726855","datavalue":{"value":"This paper solves two open questions about the computational power of real-time nondeterministic Turing machines (ndTms) with a different number of working tapes or pushdown stores. A machine is real-time if it reads a new input symbol in every step, and stops immediately after reading the endmarker. The first result states that an ndTm with two working tapes accepts in real time more languages that an ndTm with a single working tape, while it is well known that furtherly increasing the number of tapes does not affect the power of the machine [\\textit{R. V. Book} and \\textit{S. A. Greibach}, Math. Syst. Theory 4, 97-111 (1970; Zbl 0188.331)]. A second theorem shows that even two pushdown stores are sufficient to increase the computational power of one-tape ndTms. The same questions are then solved in the case of reversal-bounded machines, that is machines whose heads are allowed to make only a constant number of reversals. Even for such machines, it is shown that two tapes are better than one and that two pushdown stores are better than one tape. Finally, it is shown that real-time one-tape ndTm without restrictions are more powerful than the corresponding reversal-bounded machines. The paper terminates with a list of further open problems about the power of linear-time ndTm and their comparison with real-time machines: Are linear-time one-tape ndTms better than real-time one-tape machines? Are linear-time two-tape ndTms better than linear-time one-tape machines? Are linear-time two-pushdown ndTms better than linear-time one-tape machines? Are linear-time three-pushdown ndTms better than linear-time two-pushdown machines?","type":"string"},"datatype":"string"},"type":"statement","id":"Q3347301$5E00F38C-932D-49E7-B6C0-4FB548A8A7E4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3347301","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3347301"}}}}}