3 ms·

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 see

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.

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.