Undecidable easy arithmetical statement

Ofra: "is there some reasons to believe that the Collatz conjecture is undecidable?" There is reason to believe a generalized version is undecidable. This was explored by John Conway in "On Unsettleable Arithmetical Problems."¹ And this paper proves a version recursively undecidable:

Kurtz, Stuart A., and Janos Simon. "The undecidability of the generalized Collatz problem." International Conference on Theory and Applications of Models of Computation. Springer, Berlin, Heidelberg, 2007. (Springer link.)

Abstract. The Collatz problem, widely known as the $3x + 1$ problem, asks whether or not a certain simple iterative process halts on all inputs. We build on earlier work by J. H. Conway, and show that a natural generalization of the Collatz problem is $\Pi^0_2$ complete.

Here is their generalization:

---

         

---

¹Conway, John H. "On unsettleable arithmetical problems." American Mathematical Monthly 120.3 (2013): 192-198. (Jstor link.) Reprinted in the Best Writing on Mathematics 2014.

The "mortal matrix" problem: Given a set of $n\times n$-matrices with integer entries, decide whether they can be multiplied, in any order and possibly with repetition, to give the $0$-matrix. If I remember correctly, it is already undecidable for $n\geq 3$.

I decided to put this here, since matrix multiplication is a sequence of simple arithmetical operations.

To talk about undecidability, you have to specify the system.

I consider the simplest system in which you can do real mathematics a system with proof strength $I\Sigma_1$ (feel free to disagree).

In such system the termination of the Ackermann function is undecidable. But more advanced system can easily decide it.

But it is a good example of undecidability in practice. It also shows the relation between ordinals and undecidability. The Ackermann function is related to the first infinte ordinals.