{"entities":{"Q2460065":{"pageid":2470808,"ns":120,"title":"Item:Q2460065","lastrevid":50212475,"modified":"2026-01-13T13:12:33Z","type":"item","id":"Q2460065","labels":{"en":{"language":"en","value":"On Markov's undecidability theorem for integer matrices."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5211608"}},"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":"Q2460065$5993C136-517A-40B1-A73F-FE1E7B34BF1C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6c871a055ce5de68f804803fc677b02127935397","datavalue":{"value":{"text":"On Markov's undecidability theorem for integer matrices.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2460065$115963AA-EB82-4B50-A767-7909EF3E7ED4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aa40a1452f0a50e380fbbed86411661e3e3cec6a","datavalue":{"value":"1131.20042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2460065$114A87CA-3592-484F-AF36-7635ED761FD3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"59d83211de22bb9037eb8bb17627d49ead9fa4a9","datavalue":{"value":{"entity-type":"item","numeric-id":287018,"id":"Q287018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2460065$3DE76EAC-CA7E-46CA-A148-03EB00EFC9CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2e1040094bf74402ed6fa4c78436dda64e324757","datavalue":{"value":{"entity-type":"item","numeric-id":1806108,"id":"Q1806108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2460065$C310B552-0CA3-43B8-B8B7-E029B44117E5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"28dbf90a09492d81530507fd711b9336815e58a3","datavalue":{"value":{"entity-type":"item","numeric-id":172569,"id":"Q172569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2460065$5F8C205B-B09F-4A37-A105-453FAF97ED67","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"eb246d74428bf95f3ed2ed9a3bb24dd112fcb276","datavalue":{"value":{"time":"+2007-11-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2460065$86693130-AFD6-4306-8F49-D128D93D8C12","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1e17327ce7375ad3c211728f941924d48c1e93c5","datavalue":{"value":"The general problem under consideration here is to determine whether or not two finitely generated matrix semigroups possess a common element. In 1947 A. Markov showed this question was undecidable for semigroups of \\(4\\times 4\\) matrices even in a very restricted form, while Krom proved in 1981 that the problem in the \\(3\\times 3\\) case was similarly undecidable.   This paper gives a new proof for the \\(3\\times 3\\) case by proving, among other results, that given non-singular \\(3\\times 3\\) integer matrices \\(X_i\\) (\\(1\\leq i\\leq n\\)), it is undecidable whether or not there is a common matrix \\(X\\) that is a product of the \\(X_i\\) (allowing repeats) and a product of another given pair of matrices \\(A_1\\) and \\(A_2\\) (and indeed stronger but more technical results along these lines are proved).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2460065$50603D53-E8FC-4E7F-88B1-6D480CAD8979","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2460065$D8628C62-045C-4179-A316-4CCA8C93A43C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"28c26f343d909e4a66e25387c3adc02e650c67e8","datavalue":{"value":"20M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2460065$AF37E938-6AEC-431D-BD10-93F4B5566F9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79c9a014785e41c94f76c463174af5cf2a59ec70","datavalue":{"value":"03D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2460065$523991CB-6CBA-4FF2-B331-2F23A213C0B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f0b321fafd33da205994db3b946bd7cfe9a54983","datavalue":{"value":"15A30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2460065$B1E89D03-1142-49B0-BB51-3799E9A0B979","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d54ae9a212689b1eb52541b19184aa8a9609bb1c","datavalue":{"value":"5211608","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2460065$3DFA6A3D-681A-4043-832C-00C37832F060","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2b017f0b8007e9d8e6844c9baffa58d5f60d151","datavalue":{"value":"finitely generated matrix semigroups","type":"string"},"datatype":"string"},"type":"statement","id":"Q2460065$D581DA40-26A8-44F2-97D9-616CE35543CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2460065$F15592BA-B799-47FF-8DBE-70261D22C90C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"054529b5e09e7b9cb181f02f83c3b0d20bf30124","datavalue":{"value":{"entity-type":"item","numeric-id":444661,"id":"Q444661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2460065$F49173CF-3DA7-4FDE-B95C-879B56F455AC","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":"Q2460065$956B718D-02FD-4EE2-8928-13A8D1DEE5F4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aa6eb80ec003d09921b7b87bba67321092960888","datavalue":{"value":"https://doi.org/10.1007/s00233-007-0714-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q2460065$F4DF6B6C-8FEE-4081-BBAE-1993A57C9AEA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c248c0a74f9ef8187515a139fe128502862d5c24","datavalue":{"value":"W1985893106","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2460065$E51C1748-8A96-4E95-9E91-557243731F82","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"22ee633edf8eb40cd0d355c52084ffe4e3e9d307","datavalue":{"value":"10.1007/S00233-007-0714-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2460065$105A0B2E-09D9-40F9-B1E6-6B360B5C2407","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9079f0de480ff1fcc0e30a693788f3604bef63dd","datavalue":{"value":{"entity-type":"item","numeric-id":5758380,"id":"Q5758380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b26bad4c98e431c9a1d875310ed4d2b79e8b5bb9","datavalue":{"value":{"amount":"+0.8590884804725647","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":"Q2460065$6762F125-9DFC-4C00-8302-084515FECDFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97455e62038cf4043c224a6e543ec75f3bc7a7bd","datavalue":{"value":{"entity-type":"item","numeric-id":1275458,"id":"Q1275458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78af611208c0fe661adb15fee32260ea0a98081d","datavalue":{"value":{"amount":"+0.830295205116272","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":"Q2460065$2B2F33F0-00B8-4E4D-868A-79B1DA09594B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed2ba313c9b311d0119ec178ea7a88399216275f","datavalue":{"value":{"entity-type":"item","numeric-id":4737895,"id":"Q4737895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ac5e2969bbb029a5e615ab1d5d1724f06c14d7d","datavalue":{"value":{"amount":"+0.8277199268341064","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":"Q2460065$69FDAD9C-F4B9-4C01-87A9-D2F93CEE3634","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59e4bba44aaacf5bf3b0592340db8607321ba5e9","datavalue":{"value":{"entity-type":"item","numeric-id":5422263,"id":"Q5422263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1445e87326dea98f92ebab69e9065f6540ebdf1d","datavalue":{"value":{"amount":"+0.8078731894493103","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":"Q2460065$CA88BF18-E6B2-4005-A5CF-CD5C14C12F8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2dab127039f03a6f981987112773540e902db92","datavalue":{"value":{"entity-type":"item","numeric-id":4680730,"id":"Q4680730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4ffc4381819a0c0cb74a2c158f8877cb81db7ab","datavalue":{"value":{"amount":"+0.8057283163070679","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":"Q2460065$D16D7BD0-1711-465A-86D2-672EC80B1167","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2460065","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2460065"}}}}}