{"entities":{"Q1065930":{"pageid":1076682,"ns":120,"title":"Item:Q1065930","lastrevid":66070809,"modified":"2026-04-12T07:20:16Z","type":"item","id":"Q1065930","labels":{"en":{"language":"en","value":"Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3922951"}},"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":"Q1065930$A056D2B1-0364-4CDE-8B61-42C7415A7607","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"215a356fdfe4349b183c7a69d4930804a45c6a04","datavalue":{"value":{"text":"Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1065930$A52D2634-3AE2-4EAB-869D-185A5193FFA6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b0610f7d01784bfadd7a6a5c696c6a3a3881a329","datavalue":{"value":"0577.20021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065930$F245CA6F-B4A4-482F-BCFC-2697F355A7C8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"583f6d2ce883aaaa318fe3fc7f23c9d739dd2812","datavalue":{"value":"10.1016/0022-4049(86)90136-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065930$8135899A-02E9-4723-8A5F-19F767CD79B4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc35669eb1adb45ee22100557a37b96fc4fe6bb8","datavalue":{"value":{"entity-type":"item","numeric-id":473133,"id":"Q473133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$F2BEE3C9-F6CE-4E28-B619-33048CFF4517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"12c58198c3d0b22a092b2689c9e597b941861988","datavalue":{"value":{"entity-type":"item","numeric-id":599170,"id":"Q599170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$4CFDA7C7-844F-477E-9FF1-7250A0F87207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"238d828199312a448029477c8576c0a75197d7d2","datavalue":{"value":{"entity-type":"item","numeric-id":514624,"id":"Q514624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$4283AFC2-F40E-4CDE-A448-7814194C8946","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"34a2791b3d9645796ba9cdff19dd05bcf40f0161","datavalue":{"value":{"entity-type":"item","numeric-id":168348,"id":"Q168348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$257363D8-AB67-4964-BA3E-122A88BC7C6B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1065930$9B363AEA-FF6B-4C12-9F6C-A04D00A44471","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f26b6cd29624fb24563a2e3fae4dbb18afcd9a63","datavalue":{"value":"\\textit{O. G. Kharlampovich} [Izv. Akad. Nauk SSSR, Ser. Mat. 45, 852-873 (1981; Zbl 0485.20023)] constructed the first example of a finitely presented group with insoluble word problem. The authors, in the first of a series of four papers, develop a technique, based on Kharlampovich's ideas, that enables them both to give a simpler proof of Kharlampovich's theorem and to attack other algorithmic problems for soluble groups, such as the isomorphism problem. The present paper is largely devoted to proving a somewhat more general and applicable form of Kharlampovich's theorem.    The authors start with a theorem of \\textit{M. L. Minsky} [Ann. Math., II. Ser. 74, 437-455 (1961; Zbl 0105.008)] that a partial recursive function \\(\\phi\\) on the natural numbers can be constructed, in a sense, from the operations of multiplication by 2, 3 and 5 and the partial operation of division by 30. The precise way in which this can be done is described by a finite oriented graph. This graph, in turn, is used to construct a finitely presented soluble group G of \\(9\\times 9\\) matrices over an integral domain together with a natural normal subgroup O of G. A recursive set of central words \\(u_ 1,...,u_ n,..\\). of words of G is then constructed with the property that \\(u_ n\\in O\\) if and only if n is in the domain of \\(\\phi\\). It follows that G/O has insoluble word problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065930$D3CFAD8A-F88F-42D1-A544-53A61C1C2867","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065930$9779A838-F78F-4726-94F1-86E6D999E48F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1a9473403ba5aadfa1076dd6525b25a3172ff28b","datavalue":{"value":"20F16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065930$E2D89904-FCEE-433F-8E3D-60A8CA9A3FA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5608e4dbe85e8f6c220cc8afcea2a4ada066e3fa","datavalue":{"value":"20F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065930$8806F149-E306-4A4D-AD20-BA8B1043DA34","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a0785f480a9d32a16c791161014f6bdd0f980564","datavalue":{"value":"3922951","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065930$361170C6-945E-4FFD-BA04-099DE143E09A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7d4836dab67ec6d377d7d3ccdb65a585787ef48","datavalue":{"value":"finitely presented group","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065930$9AA23A19-F7CF-40B2-A90E-8DFCC453A665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79c284bca20681f999fc1e29a71c38142a5d319b","datavalue":{"value":"insoluble word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065930$B43F04AB-75B2-4650-BC7A-71CCCEB48257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b177b74cc3e88395a0136db39d2b8a32534e16ba","datavalue":{"value":"Kharlampovich's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065930$5980600A-3A83-4C4F-98E1-E2F9D680CAAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c5f4b362ac670040d01985b5bb04f8548e4403b","datavalue":{"value":"algorithmic problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065930$7AAE2228-546D-4CA5-89EE-576564F426AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ec6f352a9bd4927c1b473e297be91b65a62e467","datavalue":{"value":"soluble groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065930$59B155CE-4A31-436F-BCC8-3C4F451F837F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b181606adcba6432b0019d481c67f516d9807857","datavalue":{"value":"isomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065930$A8ACE376-FDDB-4014-9DD2-F7D5A6638D84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"afec1146d9075dcf0a4080c42ee24c7604101b18","datavalue":{"value":"recursive set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065930$09AE628D-C1F7-4286-BE30-58B5AE37F8BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6284587b952ae0fa2f016255a364414a4431ded7","datavalue":{"value":"central words","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065930$0630F20D-067B-4A58-8A60-32FA04DC6177","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ca8a4debfbdded045cdc2d416d5d630762e34c0b","datavalue":{"value":"Q115364450","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065930$37F0B42D-173D-4859-89FD-17BE14EA647D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4b62b510f997cfb66307a6873f8bf04b4c3541cf","datavalue":{"value":{"entity-type":"item","numeric-id":230893,"id":"Q230893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$D286158B-368D-40C8-A2CD-E4401720C7A7","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":"Q1065930$3CC12BBB-0B39-49DB-9110-D2CA4593C83A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"06be7e9ed8aea6519e094e068bd497a36e007926","datavalue":{"value":"https://doi.org/10.1016/0022-4049(86)90136-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1065930$E8BC62FF-39B5-4BFA-8899-DB59F9A4BF8B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bfff76505f3de33084e41c4ca523630c197b25e0","datavalue":{"value":"W3023099848","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065930$A682635C-982F-48AF-A311-8288713BBEF9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"04e8e937b1b32025caa939605544fee074106255","datavalue":{"value":{"entity-type":"item","numeric-id":3855376,"id":"Q3855376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$BCD552D5-6AE2-4E45-B4D1-F115F3A060A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30406a924143b929a74b0774dabe759659101528","datavalue":{"value":{"entity-type":"item","numeric-id":4773877,"id":"Q4773877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$6707B115-E00C-4B2F-934D-25C70F98E4AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea45dec13896b056b844b564cf651b6176c78a75","datavalue":{"value":{"entity-type":"item","numeric-id":1240777,"id":"Q1240777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$99F552AF-64F7-45E7-8427-C1941EFEA1F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f1d37aa9f5859a63c9cbf5d6d550accb00225fe","datavalue":{"value":{"entity-type":"item","numeric-id":1067006,"id":"Q1067006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$9913818B-3F1C-4D90-B7BF-28480E583B9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce3eeb4715ec42d210883331201f6a9086787f49","datavalue":{"value":{"entity-type":"item","numeric-id":1118677,"id":"Q1118677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$88E9071F-C038-4A12-B578-701E0D4C0AE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"155e720be9d096a6a506446d7570fc55a0d94bfd","datavalue":{"value":{"entity-type":"item","numeric-id":3944763,"id":"Q3944763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$8B98A93F-2319-4B02-9758-2F3A4BA59783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3ab60de02740591c97b8bdf852f853d690edd5f","datavalue":{"value":{"entity-type":"item","numeric-id":1054819,"id":"Q1054819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$9F24CB07-9D03-41CC-A593-5441205B89FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68ee5e3ccb9df347fdb38d61109351ad2ffac26d","datavalue":{"value":{"entity-type":"item","numeric-id":5596230,"id":"Q5596230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$9E2AC629-CA56-4EF3-8684-B1F61C6CC85F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1b26bdc210a3d291b796088837bddd84cce8b4c","datavalue":{"value":{"entity-type":"item","numeric-id":775202,"id":"Q775202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065930$B1B855AC-8D05-48E2-9473-07533D6A9E4B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00c36c39750fe90a6488dd0a0bfe61201b65730a","datavalue":{"value":{"entity-type":"item","numeric-id":3342745,"id":"Q3342745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08f38f8807e4f186b69144373078c246ac4432e1","datavalue":{"value":{"amount":"+0.902945637702942","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":"Q1065930$9227FCDC-57F5-471A-B7B5-F19676AAD525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1980a446ab874701721784245cd8d678c16163b3","datavalue":{"value":{"entity-type":"item","numeric-id":1067006,"id":"Q1067006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03809f309aa42d9770c36d990a2f6c8c6a982849","datavalue":{"value":{"amount":"+0.8966718316078186","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":"Q1065930$BC703383-039C-4E81-BE89-3F746DDC9BF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c213e1b7def02556dad68a65336502509583838f","datavalue":{"value":{"entity-type":"item","numeric-id":1118677,"id":"Q1118677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a8b67c96d89049f21429efd30330a7c6cfeda30","datavalue":{"value":{"amount":"+0.889949381351471","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":"Q1065930$570373C0-2D15-4D2C-A34B-2A2F09B0C9C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"549d0c38deb23374c50b697a974a09d6b71286bc","datavalue":{"value":{"entity-type":"item","numeric-id":3033961,"id":"Q3033961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"815850d1531b7b43b409e9298626e080167980b0","datavalue":{"value":{"amount":"+0.841841995716095","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":"Q1065930$7E268D92-FCE8-4A11-A31E-E452FF771400","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2acbed6eee77044cc8c3c4f7e21aa62ae694cc3f","datavalue":{"value":{"entity-type":"item","numeric-id":3218300,"id":"Q3218300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b42e45fc43bf1cdf4f475dd7af6f3093b68a5638","datavalue":{"value":{"amount":"+0.8297883868217468","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":"Q1065930$4B0A0F98-261E-4D91-B0DA-F0E4C7DB8F93","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I","badges":[]}}}}}