Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I (Q1065930): Difference between revisions

\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.