4 ms·
If one is willing to be that vague in drawing connections, one can reduce nearly every problem to any other one. But Turing was a mathematician, and very precis
by CaptainNegative 4y ago
If one is willing to be that vague in drawing connections, one can reduce nearly every problem to any other one. But Turing was a mathematician, and very precise with his definitions (albeit not quite as pedantic as some successors such as Aho/Ullman decades later).
The interesting bit about Turing's result is that it can be adapted to a wide class of mathematical and real objects. Physical systems? Yep. Time and/or space bounded machines? You bet. Actually, at its core Turing's result is itself an adaptation of Gödel's, who more broadly talks about the context of first-order mathematical theories.
If one want to bring these concepts to practice (where by practice I mean the realm of proving results in theoretical cs), it's a lot more effort than comparing claims to a simple sequence with an easy to derive limit. For an introductory example of the subtlety involved, while the two series (1/2 + 1/4 + 1/8 + ...) and (2 - 1/2 - 1/4 - 1/8 - ...) both approach 1 in opposite directions, most uncomputable numbers cannot be approached from both sides simultaneously (by a computably enumerable process, anyway). For example, while Chaitin's number is a definite number, you cannot write down any program whose sequence of outputs converges to it from above. They're all wrong. Comparing that to probably the most basic convergent infinite series in mathematics (that doesn't end in all zeros) is quite a disservice to the complexity and beauty of the field.
- DarkmSparks 4y agoOr, completely ignoring Zeno's paradox leaves you to believe halting problems are all impossible to solve when in practice they are generally trivial. But nice deflect, no idea why this particular topic is so rife with fud, but you keep sticking with your deadlocking programs, and I'll stick with instant reports that my code will not halt and we can both go our separate ways. thnx.