Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I (Q1065930): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0022-4049(86)90136-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3023099848 / rank | |||
Normal rank |
Revision as of 19:40, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I |
scientific article |
Statements
Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I (English)
0 references
1986
0 references
\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.
0 references
finitely presented group
0 references
insoluble word problem
0 references
Kharlampovich's theorem
0 references
algorithmic problems
0 references
soluble groups
0 references
isomorphism problem
0 references
recursive set
0 references
central words
0 references