Do Gödel's theorems imply that intelligence systems may end up in some undecidable situation (that may make them take a wrong decision)? [closed]

Question

So far I understand - I know very little on the topic - the core of AI boils down to design algorithms that shall provide a TRUE/FALSE answer to a given statement. Nevertheless, I am aware of the limitations provided by the Gödel's incomplete theorems but I am also aware that there have been long debates such as the Lucas and Penrose arguments with all the consequent objections during the past 60 years.

The conclusion is, in my understanding, that to create AI systems we must accept incompleteness or inconsistency.

Does that mean that intelligence systems (including artificial ones), like humans, may end up in some undecidable situation that may lead to take a wrong decision?

If this may be acceptable in some application (for example, if every once in a while a spam email ends up in the inbox folder - or vice versa - despite an AI-based anti-spam filter) in some other application it may not. I am referring to real-time critical applications when a "wrong" action from a machine may harm people.

Does that mean that AI will never be employed for real-time critical applications?

Would in that case more safe to use deterministic methods that do not leave room for any kind of undecidability?

Answer 1

^{Your question is mostly philosophical, not technical or scientific. So I am giving opinions and references here.}

the core of AI boils down to design algorithms

I am noticing that you are not even try to define AI (whose definition changed since the previous century). You could look at the table of contents of the Artificial Intelligence journal and notice how topics covered there changed drastically in a few decades (even experimental approaches have declined).

You might be interested in reading more about AGI and follow the few conferences about it. Beware, there is a lot of too much simplified approaches, and even a lot of bullshit (e.g. on this AGI mailing list, but some messages there are gems)

I assume you accept the Church-Turing philosophical thesis: every intelligent cognition (either natural i.e. biological or artificial) is some symbolic computation. In particular, the work of a mathematician can be abstracted as a Turing machine (that was the major insight of Turing and in the halting problem). Be also aware of the related Curry-Howard correspondence and Rice's theorem. Read Gödel, Escher, Bach !

We don't know yet how to make AGI. You could read Bostrom's SuperIntelligence book about potential dangers. You could also read J.Pitrat's book Artificial Beings (which gives much more positive and constructive insights about eventually making some AGI) and blog.

My personal belief (just an opinion) is that AGI could be perhaps achieved (in many dozens of years), should be definitely get much more funding -and more time- as a research topic (e.g. as much as the ITER reactor; see also softwareheritage.org and the motivations there), but won't be achieved by any single technique, but by a clever combination of many AI techniques (both symbolic AI -e.g. for planning- and machine learning or connectionnist approaches, with inspiration from cognitive psychology).

The conclusion is, in my understanding, that to create AI systems we must accept incompleteness or inconsistency.

We, members of the Homo Sapiens Sapiens species (in latin, the humans who know that they know, so capable of metaknowledge), claim to be intelligent. But all of us have a globally incomplete and inconsistent behavior, because each of us have contradictions (e.g. in our personal lives or ethical beliefs). So, logically speaking, incompleteness or inconsistency is not opposed to intelligence. Read also more about situated AI and machine ethics. BTW, I believe (since educated by J.Pitrat about this) that explicit and declarative metaknowledge is required in any AGI system.

Does that mean that AI will never be employed for real-time critical applications?

Notice that autonomous killing robots are already a controversial research topic today. Autonomous robots already exist (e.g. Mars rovers cannot be teleoperated -for every elementary movement- from Earth, because any radio signal takes minutes to reach Mars). And autonomous vehicles (à la Google car) claim today to use AI techniques and are real-time safety-critical systems. Today's Airbus or Boeing (cf DO-178C) are flying automatically most of the time. Cruise missiles and ICBMs are fire-and-forget devices. Many high-frequency trading systems claim to use AI techniques and are real-time.

PS. Notice that what was called AI in the previous century is today called AGI. My PhD in AI was defended in 1990 (and was about explicit metaknowledge for metaprogramming goals, see e.g. this old 1987 paper)

Answer 2

Your initial statement on the core of AI is rather limited. In general, AI is concerned with modeling human behaviour either by imitation (soft AI) or by replicating the way human cognition works (hard AI). So far there have been some successes with soft AI, as computers can perform tasks that required some "intelligence", though the degree of this intelligence is questionable. This is partly due to the fact that even we as humans don't really have a clear idea what it means for a computer to "understand" something.

But your conclusion is correct: if we build an AI system with human characteristics, then it will make mistakes, just as humans make mistakes. And any system designed by humans (or machines!) will make mistakes. However, not being able to deal with an imperfect world is not really relevant to AI alone: even systems that do not use AI methods will have to face that, and whether a system is suitable for real-time critical applications has got nothing to do with whether it is based on AI or not.

UPDATE: There seem to be two distinct issues at play here: decidability and real-time processing.

1. Real-time computing (RTC): This is not really related to AI. Even ordinary programmes written in Java are not really safe for RTC, as they could start a garbage collection cycle at any time which pauses execution of the program. Just imagine a reactor core starts overheating just as your controller runs out of memory and garbage collection kicks in, halting the program for a few minutes. If you implement AI methods in RTC-safe systems, that should not be an issue.

2. Decidability: Your reasoning is that AI systems attempt to mirror human cognition, thus incorporating the ability to make mistakes. This is a more philosophical issue — if a human can control a system, then an AI system with the same capabilities should be able to do it too. This assumes that we are able to replicate human behaviour (which we are not). There are AI methods which are deterministic, so would come to the same conclusions given identical environments. So I would say that they would not perform worse than non-AI methods. It partly depends what you want to call AI; the distinction between traditional AI and statistical methods keeps getting blurred at present.

To conclude: No, AI methods should be suitable, as they can also be deterministic. It depends on the actual application and method if they are. And, of course, on what you count as AI.

