Hacker News Reader

Comment by colorint | Hacker News Reader

Do you believe that artificial intelligence will be capable of deciding, given an algorithm and a set of inputs, whether the algorithm will finish running?

View on HN

Here's a way of thinking about the undecidability of the halting problem. Let's say you've got a person who's amazing at reading minds, and you bring someone off the street and tell them they can either have steak or a cupcake (but not both). You then ask the mindreader to decide if the person will have the cupcake or the steak. Conceivably, they might be able to figure out which one the person will have. Now let's say that you add a twist: you walk up to the person from the street and tell them what the mindreader predicted; in that case, the mindreader can't succeed because the subject can choose to do the opposite. That's similar to how the undecidability proof of the halting problem works.

Now instead of a mindreader, we have a halting oracle, and to make its job impossible we have a test program that is "made aware" of the halting oracle, and does the opposite of what the oracle says. Impossible problem for the oracle. But that then begs the question, how many potential applications of the halting problem will involve test subjects that actually know what the halting oracle thinks? How many test subjects even know about the halting oracle? For instance, how can a program that looks for counterexamples to the Goldbach conjecture know anything about your halting oracle? In these cases, the undecidability proof doesn't apply.

So the answer to your question is conceivably yes.

Yes, that was Turing's proof. Church's more indirect proof is that it's impossible to prove the equivalence of two lambda expressions. But the real essence of the problem is more like, you can't generally know ahead of time all the values that will be presented inside loop bodies. If you try to actually elaborate the loop then you get caught again: if the elaboration of the loop keeps going on for a while, the problem is re-presented, at what point do you give up? Which is to say, will this program, with these inputs, run forever? But this is basically Church's proof, since this is also the question, am I in exactly the same configuration as before? Without an ability to decide lambda expression equivalence, that question is also hopeless.

Hence the work that gets done in this area constrains the problem down to situations in which you can know enough to decide halting, like traversal of lists or trees that are known to be finite. I bring this up because, when it comes to AI, people want more than this.

Do you believe that human intelligence, given an algorithm and a set of inputs, is capable of deciding whether the algorithm halts or not?

No, the halting problem is undecidable.

Yes, so given this, do you (i.e., people optimistic about AI) believe that computer programs will be able to generate meaningful, novel computer programs, given that even the most cursory subproblem is impossible? Obviously I don't just mean metaprogramming, but the sorts of things people want artificial intelligence to be able to do, the singularity and so forth.

Lol. Ok so you are taking this halting thing and think that it means generally that no computer program can predict what a computer program will do, and therefore that proves that we will never have computers writing programs, and therefore never have general intelligence. You are really misinterpreting that stuff and not thinking it through.

For starters take a look at the field of program synthesis. It's not AGI but it demonstrates the first thing you misunderstood.

It turns out that the problem of deciding whether a predicate is universally valid in an axiomatic system is also undecidable (and, appropriately enough, called the decision problem). That is to say, declarative systems "corresponding to" general computation are also undecidable. Which isn't really surprising, since logical recurrence is isomorphic to functional recursion. Hence also why the examples I could readily find of program synthesis are decidable problems, like deciding the maximum of two numbers or deciding membership in a list.

Our brains and NNs don't work like that and don't need to decide things that are undecidable.

> the examples I could readily find of program synthesis are decidable problems, like deciding the maximum of two numbers or deciding membership in a list.

Can you find examples of human program synthesis for undecidable problems?

> do you believe that computer programs will be able to generate meaningful, novel computer programs

Yes. There's a whole field dedicated to this called program synthesis. The undecidability of the halting problem does not preclude program synthesis.

> given that even the most cursory subproblem is impossible

What makes you think the halting problem is a 'cursory subproblem'?

Moreover, what makes you think humans can solve the halting problem?

Reply on news.ycombinator.com