Skip to main content
Snapshot of their definition.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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."1 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:


          [![GenCollatz][1]][1]
1Conway, John H. "On unsettleable arithmetical problems." *American Mathematical Monthly* 120.3 (2013): 192-198. ([Jstor link](https://www.jstor.org/stable/10.4169/amer.math.monthly.120.03.192?seq=1#page_scan_tab_contents).) Reprinted in the *Best Writing on Mathematics 2014*.

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."1 And this paper proves a version 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.


1Conway, John H. "On unsettleable arithmetical problems." *American Mathematical Monthly* 120.3 (2013): 192-198. ([Jstor link](https://www.jstor.org/stable/10.4169/amer.math.monthly.120.03.192?seq=1#page_scan_tab_contents).) Reprinted in the *Best Writing on Mathematics 2014*.

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."1 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:


          [![GenCollatz][1]][1]
1Conway, John H. "On unsettleable arithmetical problems." *American Mathematical Monthly* 120.3 (2013): 192-198. ([Jstor link](https://www.jstor.org/stable/10.4169/amer.math.monthly.120.03.192?seq=1#page_scan_tab_contents).) Reprinted in the *Best Writing on Mathematics 2014*.
Added links to the two cited papers. Published abstract slightly different.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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."1 And this paper proves a version 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 recursively undecidable$\Pi^0_2$ complete.


1Conway, John H. "On unsettleable arithmetical problems." *American Mathematical Monthly* 120.3 (2013): 192-198. ([Jstor link](https://www.jstor.org/stable/10.4169/amer.math.monthly.120.03.192?seq=1#page_scan_tab_contents).) Reprinted in the *Best Writing on Mathematics 2014*.

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."1 And this paper proves a version 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.

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 recursively undecidable.


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

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."1 And this paper proves a version 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.


1Conway, John H. "On unsettleable arithmetical problems." *American Mathematical Monthly* 120.3 (2013): 192-198. ([Jstor link](https://www.jstor.org/stable/10.4169/amer.math.monthly.120.03.192?seq=1#page_scan_tab_contents).) Reprinted in the *Best Writing on Mathematics 2014*.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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."1 And this paper proves a version 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.

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 recursively undecidable.


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