2
$\begingroup$

Alan Turing states that, there can't be a program that can decide if a program will ever stop. But with such advances in AI, won't computers will be able to analyze code and decide like humans on whether a program will halt or not.

Am I missing something in his claim?

Or is it too fictitious?

$\endgroup$
1
  • $\begingroup$ Deciding like humans is not an algorithm. It's always possible, but never guaranteed. I'd guess that nearly all of mathematics is unprovable by Turing machine, in the sense that there is no Turing machine that can prove it all, yet never prove something we know to be wrong. $\endgroup$
    – Thumbnail
    Commented Apr 20, 2017 at 2:54

2 Answers 2

6
$\begingroup$

Even if we can design better AI solving problems we did not think possible even 10 years ago, they will always be computer programs. And as you said it yourself, "Alan Turing states that, there can't be a program that can decide if a program will ever stop." (he actually proved it and not only stated it...). Thus even the best AI you can think of will not be able to decide this problem, this is uncomputable.

This is a theorem, and unless we find a new device doing computation beyond the power of Turing machine (I am not talking about faster computation, but really a new kind of computing), this will remain impossible. Even if we have whole new kind of computer defining a new concept of computation, let's call them hypercomputers, it is very likely that those hypercomputers will not be able to decide if a hypercomputer ever stops.

However, you are right in the sense that in every day life, many programs are simple enough to be analyzed and proven to terminate. Thus we can still hope to have better algorithm (using for example advances in AI), that can generate proof of terminations for a large class of programs. See for example Microsoft Terminator [1] which precisely address this problem in practice.

[1] https://en.wikipedia.org/wiki/Microsoft_Terminator

$\endgroup$
4
$\begingroup$

The proof that the decision problem doesn't have an algorithmic solution does not exempt artificial intelligence techniques, as long as they're are also algorithmic in nature.

To go beyond this boundary is a matter of speculation. Current advances in AI technology, as impressive as they may be, haven't challenged the theoretical framework we currently use.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.