{"entities":{"Q920983":{"pageid":922831,"ns":120,"title":"Item:Q920983","lastrevid":65397096,"modified":"2026-04-12T02:18:54Z","type":"item","id":"Q920983","labels":{"en":{"language":"en","value":"The difference between one tape and two tapes: With respect to reversal complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4164824"}},"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":"Q920983$C07BCC5E-14B2-44B1-82FD-68FA368E4473","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"282cb486fd8d7a0028aea86579aba06b798d4908","datavalue":{"value":{"text":"The difference between one tape and two tapes: With respect to reversal complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q920983$0093D30F-5A51-46B2-917F-36C0D3958B1F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f2b75ad71bae76b86d2c766198bb2e1054c1dc2c","datavalue":{"value":"0709.03033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920983$593C9519-0B50-49F0-B328-615B889F9179","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d633d68d546847de4303cb8d21f9954f931d11c1","datavalue":{"value":"10.1016/0304-3975(90)90178-K","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920983$A45EE2E6-8D70-4CE4-891D-A4D5CFE0E8DE","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":"Q920983$FFE590CC-D159-4232-9B65-804AC92C17A6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q920983$899A2EEA-8286-48F0-8EA5-1DCC1DDE649F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6faa46b9030e8302d89ccb5b0c89a3c33e11f01e","datavalue":{"value":"Reversal complexity refers to the number of alternations in the moving of a head on the tape of a Turing machine. The paper deals with the study of the reversal complexity on 1-tape and 2-tape Turing machines. For the deterministic case, it is proven that a Turing machine with a single work tape cannot simulate a k-tape Turing machine in an efficient way provided that \\(P\\neq PSPACE\\). A result, shown in a previous paper, claims that a k- tape Turing machine can be simulated by a 2-tape Turing machine without much loss of reversal resource. The two results indicate the 2-tape Turing machine model appropriate for the study of reversal complexity. For the nondeterministic case, the correlation between space complexity and reversal complexity on the 1-tape Turing machine model is studied. B. S. Backer and R. V. Book (1968) showed that the 2-tape Turing machine model is too strong for reversal complexity. In contrast to this result, the present paper shows that reversal complexity is linearly related to space complexity for the case of 1-tape Turing machines. A list of valuable remarks ends the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q920983$37EF65F8-FA81-481B-B8AA-D826E438A4D6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920983$2ED448B5-C6C8-4EFB-B56D-2D1D768A3850","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920983$5124078E-15E6-48FC-9189-E5B91BFF4B68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920983$1A3023BB-6AD8-49FC-839B-7502B35EF644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920983$76888743-E187-4431-97ED-AD7A94119CE1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"df61aad89548203eac8c1e39469559620943f54d","datavalue":{"value":"4164824","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920983$B3C4B7FA-AF4E-4793-BD59-8404EF1427CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q920983$626932EA-D3D3-4341-A0FC-353F1BD5EC29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ea1ded585295bf04da26576978052552f241c4d","datavalue":{"value":"simulation of k-tape Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q920983$EC3E2854-F8DC-4321-83BD-12787E6133B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4a4c7666d5ca797519cbb53116f01c03b262d81","datavalue":{"value":"number of alternations","type":"string"},"datatype":"string"},"type":"statement","id":"Q920983$F230F8EA-3F1D-45E4-95C1-3DCF12C9CB72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c5d165f7251b59a9b193356776b4f2dff5f9d16","datavalue":{"value":"reversal complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q920983$2D1AEBEA-B720-488C-86EC-6C269AFBA5DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fc59007b2b1960a263350309435ca1e06e896b5","datavalue":{"value":"space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q920983$9E664A19-C22E-4D3C-8BB8-09302CAE6B63","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d03752c29b41d1b87b62e2669413b34e8ba69f6","datavalue":{"value":{"entity-type":"item","numeric-id":1599636,"id":"Q1599636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920983$17DBF98D-E321-4F82-B6D9-02D56D111476","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e5adb2f5b9beef2201bef72e73c6f511c159db61","datavalue":{"value":{"entity-type":"item","numeric-id":493519,"id":"Q493519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920983$938C4256-861A-4163-9F3A-B6FEE5C2E8D4","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":"Q920983$F4A82C2A-9C15-4F2B-BE9F-26F9EFE3D46D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b059df79753dba48fb66fda4ddb1cf3fa023547","datavalue":{"value":{"entity-type":"item","numeric-id":1219160,"id":"Q1219160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920983$5C996706-6DC1-45DA-91A5-E2ECCE48B2E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9317a61e5aadd5c9592adbc8c3d7781f047c2a25","datavalue":{"value":{"entity-type":"item","numeric-id":2540551,"id":"Q2540551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920983$2BED3D5C-3CC8-4A18-879D-EDA6017ED249","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce85fb2f2c444151f9b0af0be604d11f8e1025a7","datavalue":{"value":{"entity-type":"item","numeric-id":2560051,"id":"Q2560051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920983$BFF7F2D8-2377-46B6-9D1F-F0453F022D87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14fb011395b085a0ad4513663cab5f1c04c8f557","datavalue":{"value":{"entity-type":"item","numeric-id":5638291,"id":"Q5638291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920983$6E050748-5499-472F-8485-EE88CEC0807B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bcdf9bade970dbbdec8a2177783f04e60e5077e","datavalue":{"value":{"entity-type":"item","numeric-id":3957949,"id":"Q3957949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920983$EC8EE3EE-3C64-4E03-9E76-1FE981B97865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920983$AA303BC6-015B-4AF0-A4B0-C6D5B1D2E25E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q920983$E8D086E4-24A3-4405-AB69-266851295D23","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7cbad9bc105a6fac7beb6ebe877857a54ac1c307","datavalue":{"value":"https://doi.org/10.1016/0304-3975(90)90178-k","type":"string"},"datatype":"url"},"type":"statement","id":"Q920983$9538E4D2-0BC4-458F-B7CC-79EAC97A420D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fb059e574390bad3f3440b9a5fa0a25b51a57c07","datavalue":{"value":"W2020818044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q920983$E7ACA548-9CF3-4DE4-ABD2-0932B6C5E7B6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1ed08a38cd8da415681f428e4c64171be319ef3","datavalue":{"value":{"entity-type":"item","numeric-id":4630261,"id":"Q4630261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4870c2920a59020a67af594deed228f52c6fbe39","datavalue":{"value":{"amount":"+0.7954068779945374","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":"Q920983$97C8CEF7-FE01-4561-AF15-D8A4889804B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3074fed2fb0a77e521f8764caa4441994444e32f","datavalue":{"value":{"entity-type":"item","numeric-id":3978172,"id":"Q3978172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af651b95632241b914e9adb81041e64a79b913fa","datavalue":{"value":{"amount":"+0.792371928691864","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":"Q920983$BF457207-FD69-40A6-99CF-7289A01AD575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4b3bc57ae3d576b3151acc30c134cd318f2d8ff","datavalue":{"value":{"entity-type":"item","numeric-id":4841767,"id":"Q4841767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f60fee01e0fca9398b7b9c8e43492a444eb241cc","datavalue":{"value":{"amount":"+0.7914013266563416","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":"Q920983$36B533EB-7B36-40C9-B047-FC8EA978F6F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"890c7a9231c0a57f211f259306633d47b7fc3ad0","datavalue":{"value":{"entity-type":"item","numeric-id":3219107,"id":"Q3219107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75cb7ac73adcb86da8586615f8b39ac92f6ed606","datavalue":{"value":{"amount":"+0.7777408361434937","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":"Q920983$11E3D0A5-B052-49AB-9AF1-E86CCF437C00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1680e11224a81d36b38cd30ffafdf480aa80a21","datavalue":{"value":{"entity-type":"item","numeric-id":1102114,"id":"Q1102114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"709ffdb731e7280ff3682108206bdea5a9579dd6","datavalue":{"value":{"amount":"+0.7755305767059326","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":"Q920983$4A90D037-DFF7-4867-98DB-7D454F080A4B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The difference between one tape and two tapes: With respect to reversal complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_difference_between_one_tape_and_two_tapes:_With_respect_to_reversal_complexity"}}}}}