3 ms·

I assume you're asking because the "non-constructive" proof of the halting problem's undecidability is unsatisfying and you want a concrete example. Another wa

I assume you're asking because the "non-constructive" proof of the halting problem's undecidability is unsatisfying and you want a concrete example. Another way to approach the problem is to talk about the reals and the naturals: the cardinality of the reals is greater than the cardinality of the naturals. Turing machines are encoded in binary, hence the set of Turing machines is no larger than the set of natural numbers. Hence there are some reals that cannot be computed by a Turing machine. This suggests an obvious example: write a program to compute the square root of a number with infinite precision. Then let it run. For any input, can you tell me whether it's stuck trying to compute an irrational number, or just taking a long time to compute a very large rational number?

pjungwir 12y ago
Actually I'm asking because I'm curious whether the mind has the same limitations as a Turing machine. I really like the simplicity of your example, but it seems like it only works if you can't see the source code. If you see the source code---which is what you'd allow to any Turing machine---why couldn't you figure this out very easily?
- capitalsigma 12y ago
  No, it doesn't matter how you implement square root. If you were able to tell me whether any execution of the program halts, then you would be able to tell me, for any `n`, whether or not `n` is irrational (since irrational results are exactly the results that it won't halt on). But this isn't possible: it's an open problem whether or not `pi + e` [is irrational](http://math.stackexchange.com/questions/28243/is-there-a-proof-that-pi-times-e-is-irrational http://math.stackexchange.com/questions/28243/is-there-a-pro...). So if you could always tell me when the square root program halted, you'd be able to tell me whether or not it halted for `(pi + e)^2`. But if you were able to tell me that, you would have solved an open problem in number theory along the way -- you'd have solved a whole class of open problems about whether or not certain expressions are rational. I can't prove to you that no solution of this kind exists, but, intuitively, do you see how big the implications would be if you could solve the halting problem for your square root machine?
  - pjungwir 12y ago
    Ah, thanks for clarifying! I think I overlooked the "square root" part of your original response. You're right, seeing the source code is no help at all! And it's difficult to say that a human could always say if sqrt(x) is rational, for all x. Still, this seems a bit like the Goldbach conjecture example: we don't have a math proof for this now, but some day we might. I wonder if there is any program that is provably undecidable---like the way Godel's theorem proves that some statements are undecidable from their axioms.

pjungwir 12y ago

Actually I'm asking because I'm curious whether the mind has the same limitations as a Turing machine. I really like the simplicity of your example, but it seems like it only works if you can't see the source code. If you see the source code---which is what you'd allow to any Turing machine---why couldn't you figure this out very easily?

capitalsigma 12y ago
No, it doesn't matter how you implement square root. If you were able to tell me whether any execution of the program halts, then you would be able to tell me, for any `n`, whether or not `n` is irrational (since irrational results are exactly the results that it won't halt on). But this isn't possible: it's an open problem whether or not `pi + e` [is irrational](http://math.stackexchange.com/questions/28243/is-there-a-proof-that-pi-times-e-is-irrational http://math.stackexchange.com/questions/28243/is-there-a-pro...). So if you could always tell me when the square root program halted, you'd be able to tell me whether or not it halted for `(pi + e)^2`. But if you were able to tell me that, you would have solved an open problem in number theory along the way -- you'd have solved a whole class of open problems about whether or not certain expressions are rational. I can't prove to you that no solution of this kind exists, but, intuitively, do you see how big the implications would be if you could solve the halting problem for your square root machine?
- pjungwir 12y ago
  Ah, thanks for clarifying! I think I overlooked the "square root" part of your original response. You're right, seeing the source code is no help at all! And it's difficult to say that a human could always say if sqrt(x) is rational, for all x. Still, this seems a bit like the Goldbach conjecture example: we don't have a math proof for this now, but some day we might. I wonder if there is any program that is provably undecidable---like the way Godel's theorem proves that some statements are undecidable from their axioms.