Markov's theorem and algorithmically non-recognizable combinatorial manifolds

DOI10.1070/IM2004V068N01ABEH000471MaRDI QIDQ4674631zbMATH OpenOpenAlexFDO

Authors M. A. Shtan'ko

Publication date 17 May 2005

Published in Izvestiya: Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1070/im2004v068n01abeh000471

zbMATH Keywords

algorithmically non-recognizable manifoldcombinatorial manifoldhandle theoryinsoluble word problemregular neighborhood

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Polyhedral manifolds (52B70) Comparison of PL-structures: classification, Hauptvermutung (57Q25) Regular neighborhoods in PL-topology (57Q40)

Review text

In 1958, \textit{A. Markov} stated the algorithmic insolubility of the combinatorial homeomorphism problem in dimension greater than three [Dokl. Akad. Nauk SSSR 121, 218--220 (1958; Zbl 0092.00702)]. A more complete proof, involving logic and algorithm theory, was obtained by \textit{W. W. Boone, W. Haken} and \textit{V. Poenaru} [Contrib. Math. Logic, Proc. Logic Colloq., Hannover 1966, 37--74 (1968; Zbl 0246.57015)]. The aim of the present paper is to give a comprehensive proof of Markov's theorem in the PL-category, by making use of combinatorial methods concerning regular neighborhoods and handle theory. A PL manifold which is algorithmically non-recognizable is concretely constructed, for each \(n \geq 4\), starting from \textit{V. V. Borisov}'s example of a group with insoluble word problem [see Math. Notes 6, 768--775 (1969; Zbl 0215.10803)] and making use of the Adian-Rabin Theorem [see \textit{S. I. Adyan} and \textit{V. G. Durnev}, Russ. Math. Surv. 55, No. 2, 207--296 (2000; Zbl 0958.20029) and \textit{M. O. Rabin}, Ann. Math. (2) 67, 172--194 (1958; Zbl 0079.24802)].

Recommendations

• On the Markov theorem on algorithmic nonrecognizability of manifolds
• Unrecognizability of manifolds
• Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization
• scientific article; zbMATH DE number 1342334
• scientific article; zbMATH DE number 1133271

Cited in

(11)

• Recognizing free generating sets of \(\ell\)-groups
• Fans, decision problems and generators of free abelian \(\ell\)-groups
• Complete and computable orbit invariants in the geometry of the affine group over the integers
• Balanced presentations of the trivial group and four-dimensional geometry
• Idempotent endomorphisms of free MV-algebras and unital -groups
• scientific article; zbMATH DE number 1342334 (Why is no real title available?)
• Questions in algebra and mathematical logic. Scientific heritage of S. I. Adian
• Computing on Lattice-Ordered Abelian Groups
• On the homeomorphism problem for 4-manifolds
• A Geometric Approach to MV-Algebras
• On the Markov theorem on algorithmic nonrecognizability of manifolds

This page was built for publication: Markov's theorem and algorithmically non-recognizable combinatorial manifolds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4674631)