Hacker News Reader

Comment by yters | Hacker News Reader

Yes there are many problems that in general are impossible or intractable for computers, yet humans solve instances of these problems with ease. In fact, it seems most problems of interest to us fall in this category of generally impossible or intractable. So, is the mind just by chance stumbling on the computationally tractable instances of these generally intractable problems, or is the mind doing something special that computers inherently cannot do? I've not seen this question addressed anywhere. Instead people assume materialism and conclude the mind is a computer, which merely begs the question. There are many more uncomputable than computable functions, so there is no a priori reason to assume the mind is a computation.

View on HN

You have to consider that computer science is soemthing we do; it is, in a sense, a way that we talk about a way that we conceptualize our own ability to solve problems. This issue only comes up because people confuse our theories about problem solving with our abilities to solve problems. Or put another way, the halting problem is disappointment about metaproblems, that we can't model the model. Even more deeply, we encounter a world in which we have these things ready-made; we come into the world with the capability to do things, but because of that, our capability comes before our understanding of our capabilities, and the whole thing becomes a jumble.

This opens up onto philosophical traditions that have mostly been obscured behind modern ideas about us being like computers, but you may want to consider something like Merleau-Ponty's The Phenomenology of Perception (or if you're really strong of heart, Husserl's Crisis of European Sciences and Transcendental Phenomenology).

Phenomenology points out important truths, but do not do so in a technically interesting way, and sometimes in language that is consistent with materialism which also doesn't help resolve anything, at least within my brief exposure to the field such as Dreyfus.

> 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?

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.

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.

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.

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.

> So, is the mind just by chance stumbling on the computationally tractable instances of these generally intractable problems, or is the mind doing something special that computers inherently cannot do?

Approximations. The mind uses approximations - for example, you can use approximate solutions that are fast and computable and still reap 99% of the benefits of a full solution.

Finding good approximation heuristics is not easier.

Reply on news.ycombinator.com