I don't understand how Gödel showed limits of AI, or even addressed AI in its modern incarnation, which has little to do with logic. Perhaps some more knowledgeable reader can elucidate?
If your AI uses a classical computer, then everything it's doing is reducible to the Boolean algebra of its component logic gates.
All of the training you've done on the GPU; all of the coordination done by the CPU; everything… it's all one (absurdly long) boolean expression.
Like all algebraic structures, Boolean algebra is built from an initial set of axioms. Under Gödel's incompleteness theorem, it is therefore true that if Boolean algebra isn't inherently broken (inconsistent), then we can craft questions that cannot be answered using Boolean algebra alone, but this is all your classical computer is capable of doing!
Now, if you're training AI using an analog system or a non-classical computer such as a quantum computer, then this opens up a totally different discussion.
> we can craft questions that cannot be answered using Boolean algebra alone
Sure, that's trivial, the travelling salesman problem for example can't be solved exactly, but approximative methods come very close. Given that brains are pattern recognition machines generating probabilities we're already in the approximative regime. Nothing is certain, even science has its revisions.
So does it matter if we can only approximate? For living things the main thing that matters is life, self reproduction, not exactness. As long as they reproduce they are still valid, with all imperfections and approximations. I think the only questions that matter are those related to life, there are plenty of uncomputable things outside self reproduction. This is for biological agents, an AI would be using evolutionary methods to reproduce their digital genes instead.
It's exponential, you can solve it for N=100, but not for N=1,000,000. You can't say "it just takes a lot of time" if that time is > age of the universe.
Actually, you can. There's a huge gulf between things that we know we could compute given enough time, even if that time is impossible to actually be given, and things we know can never be computed given infinite computing power.
Something like the perfect security of either hiding or binding in a commitment protocol can never be broken given computers of infinite capacity and speed because it's mathematically impossible. That is opposed to computational security, which only states that the property can't be broken within any usable time frame. This is often in the order of hundreds of millions of years in practical cryptographic systems. The point is, it can be technically be done.
Breaking RSA can factored just by brute forcing. It might take a lot of time, but actually doing it is not hard for sufficiently small keys. We just increase the key size until it takes a long time.
> You can't say "it just takes a lot of time" if that time is > age of the universe.
1. The difference matters a WHOLE LOT when you're studying computability. If the question you're trying to answer is "Can this be computed exactly?", then the distinction is paramount.
2. Your argument here is functionally equivalent to stating that there exists a largest number since it's trivial to construct a number which would require more digits (in any base you'd like) than subatomic particles in the entire universe to represent in its fully-expanded form… so let's pick this one as the largest and stop worrying about all of that infinity hub-bub!
There is a fundamental difference between "We don't know how to solve this practically since the best solution we have would take too much time." and "It is a problem without solution. It can not be solved at all not matter how you approach it, or even how an imaginary alien specie with technology beyond our understanding would approach it".
Also, the equivalence between the different models of computation for Turing completeness (turing machine, lambda calculus, ...) isn't about complexity classes of the problems, only wether or not the model allow to solve the same set of problems. For example searching in a sorted array is O(log n) on a Von Neumann machine but O(n) on a Turing machine.
Isn't his theorem proving that any mathematical system will be either incomplete or inconsistent ? And quantum computing is still a mathematical system so the same applies ?
Yes, but I didn't cite QC as an exception to the rule. I only mentioned it because it's governed by a different set of axioms and would result in a different discussion.
Without getting too technical, if AI must run on a computer, and there are
programs that computers cannot compute, then there are limits to what AI can
compute, or in other words think (because it's an AI; so to think, it
computes).
As a very crude example of this kind of limitation, I'm sure I've read a hundred
Sci-Fi stories where the humans defeat the AI by posing to it an unsolvable
problem, usually a variation of the "liar's paradox", e.g. "this statement is
false" (which btw is used by Gödel in his proof). So a human traipses over to
the superintelligent AI and blurts "I always lie". Then the AI spends an aeon
processing the sentence and then blows up.
Even worse, intelligence itself may turn out to be an uncomputable program that
cannot be executed on a computer. In that case- no AI.
The scenarios you described are not realistic. There's no AI getting stuck into a loop by a tricky question, not even GPT-3. Any solution would take into consideration its computation cost. AlphaGO for example would evaluate 50K board states per move, it won't go into a 3^361 recursion.
In general when the problem is so hard evolutionary methods are suitable. They naturally blend the notion of cost with that of search and cope better with deceptive objectives.
Your turn of phrase "there's no AI getting stuck..." has me stuck. Are you
assuming that there exist "AIs", as in artificially intelligent entities, like
the kind imagined by science fiction writers and (some) AI researchers, alike?
To clarify, there are no such systems. "AI" is the name of a research field, not
any ability that characterises a class of systems currently known.
This suffices to explain why there is, indeed "no AI getting stuck inot a loop
by a tricky question". Because there is "no AI" at all, certainly not of the
kind that can understand a "tricky question" sufficiently well to stumble on the
paradox inside it.
For example, GPT-3 has no ability to process "this sentence is false" in such a
way as to decide its truth. AlphaGo is not capable of processing language at
all, it is only capable of playing board games and it isn't even capable of
playing board games by reasoning, only by search. AlphaGo searches a game tree
structured as a directed graph, without loops so it's hard to see how it could
get stuck on recursive paradoxes anyway.
In general, such systems as exist today do not have the mathematical properties
of the formal systems described by Gödel, Church and Turing. They don't even
have memories. So they are, let's say immune to incompleteness, because they're
not even incomplete.
It's important though to note that we know of no problem so far that a human mind can solve that couldn't be solved by a Turing Machine. Godel's incompleteness theorems may very well apply to human minds as well, and so far this seems more likely than not (though a lot of human thinking is actually inconsistent, so perhaps it falls to the other side of the incomplete/inconsistent "choice" than formal systems).
Well... maybe human minds are themselves as limited as Turing machines? In that case we may never be able to create a machine that can overcome our, and Turing machines', limitations.
All of the training you've done on the GPU; all of the coordination done by the CPU; everything… it's all one (absurdly long) boolean expression.
Like all algebraic structures, Boolean algebra is built from an initial set of axioms. Under Gödel's incompleteness theorem, it is therefore true that if Boolean algebra isn't inherently broken (inconsistent), then we can craft questions that cannot be answered using Boolean algebra alone, but this is all your classical computer is capable of doing!
Now, if you're training AI using an analog system or a non-classical computer such as a quantum computer, then this opens up a totally different discussion.