{"entities":{"Q1111379":{"pageid":1122128,"ns":120,"title":"Item:Q1111379","lastrevid":66688608,"modified":"2026-04-12T11:59:37Z","type":"item","id":"Q1111379","labels":{"en":{"language":"en","value":"Transposition of an \\(\\ell \\times \\ell\\) matrix requires \\(\\Omega\\) (log \\(\\ell)\\) reversals on conservative Turing machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4076615"}},"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":"Q1111379$0CEBA3C5-01CB-42F1-8346-256207D1243B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"caeb65baaeb9b58fe90fde6eea72abe57e38feba","datavalue":{"value":{"text":"Transposition of an \\(\\ell \\times \\ell\\) matrix requires \\(\\Omega\\) (log \\(\\ell)\\) reversals on conservative Turing machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111379$AF5C2861-562B-4B0C-8D59-6DBBBD016222","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dfdeb26330ac4a2b42680ae4ea80e5b6578421a1","datavalue":{"value":"0658.68047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111379$39781907-96F0-4CBA-885B-E83231FC7A3A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8f70066f0ba92733869b85807dbb021d8ee08c47","datavalue":{"value":"10.1016/0020-0190(88)90163-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111379$9FBAAE1B-2E97-4EEF-9438-4D23C40E2B79","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a0ec2208b25ece90cbfecb2a3cc411806b924f37","datavalue":{"value":{"entity-type":"item","numeric-id":1111378,"id":"Q1111378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111379$265761B5-5AD1-400D-BC88-AD9D217047BB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111379$EBBF4E1D-046B-49FC-84FB-F65A113A753A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1111379$3BD91E79-EF47-47A1-A46A-69DDD36B6730","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"51758ae7cb128e9bb6ce2be4298eacb0f257b2b0","datavalue":{"value":"We consider matrix transposition on a k-tape Turing machine which treats entries of a matrix as indivisible entities (`pebbles'). We call such a machine a conservative k-tape machine. We show that such a machine requires \\(\\Omega\\) (log \\(\\ell)\\) reversals to transpose an \\(\\ell \\times \\ell\\) matrix.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111379$C80302DF-2348-489C-A18C-097EE6BB5997","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111379$59AE8238-2F14-4B05-85BF-4D0BED0459C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111379$D7CCBD57-0C29-4686-999E-47074B0A0DF6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2a22751b02087b20b2bcc4330a9d8ceaa1522dc3","datavalue":{"value":"4076615","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111379$36F199FF-22B7-4C4B-B200-3197526206B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc6943d9e89e4b240a0674fc93f634b56334b21b","datavalue":{"value":"peppling game","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111379$B4D8CC95-291E-4F5D-8A9A-0D23F28FD636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2217666a384d291df6fb0dc72a41f7e9cce4afa5","datavalue":{"value":"matrix transposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111379$80D9EB2A-DE59-48D5-9A35-0DFE5DB76370","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"709c0f1970b625c924543cd42f8a54c7ce976554","datavalue":{"value":"Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111379$C5560207-5A36-42B7-8E36-D558711C6585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"630938c5da18e078d878f7b956e797486e6411f7","datavalue":{"value":"conservative k-tape machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111379$07E1EB06-4F17-4C79-A3AE-6B4823E4B819","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":"Q1111379$A29131CD-9360-4B9F-AEAC-95675A2C88B6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"41a745736e80316281791591c0cbc1f7ece16ae9","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90163-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111379$65D0CBB2-4D4C-4721-8FC0-D5CA134965CA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f5ba581e55377a71f99742fa308a2c78f3b18638","datavalue":{"value":"W2095345626","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111379$1FECAB92-988B-468B-BD5D-28DDC115AB99","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc227928812260e1dc2f5a33574844481df95a1f","datavalue":{"value":{"entity-type":"item","numeric-id":3978172,"id":"Q3978172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111379$FEAA054D-7B9E-4AF2-BA86-BF80AFF36ECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af8d9eb004372ad97ad8e1d8be30b3c23091db7f","datavalue":{"value":{"entity-type":"item","numeric-id":5649368,"id":"Q5649368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111379$58F1E6FB-D92E-4609-81AC-2FC971AA05CA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"719f948616a6000eaf1ca9a05453e56888862e1b","datavalue":{"value":{"entity-type":"item","numeric-id":1208717,"id":"Q1208717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f0d06ac023f73bd3470f6dcce0a1bdc804b1bf0","datavalue":{"value":{"amount":"+0.828612208366394","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":"Q1111379$11EE86CF-DBDF-421E-ADD5-28F042B01905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f1dd153135242659cc79af9ec8f66baf2fc9ff3","datavalue":{"value":{"entity-type":"item","numeric-id":2272153,"id":"Q2272153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4974877140ddd8f9d7ff3aefe2ee4576c412313a","datavalue":{"value":{"amount":"+0.8274049162864685","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":"Q1111379$872FB4D4-3E9D-4108-A2D1-B4D06D9CB936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a61e66d0af71f2a529e85bcc0ff189df80fdf72","datavalue":{"value":{"entity-type":"item","numeric-id":3795216,"id":"Q3795216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0b192ebe52797a4ce4351c0b35fba411fca5e69","datavalue":{"value":{"amount":"+0.8242560029029846","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":"Q1111379$F16776D3-79FD-4784-A137-F0D308854711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa9246276aad9a1306f5c379cac0c0aa0b66032a","datavalue":{"value":{"entity-type":"item","numeric-id":808247,"id":"Q808247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efb0a469b9897f596f20999427ca68edbeaee45c","datavalue":{"value":{"amount":"+0.8129058480262756","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":"Q1111379$A3D9B74F-3421-4BFC-B80C-D89C6D46F441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5785911600dd57403705b2f3ef93368881c1c80a","datavalue":{"value":{"entity-type":"item","numeric-id":3751009,"id":"Q3751009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38ac4ea6acbee55b83c7e1d37a0fe7d06551a0fd","datavalue":{"value":{"amount":"+0.7614616751670837","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":"Q1111379$C8DD34A4-7491-4720-8AC1-8F9AE2CC6B51","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Transposition of an \\(\\ell \\times \\ell\\) matrix requires \\(\\Omega\\) (log \\(\\ell)\\) reversals on conservative Turing machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Transposition_of_an_%5C(%5Cell_%5Ctimes_%5Cell%5C)_matrix_requires_%5C(%5COmega%5C)_(log_%5C(%5Cell)%5C)_reversals_on_conservative_Turing_machines"}}}}}