The halting problem is only one example of what we would today call an RE-complete problem. Another example, which is equivalent in strength to the halting prob

The halting problem is only one example of what we would today call an RE-complete problem. Another example, which is equivalent in strength to the halting problem, is mathematical theorem proving, which is precisely the topic of this very article (as this is one way to interpret Gödel's theorems). Any algorithm powerful enough to generate a proof or refutation of an arbitrary sentence in first-order logic is equivalent in strength to one which can solve the halting problem. This general framework of thinking has often led people to declare that computers will never be able to perform automated theorem proving of arbitrary theorems, for this very reason. This very narrow analysis doesn't square well with the "real world," particularly in the 21st century, where it is widely projected that AI will eventually get, let's call it, "very good" at this kind of thing, with much fanfare about how it will design the next generation of itself and possibly turn planet Earth into grey goo in the process. These two perspectives are not really in conflict, because when we talk about an AI that is "very good" at doing math - one exponentially better than a human, which is capable of solving any problem a comparatively puny human mind is capable of coming up with, or perhaps using stochastic methods with a small but nonzero failure rate, and so on - we are talking about an infinitely lower set of goalposts than we have when we talk about the traditional halting problem. To qualify as solving that, an algorithm must be "infinitely good" at this task - it must never fail, even if the probability of doing so is exponentially small, and its failure mode can never be an infinite loop, etc - all things which we do not care about in a realistic machine learning sense. These things are really very technical statements that need to be interpreted in a very precise and careful way - they are very powerful ideas that shaped 20th century computing, but when we carelessly use them to make claims like "computers will never be able to do _______," we do them a disservice.