5 ms·
Every problem can be solved by breaking it up into a series of smaller problems. A good ballpark, but not entirely true. At some point you'll end up with a sm
by bluesmoon 16y ago
Every problem can be solved by breaking it up into a series of smaller problems.
A good ballpark, but not entirely true. At some point you'll end up with a smaller problem that cannot be broken up further. For the most part these may be solved problems, like `increment foo`, but at some point you might hit an unsolved atomic level problem that you either need to spend a lot of time working on, or forces you to find an alternative path.
- leif 16y agoWhen you hit a problem like that, it's time to start going in the other direction. All problems in computer science can be solved by another level of indirection.
- eru 16y agoPlease solve the halting problem with indirection. Thanks!
- Dylan16807 16y agoSure! Here's your wrapper that abstracts the concept of processes and never says 'done'.
- eru 16y agoSome computations (and most computations of practical importance) do halt eventually.
- Dylan16807 16y agoDoesn't matter, it's indirected away. All you know is that you were done asking it for data.
- eru 16y agoI don't get it.
- Dylan16807 16y agoYou have a program. It has input and output, and is either running or done. With abstraction, you can have a view of the program that is just a bidirectional data pipe. You give it information, you request information back. At some point you're done talking to it and drop the reference. The entire idea of 'halting' is gone.
- eru 16y agoNo, that doesn't work, because programs in general don't give one output bit per input bit, and they can also take a very long time to come up with their answer. E.g. input stream: stream of description of Turing machines and their input tape. Output stream: A stream of booleans that are true iff the respective machine holds.
- Dylan16807 16y agoI guess I should have addressed that idea specifically. If you transfer total control to a subprogram that directly looks for halting, you've just moved the problem, you haven't really abstracted it. Apply indirection to anything with unspecified runtime. When you need a result, put a reasonable waiting time on it, and if it doesn't happen assume the source has died and handle it as an error code.