Comment by tensor | Hacker News Reader

Comment by tensor | Hacker News Reader

Parent Full thread

> Yes there are many problems that in general are impossible or intractable for computers, yet humans solve instances of these problems with ease.

Can you provide examples? Generally when we say a problem is intractable in CS we are talking about solving it for every instance, not just a particular instance.

For example, the halting problem is "given an arbitrary program, can you determine if it will halt?" I see no reason believe that a human can determine if any arbitrary program will halt. In fact, it's trivial to come up with examples of programs that are so large that there is no way for a human to remotely comprehend what they do, let alone say if it will halt.

So what are these intractable problems that humans can solve with ease?

Example: recognizing and picking up objects, with grace and agility. Simply calculating the rotational angles required on limbs with multiple (>8) joints is intractable for a computer, yet we do it all the time.

Another example: writing new sorting algorithms. Writing a program to do a well defined task.

You can come up with examples where it's infeasible for a programmer to decide halting, but that's not the same thing, because feasibility is just about the amount of time or resources it would take to do something. One can imagine giving an arbitrarily difficult program to an arbitrarily bored programmer, and having an answer to whether it'll halt after ten years. But that's pure thought experiment, because nobody would ever actually do it, because it wouldn't be worth doing.

That is, the undecidability of the halting problem hinges on the need to specify a mechanical/formal process for making the decision, which cannot be done.

Sure, just limit the types of programs to those that could be understood by an average programmer within 8 hours. This way, a human could solve the halting problem for a limited domain of programs, but there is still no general algorithm which would be able to make the same determination.

The main intractable problem is recognizing and solving the tractable instances. If computers could do this in the general case as well as humans, then we'd not need humans.

Reply on news.ycombinator.com