Hi. I'll confess from the start to not being a logician. In fact this question came up not from research but during a discussion with a friend about whether the classical proof that $\sqrt{2}$ is irrational can be made acceptable to an intuitionist. (It can be.)


The question is: *Are there any "natural" statements which can be proven in [Peano Arithmetic](http://en.wikipedia.org/wiki/Peano_axioms), but not in [Heyting Arithmetic](http://en.wikipedia.org/wiki/Heyting_arithmetic) (Peano Arithmetic but with a logic that does not admit the law of the excluded middle)?* 


In fact, any statements -- even pathological ones -- that can be proven in one but not the other would be interesting to me, since I wasn't able to come up with any. (Even after doing a few web searches!) But of course, the closer to the surface the better.



What can be proven in Peano arithmetic but not Heyting arithmetic?
The first example that occurs to me is (a formalization in the language of arithmetic, via coding, of) "For every Turing machine M and every input x, the computation of M on input x either terminates or doesn't terminate." With classical logic, this is trivially provable, as an instance of the law of the excluded middle. But it's not intuitionistically provable because the halting problem is undecidable. (In a bit more detail, if it were provable, then it would be recursively realizable, and the realizer would be an index for an algorithm that solves the halting problem.)


