The Origins and Limits of AI: Exploring Gödel's Incompleteness Theorem

We all have used chat-gpt which is a large language model and know its hype regarding many different A.I models in today's time.

However if you research for the origins, it pre-dates to a time when there weren't calculators. Although not technically but the origin of A.I can be traced back to Ancient Greece with philosophers arguing about reasoning. Aristotle provided the syllogisms ( similar to transitivity in mathematics ) for arguments about logical statements which would later formed as fundamental blocks of modern computers. 

Talking about technicalities, one such mathematical technicality which A.I uses largely for automated reasoning is "Godel's incompleteness theorem". Before dwelling into it , I would like to mention how Alan Turing ( considered as a pioneer in the field of computation ) described what A.I might be. A.I should be able to pass a Turing Test which is 'when given a problem by a human, the solution given by the A.I should be indistinguishable from a solution given by a human'.

Turing test consists of following requirement of what an A.I might be able to process - 

1]Natural language processing 

2] Automated Reasoning

3] Knowledge representation

4] Computer vision

5] Machine learning 

Its important to know and resonate upon the fact that it is much better to study and research to the depths of each domain than to try to replicate an exemplar(accurate model). As Wright Brothers were successful in inventing an aircraft when they learnt more about aerodynamics rather than studying about 'How pigeons fly'. 

Lets get into mathematical part - 

The incompleteness theorem  

Key-points before understanding the theorem - 

i] Language 

ii] Interpretation 

iii] Validity

iv] Axioms

v] Consistent and Complete theorems 

vi] Decidable and semi-decidable problems 

Have a look at the following formula - 

∀ x ∃ y ( ( s(0) < x) → (x + y) < ( x ⋅ y ) ) 

lets define the above terms using this formula ,

 This formula contains symbols which are beyond the defined scope of propositional logic , these symbols are s , < ,+, ⋅. 

language - It is the set of additional symbols one wants to allow. language does not know that the function or the predicate does but it knows to how many elements these symbols are applied to. 

Interpretation - Interpretation are simply about semantics as to what does the symbol do and is usually denoted by M*.

Validity - A formula can be called valid if all interpretation are true. 

Axioms - Axioms are logical mathematical statements always considered true and assists in proving the statements/formulae true or false 

Consistent- A proof is called consistent if and only if at least one M* is true 

Complete - A proof is called Complete if and only if at most one M* is true

Decidable - A proof or formula is termed decidable if and only if it behaves like the following - 

                   a) if the correct answer is yes, output is yes

                   b) if the correct answer is no, output is no 

Semi-Decidable - Similar to decidable 

                   a) if the correct answer is yes, output is yes 

                   b) if the correct answer is no, output is anything but no. 

Our formula was -  ∀ x ∃ y ( ( s(0) < x) → (x + y) < ( x ⋅ y ) ) 

lets make an interpretation on this formula - 

- s is interpreted as numerical successor to 0 belonging to natural number ( n → n + 1 ) .

- < is interpreted as 'less than'

- + is interpreted as 'arithmetic addition'

- ⋅  is interpreted as 'arithmetic multiplication'

Thus if you any values for which the above formula is Turing computable, you'll find that for M* the formula holds true. However there exists many other interpretations for which the same formula might not be true. 

the logical system provides a systematic tools for proof. It contains what we call as soundness, if the proof is not sound, it implies that there exists one interpretation for which the validity of the proof is not true. 

Since our interpretation might hold us from proving the formula ture , lets take help from axioms. 

1] A1 -  ∀ x ( x < 0 )

2] A2 -  ∀ x ∀ y ( x < y → x < s (y) )

considering these two axioms as interpretations , the formula holds its validity true, 

Lets understand this through illustration - 

Even when you prove this formula with the help of axiom, it would still be considered as 'internally provable' there might be more axioms which makes the proof complete. 

Our proof is just consistent and no complete. Thus our problem is semi decidable. Lets take a look to understand more about decidable and semi-decidable problem 

2 problems - 

1] Given an arbitrary long number find out whether the number is a prime number. 

2] Given an arbitrary long program code , find if program runs whether the program halts.

Going by the definition mentioned earlier you will find that the problem 1 is decidable and problem 2 is semi decidable. 

With these things being understood, we find that the problem might be valid and complete with the axioms ( although few ) but if you remove the axioms the mathematical proof part just keeps on adding new and more axioms which goes beyond the Turing computation and thus causes many contradiction in the proofs making the proof 'INCOMPLETE' !!!.