Answer 3

Artificial intelligence cannot be boiled down to designing algorithms, binary or otherwise, simply because the exhibition of intelligence in biological systems predated the invention of algorithmic computing. From this, we can further draw the conclusion that algorithms are not a necessary component of systems that exhibit behavior we deem intelligent.

A decision was made, per the recommendation of John von Neumann, to increase reliability of computing machinery by delegating to a single binary central processing unit all computation. This choice and the prior work upon which it was based (Shannon, Church, and Turing) led to the preeminence of algorithm specification in computer languages. The foundation of expressing functional design in algorithmic terms was laid and the software industry was born.

Since that time, there has existed a parallel trend in research back toward the biological inspiration of computing machinery and, more specifically, parallel processing. We see this at several levels.

• Movement of floating point arithmetic, video rendering, and machine learning bottlenecks to dedicated VLSI hardware acceleration
• Multiple core VLSI processors
• Computing clusters and processing frameworks, containers, and environments that expose interfaces through which compiler and kernel programmers can control parallel machinery explicitly or implicitly
• Multiple thread and processes delegated to multiple cores, agents, or hosts in computing clusters
• Sophisticated VLSI level caching to maximize the efficiency of parallel operations
• Language and compiler features to support the trends toward deployment to multiprocessing environments, such as declarative languages for Big Data platforms (ECL for example)
• Development of AI chip designs that completely or partially shift the computing paradigm to prior to the emergence of the CPU in some ways, returning to considerable parallelism and departing from centralized processing (yet capitalizing on lessons learned in computer vision, cognitive science, reverse engineering of brain genetics, mental signal tracing, the use of gradient descent with back propagation, reinforcement designs, and applied robotics) — This is likely a major research direction for the 2020s.

Some believe that an implication of Gödel's two incompleteness theorems is that the human mind does not meet the criteria of a computing machine as Turing defined one, but these are largely tangential issues.

It is true that The working out of a proof that RNNs of sufficient resolution, depth, and width can be trained to be equivalent to any Turing Machine by Hava Siegelmann. It is true that her work is considered support for Marvin Minski's bold assertion that the human brain is a meat machine. However, the work on determinism by John Lucas and Roger Penrose's The Emperor's New Mind are not refutations of either of Gödel's theorems. They are refutations of what some thought were consequences Gödel's theorems and some of the implications of Minski's declaration.

Gödel clearly explains his intentions in the early portion of the paper presenting the theorems, and they had nothing to do with computing. He intended to and succeeded in proving that theorems within a concrete mathematical system not always be proven even if they are true. Gödel's work placed unwanted doubt on the initiative to prove all remaining unproven mathematical theorems. Mathematicians naturally tended to think of mathematics as the perfect human endeavor, and a legitimate proof of incongruity between what is true and what is provable seemed an imperfect irritation.

Perhaps the most profound response to Gödel's incompleteness theorems came from Alan Turing, who likely deliberately placed the word Completeness in the name of his theorem. But this was not a refutation either. He worked around incompleteness by defining a class of mathematical operations and finite data structures upon which they can operate that he could prove could be complete. Upon doing so, he put into place an important portion of the basis for algorithm development.

Nonetheless, it is probably wise for present day AI researchers to accept both incompleteness and inconsistency and realize that intelligence, artificial or not, is likely fallible after any finite degree of learning. This is likely because one cannot provide an infinite range of problem types to a learning system in a finite amount of time. There may always be at least one problem that the current state of learning cannot address. The practical colloquialism for this condition of partial knowledge is, "We don't know what we don't know."

Furthermore, a clear implication of the work of Gödel is that no proof may be found for some things that are true, ever, by any type of intelligence. Similarly, we cannot be sure that the most intelligent searching for a counter example to dispute a false assertion may end in finding one, ever. The PAC Learning framework addresses categories of problems that are solvable or not from a mathematical perspective and is worthy of study.

Lastly, but perhaps most profoundly, it is not clear that a type of intelligence exists that can learn anything, as opposed to be programmed to accomplish anything. Said another way, general intelligence may be an ideal conception never achieved but possibly approached. What may seem like super intelligence in one environment and during one specific time period may be entirely ineffective or even counter-intelligent and problematic in another environment or during a different time period.

This cannot be stressed too much, with so many statements about AI being made in the guise of science that have no origin in scientific rigor.

Nonetheless, even with these likely limitations on both AI and human intelligence, one cannot conclude that AI will be ineffective in real time critical applications. One cannot conclude that AI will be less effective than human intelligence in any particular domain either.

It is actually difficult to conclude anything about intelligence at all, without defining it formally and reaching a consensus in that definition, which continues to escape us. We can see that in the absence of this formality, mail industry from continuing to sort mail automatically. The automotive industry continues to pursue the invention of better artificial drivers than the average human driver. The game industry implements artificial opponents that have to deliberately make mistakes to let people win in an otherwise fair, real time game.

Clearly AI is evolving faster than the DNA components that affect the human brain.

People are less startled today than they would have been ten years ago by the proposition that, some time during this century, driving a car will be illegal in some jurisdictions, when the human and property loss statistics prove automated drivers to be substantially safer than nearly all manual ones. The bar for driving safety set by humans is not very high, with day dreaming, texting, occasional tiredness or inebriation slowing an already insufficient reaction time for many street events.

If the driving computing agent panics because there is determines the trajectory of a dog, a child, and an elderly person is intersecting with the car's trajectory, it may resolve the panic and plot a safe course in a millisecond (perhaps avoiding all three or perhaps sacrificing the dog to save the two people), whereas the human may resolve the panic only after hitting some one.

In summary, it is not infallibility that determines the proper balance or volume of AI deployment but the comparison of the distribution of human performances compared with the distribution found with the machine replacements under similar conditions.