The Comprehensibility Theorem and the Foundations of Artificial Intelligence

Minds and Machines 24 (4):439-476 (2014)
Problem-solving software that is not-necessarily infallible is central to AI. Such software whose correctness and incorrectness properties are deducible by agents is an issue at the foundations of AI. The Comprehensibility Theorem, which appeared in a journal for specialists in formal mathematical logic, might provide a limitation concerning this issue and might be applicable to any agents, regardless of whether the agents are artificial or natural. The present article, aimed at researchers interested in the foundations of AI, addresses many questions related to that theorem, including differences between it and results of Gödel and Turing that have sometimes played key roles in Minds and Machines articles. This study also suggests that—if one is willing to assume a thesis due to Donald Knuth—the Comprehensibility Theorem is the first mathematical theorem implying the impossibility of any AI agent or natural agent—including a not-necessarily infallible human agent—satisfying a rigorous and deductive interpretation of the self-comprehensibility challenge. Some have pointed out the difficulty of self-comprehensibility, even according to presumably a less rigorous interpretation. This includes Socrates, who considered it to be among the most important of intellectual tasks. Self-comprehensibility in some form might be essential for a kind of self-reflection useful for self-improvement that might enable some agents to increase their success. We use the methods of applied mathematics, rather than philosophy, although some topics considered could be of interest to philosophers
Keywords Fallibility  Formal Peano Arithmetic  Formal proofs  Foundations of AI  Halting problems
Categories (categorize this paper)
DOI 10.1007/s11023-014-9349-3
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 34,507
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Mathematics: Form and Function.Saunders Mac Lane - 1988 - Journal of Symbolic Logic 53 (2):643-645.

View all 11 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Analogy and Diagonal Argument.Zbigniew Tworak - 2006 - Logic and Logical Philosophy 15 (1):39-66.
What Turing Did After He Invented the Universal Turing Machine.B. Jack Copeland & Diane Proudfoot - 2000 - Journal of Logic, Language and Information 9 (4):491-509.
On the Philosophical Relevance of Gödel's Incompleteness Theorems.Panu Raatikainen - 2005 - Revue Internationale de Philosophie 59 (4):513-534.
Löb's Theorem as a Limitation on Mechanism.Michael Detlefsen - 2002 - Minds and Machines 12 (3):353-381.


Added to PP index

Total downloads
14 ( #396,188 of 2,268,110 )

Recent downloads (6 months)
4 ( #106,477 of 2,268,110 )

How can I increase my downloads?

Monthly downloads

My notes

Sign in to use this feature