So far, no mathematical theory has generated so much interest and outrage as Godel’s theorem. After Turing machines, mathematicians and non-mathematicians have poured in substantive amount of time and research over Godel’s paper, that proposes the human mind is like a formal system. Kurt Godel 1930s Godel’s Incompleteness Theorem stirred up a conversation about the implication of the result on artificial intelligence (AI) and its future.
Mathematicians and computer scientists all agree that Gödel’s Incompleteness theorem is one of the most important and impactful results in modern logic and mathematics. Kurt Godel changed the world of logic, mathematics and philosophy with his paper — an attempt to mathematise the workings of the human mind by describing them as formal system.
Inside Godel’s Incompleteness Theorem
Godel’s Incompleteness theorem says that, “all consistent axiomatic formulations of number theory include undecidable propositions.” In simpler mathematical terms, Godel’s Incompleteness Theorem says that any consistent formal system which can do even simple arithmetic is incomplete meaning there are true statements in the realm of number theory which can not be derived from the axioms of the formal system. This means that some statements even if they are true are not theorems of the formal system. There are several terminologies here like consistency, completeness, formal system and theorem which we should define to make a connection to AI and think deeply how Godel’s incompleteness theorem could implicate in Artificial intelligence.
Let us deep dive into the terminology
Formal system: A formal system is defined by a finite set of symbols and a some rules of inference. A group of symbols arranged in an order of some sort is called a string. There are some strings in the formal system which are known as axioms. The rules of inference show us a way of creating or generating theorems from these base axioms.
Theorem: A theorem is any string which can be can be derived from the axiom(s) by applying zero or more of the rules of inference in succession to the axiom(s).
Consistency: Consistency in a formal system means that every theorem [of the formal system], upon interpretation, comes out true (in some imaginable world).
Complete: A formal system is complete if for every statement of the formal system, either the statement or its negation can be derived (i.e., proved) in the system. Hence a formal system is consistent if there is no statement such that the statement itself and its negation are both derivable in the system.
The implications of Gödel’s Incompleteness Theorem came as a surprise to many experts and mathematicians. The theorems proved there are true statements that will never be proved we never know if it’s true or false.
Lucas’s Argument and Objections
On of the early connection between artificial intelligence and Godel’s Incompleteness Theorem was established by British philosopher John Lucas. He put forward his ideas in a paper titled Minds, Machines and Gödel. His idea say that many machines that are electronic or calculating (which includes computers) are an example of a formal system. The argument connects the modern machines with the Godel’s Incompleteness Theorem. He goes on to argue that cybernetic machines (like the modern computer) has finite operations and matches the definition of Godel’s formal system. All operations of computers can be represented in formulae and there are rules of inference which are given by computer algorithms.
Hence, as we go for all sequences of operations performed by machine can be reframed in a formal system and Godel’s theorems applied to it. By following up this idea and comparing the human mind to the formal system of the computer. Imagine that a human mind knows that a certain statement is true but according to Godel’s theorem the statement can not be proved inside the formal system and hence can’t be produced by the formal system as being true. Lucas concludes that machines can never match the human mind because of the limitations put forward by Godel’s Incompleteness theorem. There are also many objections to Lucas’ argument and they can be found here.
One of the strongest argument against Lucas’ argument is the Penrose Argument which goes as follows.
- Assume (for the sake of contradiction) that there is some formal system F that captures the thought processes required for mathematical insight.
- Then, according to Gödel’s theorem, F cannot prove its own consistency.
- We, as human beings, can see that F is consistent.
- Therefore, since F captures our reasoning, F could prove that F is consistent.
- This is a contradiction and, therefore, such a system F could not exist.
If a formal system F promised to frame or copy human thought, it is not always the case that today’s system can be framed as the traditional formal system. There are many problems with the Lucas’ argument particularly in the assumption that humans can see all kinds of truths.
Try deep learning using MATLAB