Hacker News new | ask | show | jobs
by colorint 3184 days ago
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.
2 comments
ilaksh 3184 days ago
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.

link
colorint 3184 days ago
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.
link
cgmg 3183 days ago
> 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?

link
ilaksh 3184 days ago
Our brains and NNs don't work like that and don't need to decide things that are undecidable.
link
cgmg 3183 days ago
> 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?

link