Iteration of functions and contractibility of acyclic 2-complexes (Q2232007)

In this article, the author obtains an interesting connection between the theory of 2-dimensional complexes and the famous \(3x+1\) problem. Let \( \mathbb{N}\) be the set of positive natural numbers and \(f:\mathbb{N} \rightarrow \mathbb{N}\) be a function defined by \(f(x)=3x+1\) when \(x\) is odd, and \(f(x)=x/2\) when \(x\) is even. The Collatz conjecture states that every orbit of \(f\) contains \(1.\) A result of \textit{S. A. Kurtz} and \textit{J. Simon} [Lect. Notes Comput. Sci. 4484, 542--553 (2007; Zbl 1198.03043)] implies that there can be no algorithm to decide whether the Collatz conjecture is true or not. Let \(\mathcal{P}(f)=\langle a_{i},i\in \mathbb{N} :a_{f(i)}^{-1}a_{i}a_{f(i)}=a_{i}^{2}\rangle \) and \(P(f)\) be the presentation 2-complex. The author proves that \(P(f)\) is contractible if and only if the Collatz conjecture holds. Since \(P(f)\) is aspherical and acyclic, there can be no algorithm to decide whether an infinite, recursively described, aspherical, acyclic presentation 2-complex is contractible.