Gödel’s Incompleteness Theorems And Their Implications For Computing

G del s Incompleteness Theorems and their Implications for Computing

A mathematician David Hilbert wanted to establish Mathematics as a formal system. To achieve this he devised a set of axioms or rules that need to be followed within a system rather than relying on intuition. This was done by Euclide when he set up five axioms on which all of the Euclidean geometry is based on.

The fundamentals of a formal mathematical system are:

Consistency: no statement can be both proven and disproven in a system.

Completeness: any statement is either provable or disprovable, meaning any true statements in a system could be proved within that system.

Decidability: there is an algorithmic approach to prove or disprove any mathematical statement.

This elimination of intuition allowed mathematics to be formalized. Axioms are true statements. Proofs could be deduced based on these axioms by manipulating them. The rule of inference can be used to infer new mathematical statements based on earlier proof and theorems which imply that the new statement is true as well.

G del, an Austrian mathematician, wanted to prove The limitations of what can be achieved with the axiom system . He has done this by his two incompleteness theorems. These theorems relate to the consistency and completeness of a formal mathematical system.

To understand the incompleteness theorems a few key points to remember:

In an incomplete system, a statement can neither be proven nor disproven. Such statements are called undecidable .

For any computer program, its inputs are read as strings even if another program or the program itself is given as the input.

Computational formalization is simply the axioms of the system which are always true. Allowing the system to be formal.

F is used when referring to a formal mathematical system.

A predefined working of a program: Program B: reads a proof (P) and statement (S), if S is in F and P is the proof of S, then the program returns true or else false.

Computational soundness: if a statement is true in the system there is no proof to disprove it. Computational soundness implies that the mathematical system is consistent.

The first incompleteness theorem: If F is a consistent system then it is incomplete.

Proof:

P is a computer program that reads another program A and produces a statement (S)

S = A loops when run on A

P cycles through F to find a proof for S ( similar to how Program B works).

If P finds a proof then it outputs A loops and halts. Else P loops.

Now suppose P runs on itself as an input.

Case I : P halts on P

Then this proves P halts when run on P

If P halts this also proves S in terms of P, P loops when run on P .

There is a contradiction here as this proves both statements, P halts when run on P and P loops when run on P . This questions the consistency of the system F.

Now assuming that F is consistent and P loops when run on P.

Case II : P loops on P

This means that P will never find the proof it is looking for which is P loops when run on P . SInce P checks the proof exhaustively, there is no such proof.

Now suppose G, G del statement, be P loops when run on P which is the last statement in the string. Since it is the last statement is not provable as each string could be infinitely long and there are infinitely many strings in a text.

Thus we conclude that G is true but unprovable in F, at the same time it is not disprovable as well.

Therefore from the above cases, we can conclude that a consistent system is incomplete

The Second incompleteness theorem: A consistent mathematical system can not prove its own consistency.

Proof :

Let Q be a statement which states If F is consistent, then G is true ( inferred from the first theorem)

Let K be a statement which states F is consistent .

P is a program that halts if and only if F is inconsistent else it runs forever.

Now, statement K can also be written as P loops .

So we can assume that there is a proof for Q in F. We already from the first theorem know there is no proof for G in F if F is consistent.

Hence, there is no proof for K in F . If there was a proof of K" then we must be able to deduce a proof for G through inference, but we already concluded that there is no proof of G in F if F is consistent.[4]

Thus, we can conclude that F can not prove its own constancy.

There are many other extensions to the G del incompleteness Theorems such as Rosser s theorem that checks for the statement and its negation. Fixed Point Theorem that introduces a free variable into the proof. All these follow the same principles as the G del theorems to show the limitations of an axiom system .

Let s assume that our current mathematical system is weak and adding more axioms would make it a stronger, more formal and consistent system. Adding axioms will not solve the problem of incompleteness as the process to make a complete system never ends and will always have incompleteness within it.

Implications of the G del incompleteness Theorems on AI

The theorems suggest that it is not possible to have a strong or/and complete AI. Some aspects of AI can be achieved but not all.

Reasons we can not achieve a strong or/and complete AI:

One of the main reasons is that the Turning Machine ( an abstract machine with unlimited storage and can compute without making mistakes) fails to come to halt in the Halting Problem as the consequence of G del incompleteness Theorems. The halting problem states Can a program when run on itself as an input determine if the program halts or loops? . This problem can not be solved as it results in a contradiction similar to that of the incompleteness theorem.

Another factor is the problems that are deterministic but not computable such as the tiling problem. The tiling problem states If given n tiles of certain shapes (each can be different), is it possible to arrange the tiles in a certain way to obtain a given shape in given dimensions (measurements)? . The tiling problem also has added levels of complexity if conditions such as adjacent tiles must be the same colour or the tiles can not be rotated and others are added. This tiling problem is not computable as there is no fixed algorithmic approach and can only be achieved through trial and error.

These issues hinder us from achieving a complete AI with a classical computer. But we hope that quantum computers may be able to solve these issues. In the case of not computable problems, this can be done by quantum computational proofs``. A quantum computer has the ability to derive and check proofs but it may fail to explain how it did it. Any attempt to watch the internal workings of a quantum computer may compromise the proof itself due to the nature of the superposition of the Qubits. This, therefore, limits our understanding of the problem itself. In the case of the halting problem, a quantum computer might be able to solve it but it is not yet studied in greater detail.

Thus, the possibility of achieving a strong and complete AI with quantum computing is not yet known.

An interesting question that arose in one of the articles was whether our human mind can be related to the incompleteness theorems. Is the reasoning of our mind capable of reasoning itself? Is it consistent, and therefore incomplete? Or is it consistent in the first place? These philosophical ideas show the extent to which the G del incompleteness Theorems can be applied to.