12
$\begingroup$

Is there a basic arithmetic statement which is known to be undecidable ?

By basic arithmetic statement I do mean an easy statement in the spirit of the Collatz conjecture . By the way is there some reasons to believe that the Collatz conjecture is undecidable ?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Please, if you down vote do tell the reason, May be I can ameliorate my question :-) thanks. $\endgroup$
    – Ofra
    Commented Oct 31, 2017 at 21:29
  • 9
    $\begingroup$ In at least one precise sense of "easy", namely quantifier complexity, Gödel's original examples were easier than the Collatz conjecture. $\endgroup$
    – Andreas Blass
    Commented Oct 31, 2017 at 21:34
  • 7
    $\begingroup$ The question would be better if you indicated (1) undecidable from what axioms? (e.g., Peano arithmetic, Zermelo-Fraenkel set theory, or what) and (2) a criterion for "easy" that doesn't depend on discerning "the spirit of" a mathematical statement. $\endgroup$
    – Andreas Blass
    Commented Oct 31, 2017 at 21:41
  • 4
    $\begingroup$ In my previous comment, I should also have mentioned (3) a more precise description of "some reasons". If I take that phrase literally, then the failure (until now) of a lot of smart people to prove or refute the Collatz conjecture could qualify as some reason to believe it's undecidable (in ZF). But I suspect that's not what you intended. $\endgroup$
    – Andreas Blass
    Commented Oct 31, 2017 at 21:43
  • 2
    $\begingroup$ @Adreas Blass (1) I'm considering ZF. (2) I think your comment is as subjective as mine :-). (3) What you mentioned is one reason I was thinking about but it is not enough. I was wondering if there is a mathematical reason to believe that the conjecture is undecidable. $\endgroup$
    – Ofra
    Commented Oct 31, 2017 at 21:55

3 Answers 3

Reset to default
15
$\begingroup$

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
1Conway, John H. "On unsettleable arithmetical problems." American Mathematical Monthly 120.3 (2013): 192-198. (Jstor link.) Reprinted in the Best Writing on Mathematics 2014.

Improve this answer
$\endgroup$
15
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ In relation to the other comments here that such a question may only be undecidable "in a given system"; is there some system in which this statement is true? $\endgroup$
    – Robert Frost
    Commented Nov 10, 2017 at 9:39
  • $\begingroup$ Can you elaborate on what you mean by a system? Maybe your question should be in a mathoverflow post of its own. $\endgroup$
    – Dominic van der Zypen
    Commented Nov 10, 2017 at 9:46
  • 1
    $\begingroup$ I refer to the meaning used by Lucas K in his answer below and in the comments on the question. I presume they're referring to the set of axioms from which the conclusion is deducible e.g. Peano, ZF, ZFC etc. I believe a logician will argue every statement is decidable in some system. $\endgroup$
    – Robert Frost
    Commented Nov 10, 2017 at 9:50
  • 2
    $\begingroup$ @RobertFrost technically there is, since you can just add an axiom deciding it $\endgroup$
    – Christopher King
    Commented Nov 11, 2017 at 20:09
  • 1
    $\begingroup$ @PyRulez I was going to reply to Dominic; but thought better of it;..."a logician would probably answer such a question with; the machine which immediately halts for any input, decides the problem. So you would need to specify a consistent system which models arithmetic, or something similar..." but I didn't want to get started in a field I know insufficient about. $\endgroup$
    – Robert Frost
    Commented Nov 12, 2017 at 17:43
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ It seems that one could say, more precisely, that termination of the Ackermann function corresponds to the ordinal $\omega^2$, since the nested recursion has that order type. $\endgroup$
    – Joel David Hamkins
    Commented Nov 8, 2017 at 0:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .