Foundational Questions

Original: 02/01/20
Revised: 06/10/21, Revised: 02/11/22

In this article we elaborate on the impossibility of constraining AI into a formal system of rules such that no unintended consequences can occur by following those rules. Gödel's theorems show that there are limits to what can be done with mathematical formalism; these limits are also behind this impossibility of constraining AI. To be sure, those limits in mathematics did not and will not stop progress, just as the present anxiety about AI will not stop the progress of AI. It is not for lack of trying, it is not that we just have to push harder in order to get our answers, it seems that uncertainty is an intrinsic part of our mathematics and our physics, and so it is something to embrace, rather than fear.

AI is now in a situation similar with the situation in which mathematics was at the beginning of the 20th century. Up until that time, mathematics looked primed for eternal unquestioned expansion, adding more and more beautiful bricks to its edifice. Then some kinks (=paradoxes) in that awesomeness appeared and we now have a more sober view, and an awareness of the limits of what can be done mathematically. We have seen in the previous articles that the extraordinary recent success of AI is mainly due to deep learning applied on large data sets, which learning is done with neural networks. We do not yet have a mathematical theory which explains how these neural networks learn, adding a very specific point to the uncertainty. We just see that they do learn, in a black-box fashion. We cannot satisfactorily explain yet why we choose specific layers in these networks to solve a particular AI problem, and many times these choices feel more like an art than a science. As we will see below, the very concept of learnability in these deep neural networks may be also intimately related to foundational questions of mathematics, and some of these questions are fundamentally unanswerable.

Another set of questions arises from the fact that AI is software, and as such, it has defects. In many areas of software development where safety is paramount, either because of a potential loss of human life or because of a potentially unacceptable financial loss, for example sophisticated medical devices or space missions, software professionals employ formal methods, i.e., tools of mathematical logic. These methods ensure that programs do indeed satisfy their specifications. In fact, specifications are nothing but mathematical theorems and programs are nothing but proofs of these mathematical theorems. In a fundamental way software can (and should) be reduced to mathematics. For these formal developments, there is no need for Quality Assurance (QA) teams because this software is guaranteed to have no bugs. As you can imagine, this kind of formal development requires high skill sets from its practitioners, a higher knowledge of mathematical logic, and it is very expensive to do. To our knowledge, no practical AI systems yet are being developed with formal methods at this time.

So, we develop some critical software for medical devices and space missions with formal methods. But is there an area more critical to human life, or with potentially higher financial loss than AI? Should we even strive to develop powerful AI systems that could possibly reach a higher intelligence than ours, without being sure that their specifications are safe and beneficial to humans and that the programs implementing these specifications are bug free? Not just that, but certainly AI systems will be able to detect bugs in other AI systems much better that QA teams and exploit those bugs to achieve their goals, however benign those goals may or may not be. Software bugs in AI systems represent a new category of risk.

We have seen in the Graphs of Data article that AWI systems are implemented and deployed in large distributed systems of computers, or in supercomputers or in combinations of these two computing architectures. They use sophisticated software, of which deep learning algorithms are only a very small part. In fact, in most AWI projects, software development issues, for example those related to Big Data (extracting, cleaning, and moving distributed data), take upwards of 80% of total project time. Data scientists and machine learning engineers spend most of their time in software development, rather than in training statistical models, which models are the core of AI. So the issues regarding the safety of these AI systems cannot be disassociated from general issues of safety in software, for very practical reasons.

Both sets of issues, the limitations to our possible control of AI and the issues of safety in our AI software, spring from the same source, the formal systems which are the very foundation for doing mathematics. Formal systems, with their limitations and their power, are much better understood now as a result of all the introspection started by the crisis in the foundations of mathematics, to which we will now devote some space.

Crisis in the Foundations of Mathematics

This foray into foundations has a definite goal for us. Without this foray, not much of what we say now or later would make sense. The crisis in the foundations of mathematics has led to Gödel's incompleteness theorems, without doubt the most important theoretical results behind our entire website. The theorems were mentioned already in the first video above, and they pop up in too many contexts; without a basic understanding of them, we would lose our footing. Not only that, but we are going to be a bit persnickety about terminology and concepts. One of the main themes in our website is that AI will force us to sharpen our understanding of all human affairs, that added precision being required to operate side by side with AI. It is also needed in the search for a formally specified morality which will up the odds of building benevolent AI systems.

Formal methods in mathematics were developed as a reaction to a deep crisis in the foundations of mathematics at the beginning of the 20th century. Until that point, mathematics looked like an ever-growing tree of knowledge, spawning beautiful theorems without much worrying about their logical foundations. Between 1874 and 1884 Cantor had just formulated a powerful theory of sets and in that theory there is an astonishing array of different infinities, not just one. Everything was pointing to a glorious future. Then Bertrand Russell formulated a set-theory version of the contradictory statement

You can easily see the problem with \(A\), namely that if \(A\) is true, then \(A\) is false, and if \(A\) is false, then \(A\) is true. Any theory that allows contradictions is worthless, because then you can deduct anything with it. \(A\) is a self-referential statement and you may think that the problem is with the language, not the logic. But Russell then considered the set of all those sets that do not contain themselves as a member, a perfectly legitimate construct of Cantor's theory of sets up to that point, namely:

$$S = \{x \mid x\ is\ a\ set\ ,and\ x \not\in x\}$$

The symbol \(\in\) means "belongs to", and \(\not\in\) means "does not belong to". Just as with the self-referential statement above, this set is a problem, and clearly not a language problem. According to its definition, if it does not contain itself, then it contains itself, and if it does contain itself, then it does not contain itself. Needless to say, the foundations of set theory had to be revised so that \(S\) and similar contradictions could not be formulated. Obviously \(S\) cannot be a finite set, the problem only occurred after Cantor's allowance for the diversity of infinite sets. Some mathematicians wanted to impose a limiting of this diversity, but the pre-eminent mathematician of that time, David Hilbert, had more ambitious plans.

The definitive clarification of the nature of the infinite has become necessary, not merely for the special interests of the individual sciences but for the honor of human understanding itself.

Hilbert proposed to base all of mathematics on rigorous formal systems. What is a formal system? A formal system is a game and this may seem a bit hard to swallow when we are talking about basing the whole of mathematics on games. Such a game consists of a number of symbols, a grammar that specifies how symbols can be combined into formulas, a number of specially selected formulas called axioms, and a set of rules of deduction, specifying how to deduct formulas from other formulas. How is the game being played? You start with axioms and apply the rules of deduction repeatedly to get other formulas. These new formulas that you get from axioms are called theorems, and the string of deductions that you used to obtain a theorem is the proof of the theorem. All the mathematics you have learned is based on such systems: numbers, geometry, algebra, calculus, etc. All the mathematics you have not learned yet is also based on such systems. One of the very first aha! moments that follow from this game playing is the realization that mathematics is not about truth, it is all about provability, it is all about playing games! Kids should love it! But it is the relationship between truth and provability which is at the crux of our discussion. This relationship belongs to logic, as do the formal systems and their study. So we will be doing a bit of logic here, not mathematics, in other words we will talk about the rules of the games, but not play the games. The material is a bit technical, and while it is needed for a full understanding of Gödel's work and its implications for AI, the reader may decide to gloss over it and return maybe later, on a rainy day:

To resolve the crisis in the foundations of mathematics, Hilbert asked for a proof of the consistency of PA (if you did not click on the "Truth and Provability" button above, then PA will be a mysterious acronym, sorry). He was also hoping that PA is a complete system. You can see that Hilbert hoped to use mathematical rigor itself to prove the consistency and completeness of all its games. The thinking was that if PA could be proven consistent and complete, then the consistency of higher mathematics, like calculus, could be proved with similar methods.

Hilbert proposed this solution to the crisis in mathematics, namely the establishment of the consistency of PA, as part of 10 problems presented in 1900 at the International Congress of Mathematicians in Paris, which he considered the most important unsolved problems at that time. (He later added 13 more, so that today Hilbert's Problems are known as the 23 problems.) For a while it looked good. And it was in fact Russell himself, together with Alfred Whitehead, who produced a most rigorous attempt to base all mathematics on a contradiction-free logic; they published Principia Mathematica in three volumes between 1910 and 1913. Then it all fell apart again in 1931 when Kurt Gödel published his incompleteness theorems.

Gödel's theorems and the limits of understanding

Gödel incompleteness theorems are about provability within consistent systems sufficiently powerful to include PA and effectively axiomatized; effective axiomatization means that there is a computer which in principle could spill out all the theorems and only the theorems of the system; we will elaborate on this effective axiomatization later; we will call such a system \(F\). We have seen that the relationship between truth and provability is a fundamental one, and it is Gödel himself who, about 2 years earlier, in 1929, proved that there is a positive relationship between truth and provability in FOL; it is hard to understand the incompleteness theorems without the completeness theorem. Anyway, the completeness theorem shows that a statement of FOL is logically sound (i.e., true in all models of the theory) if and only if it is provable. In other words, FOL is sound and l-complete.

We are now ready for the incompleteness theorems. The first theorem states that there are statements in \(F\), which cannot be proved or disproved within \(F\). What does this mean? Why do some statements of incompleteness (as in the video you watched above) refer to truth, when there is no reference to truth in the statement of these theorems? That's why we need the completeness theorem. Gödel carefully built a statement \(G_1\) (using a very ingenious way to codify the symbols, the axioms of PA, and the provability itself, as natural numbers), such that one could see that \(G_1\) is true in the standard model of natural numbers, but which could not be proved or disproved. Gödel constructed \(G_1\) to assert that \(G_1\) itself is unprovable. This is mistakenly interpreted by many to suggest that Gödel introduced a paradox. There is nothing paradoxical about \(G_1\). Tying this with the completeness theorem this means that \(G_1\) is not true in some other model of PA, otherwise by the completeness theorem if it were true in ALL models, then it would be provable. \(\sim G_1\) is also not true in some model, otherwise \(\sim G_1\) would be provable, by the same completeness theorem. In the second incompleteness theorem, a more difficult statement \(G_2\) was built to assert the very consistency of the system \(F\). The theorem showed that \(G_2\) was not provable by the system, and this result was the final disappointment to Hilbert's wishful endeavor. What does all this mean for us, as we are interested in AI? It means that we cannot hope to find a formal system which will be powerful enough and which will completely capture a moral behavior of AI; there would be a model of that system in which the statement "AI is doing all the right things" is false, although we would have liked that statement to be true in ALL models.

Can we specify a benevolent AI axiomatically?

What is laid down, ordered, factual, is never enough to embrace the whole truth: life always spills over the rim of every cup.

We have seen that there are limits. Does the incompleteness of these formal systems render them hopeless? No, not at all, we kept doing mathematics in PA, and in ZF, without worrying too much about incompleteness. We do have confidence that these systems are consistent, we just have to get used to the fact that those proofs of consistency cannot be done within the system itself, you have to use a more powerful system to build such a proof of consistency, and that new system will in turn suffer the same limitation, not being able to prove its own consistency. If you insist, you just end up with a long string of systems, each proving the consistency of the one before it, but not its own.

So we should search for that formal system for AI, just do not expect it to be complete. There will be unprovable statements and that is OK. Our search for a formally specified morality (or an AI Constitution as Wolfram calls it) will continue and also the search for formal proofs that our AI programs are indeed respecting their specifications written within that formal system. Unintended consequences and relatedly, the occurrence of concepts, situations, that we did not envisage, resembles a bit what we are seeing with a neural network: nodes capture things we have not asked for, and although many times those things are not good, many other times they are, and they may correspond to creative strategies that humans have not thought about.

When attempting to write such an axiomatic system for AI, we would be facing first a representational problem, a language problem. How do we write down what AI should do, in what language? We will assume that such a language will be available, for example a symbolic discourse language, something like the Wolfram Language. Meantime, we will continue to try to find a description of these axioms in a natural language, English for example. There will be many details in such axioms which will reflect our current humanity, our current morals, our history, etc. The existence of unintended consequences should not prevent us from working on those descriptions. In a way these unintended consequences bring spice and interest to our lives. It would be boring if there wasn't always an element of possible surprise in what lies ahead.

( Man is presented with a similar puzzle. He aims his boat to reach a goal A, but ocean currents will surprise him and prevent him from reaching exactly A. When that happens he must row sideways, trying to get out of the current and resume his trip towards A. He'll reach B eventually, not A. It does not pay off to either fight the currents or to give up and drift aimlessly. Most likely, B would be a much more interesting place than A. And even our approach to formally specify morality for AI is no different. We have no idea what B will be like.

Since we started to slide off into poetry with this idea of surprise, and since poetry is closer to morality than to the foundations of math, we will need to dream a little more before the poetry makes sense, so we defer to the Superintelligence and God article where we try to answer some questions about morality and AI. In that article you will watch a video by Allan Watts, in which he posits that if each of us had 75 years of living all our ultimate pleasures, that in the end we would want to introduce surprises anyway, that just unending pleasures without surprises would become boring. And when those surprises come in, we would realize that we would actually dream of living the lives we live now; we have accumulated so much puzzle and pain, that sorting all those things out brings the most spice to our lives: we would be most interested to see where our own life goes, not how other "better" lives may unfold. Gödel's theorems offer us hope that surprises will always be available, as long as our inner systems are powerful enough.)

We have seen that there is no way for us to develop a sufficiently powerful formal system that will guarantee a benevolent AI in which no other unintended consequences are possible. But that type of limitation does not mean that we should not look for such a system. Is there a starting set of Golden Rules for AI that aim at "You shall do no harm"? Isaac Asimov proposed three such rules, known as Asimov's Rules of Robotics; we will refer to them (and dare to criticize them!) in later articles. We can safely substitute AI System for the word robot to get the more general statements we are interested in:

1. An AI System may not injure a human being or, through inaction, allow a human being to come to harm.
2. An AI System must obey orders given it by human beings except where such orders would conflict with the First Law.
3. An AI System must protect its own existence as long as such protection does not conflict with the First or Second Law.

Current Research in the Foundations of AI

Here is the plan for what follows. We have built all this apparatus, so it would be good to take advantage of it and glimpse into the future. Many of the questions about the foundations of AI will continue to touch on the foundations of mathematics. These questions are part of what it's called computational learning theory, the discipline for understanding how machines learn. Many of the concepts within computational learning theory have not reached agreement in their definitions and justifications, especially when it comes to deep learning, which is where most of the interest is nowadays. It will take some time for these questions to be settled, and we'll have to tread lightly when we discuss them. That is not a comforting position because human understanding proceeds now at a slower pace than AI's power of understanding; the progress of AlphaGo is a reminder of this pace mismatch. So it is quite possible that our development of AI will surpass our ability to find answers to some of these questions and that AI itself will find some of these answers before we do.

We have seen how Gödel carefully brought the provability mechanism into the PA system and constructed the \(G_1\) statement to assert its own non-provability. So \(G_1\) was a contrived statement but you should not be left with the impression that there are no naturally occurring mathematical problems which are formally undecidable in these formal systems. Some very significant mathematical problems have turned out, after heroic efforts, to be formally undecidable. There may also be AI algorithms whose learnability is undecidable. So these algorithms may be able to learn or not learn, but we will not be able to prove it either way. We will also see that we do not yet understand how they learn. Together with not being able to prove it when they do learn, we are sitting very pretty indeed! We can't do and we can't do. So what is it that we can do? Let's see.

Let's look at two of these naturally occurring statements that have turned out to be logically independent (=undecidable) in ZF. The first one is the Axiom of Choice (AC). It says that given an infinite collection of non-empty sets, one can build a new set choosing exactly one element from each of the sets. It may appear innocent at the first sight, but it actually makes a pretty strong statement about collections. For finite collections of sets, there is no problem picking one element from each of them. But with an infinite collection it's not so clear. In 1938 Gödel proved that one cannot disprove AC within ZF and in 1963 Paul Cohen showed that one cannot prove AC either, so AC is undecidable (=logically independent) in ZF. The vast majority of mathematicians have no problem with adding AC to ZF, and working within the so-called ZFC (ZF + AC) system, others prefer to avoid it. The mathematics done using AC is usually referred to as being non-constructive, because AC allows non-constructive sets to be considered.

The second naturally occurring statement which has been shown to be undecidable (=logically independent) in ZF and in ZFC is the Continuum Hypothesis (CH). CH is a bit more natural than AC and so it was historically the most frustrating one which could not be proved or disproved. Hilbert had it as the very first problem in his 1900 Programme. What does it say? Let's look at this problem a bit, because you most likely saw all its ingredients in high school.

The natural numbers, namely \(1,2,3, ...\), are named that way because they appear very natural to humans from the very beginning; an infant has that concept figured out, it appears that infants have an innate ability to grasp 1 and the successor function \(S(n) = n + 1\); \(\ 0\) was introduced as an abstraction a bit later, but it's not hard to see why: there is a sense of completion, of wanting to base the numbers on a set of more workable axioms. Although people make the distinction between the natural numbers \(1,2,3, ...\) and the whole numbers \(0,1,2,3, ...\) we will not make that distinction, and instead include \(0\) when talking about natural numbers.

The need to be able to do more and more with numbers (solve more and more equations) is what motivated the introduction of number systems with stronger algebraic properties. If you want to be able to always subtract two natural numbers from each other, you need the integers: \(...,-3,-2,-1,0,1,2,3, ...\). Integers have stronger algebraic properties, that sense of completion is stronger. But you cannot solve all simple equations that involve multiplication with integers, so you need fractions. That number system has even stronger algebraic properties. But all these enlargements have one property in common. With Cantor's foray into set theory, he formulated the concept of cardinality of a set, i.e., informally, "how many things are in the set?". Now, although it may appear weird first, it only takes a bit of effort to set the procedural game right (games again!?, you probably saw the procedure in high school), in order to see that based on Cantor's definition, there are no more rational numbers (fractions as we called them) than integers or natural numbers; all these sets have the same cardinality. If you have not seen how the correspondence between the rationals and the integers is set and proven to be a bijection (bijection is the procedural game, look this up with google), this may not appear natural and you may want to work that out until it does.

The next step in this process of getting stronger systems of numbers to satisfy our needs was a bit harder to swallow in high school. The simple equation \(x^2 = 2\) did not have a solution in rational numbers, so it felt like there was a hole in the rational numbers. To plug in that hole, the concept of limit of a sequence of rational numbers was introduced, and then all hell broke loose in high-school: the epsilon-delta saga of proving things was introduced and drilled for days, even weeks. This most fundamental definition was very frustrating to many people, although it is one of the most intuitive definitions math has produced. Nevertheless, the new system of numbers, the reals, was built and accepted, even as a bitter pill, and it has some pretty good algebraic properties, allowing us to solve many more problems than the earlier systems. Long live \(\sqrt 2\)! But this system of real numbers could not be put into a bijective correspondence with the other number systems, the rationals for example. The proof of this impossibility is known as Cantor's diagonal argument and it is one of the most beautiful and consequential proofs in all of mathematics. So there were "more" real numbers than rational numbers, the cardinality of the reals is strictly bigger than that of the rationals.

Could there be subsets of real numbers whose cardinality is between that of the rationals and that of the reals? The statement that says NO is the Continuum Hypothesis. This was a very frustrating question and Hilbert put it at the very top of his 1900 programme. It seemed so accessible, it dealt with our bread-and-butter familiar numbers after all, so why can't we have a yes or a no answer!? ( These number systems are so dear to our nature that we are prepared to go to great lengths to believe in their magical properties. For example, you know by now that the above equation \(x^2 = 2\) has a second solution, namely \(-\sqrt 2\). When Paul Dirac discovered his famous equation, which binds together two main theories of physics, quantum mechanics and special relativity, and for which he received the Nobel prize in physics, he looked at one of its formulations, in which the energy of a particle appears squared. He was so convinced that a negative solution must exist too, (how in the world can we have a negative energy as a solution!?), that he told people to go look for antiparticles, they must be there, the equation said so!. And indeed, they were there. )

In 1940 Gödel showed that ~CH cannot be proved in the ZFC system and in 1963 Paul Cohen showed that CH cannot be proved either in the same system ZFC. So within ZFC, CH is logically independent too. So the existence of such independent statements is very deep, one does not have to contrive them the way Gödel contrived \(G_1\) and \(G_2\). On a lighter, more humorous note, here is an entertaining video clip that nevertheless is very good at capturing the surprise felt when Gödel's results put the nails in the coffin of Hilbert's programme; it is also good at capturing the mistake being made that somehow Gödel fooled us with a proof that introduced paradoxes into PA. The proof just shows that a formal system which is sufficiently powerful will allow constructions which will be unreachable, and among these constructions, in the second theorem Gödel used that power to build \(G_2\), the statement that PA is consistent.

The video is not just funny, it touches on something that hopefully we succeeded in demystifying. "Hitler" complains about the game being played, and he asks "who needs these sentences which speak about themselves?". So the question was this, are unprovable statements just tricks? While \(G_2\), the sentence that Gödel carefully built to assert the consistency of PA within PA is contrived, the general answer is no: we just saw above that some of the most important questions in mathematics (like AC, CH) have turned out to be, after extraordinarily consequential mathematical apparatus were developed for each of those results, to be such statements. Could there be such statements in AI that are also undecidable? We'll look at that possibility next.

Undecidability and AI

We have seen in the Main AI Concepts article that the current success of AI is in large part due to neural networks. These neural networks have only recently been proven effective and they are under intense scrutiny. The relationship between undecidability and these AI algorithms is a very lively area of research at this time. Of particular interest is trying to figure out how these networks learn. We will survey some results in this area, but the reader should be aware that these results have not gained wide acceptance, as opposed to the mathematical results we have mentioned in the previous sections.

We have seen that there are interesting problems in mathematics that are undecidable in the formal systems in which they are formulated. There is no controversy about the undecidability of these problems as the proofs have been checked in different contexts and the proofs themselves have spawned new valuable tools for mathematics. Among these problems we have seen that AC is independent of ZF, and CH is independent of ZFC. Learnability for a large class of algorithms is defined as the ability of the algorithms to make good predictions about a large data set after sampling a small number of items in the data set. So far we have seen that many classes of algorithms do indeed have these properties, and that important efforts are being made to provide a theoretical understanding of the learning process for the most successful class of algorithms, the neural networks.

One of the most interesting early results has been published in 1986 in the paper Relating Data Compression and Learnability. The idea was that if the family of the algorithm can compress its samples, then the problem is of lower complexity and therefore learnable.

The connection between learnability and compression has been used to connect learnability with the continuum hypothesis. It was proposed in a January 2019 article in the Nature magazine, Machine learning leads mathematicians to unsolvable problem, that the learnability of a class of AI algorithms is equivalent to the continuum hypothesis. It would be quite remarkable if this equivalence result held up and be extended; there are some objections to the claim in the article, which will likely lead to revisions and clarifications.

How is the connection between learnability and CH being made? The function that an AI algorithm tries to learn is called a predictor. The learning process is based on a set of samples of data from the problem domain, which set is usually called a training set. The AI algorithm tries to built a "good" predictor, one that has generalization power, i.e., it works well on data samples from the problem which it has not previously seen (they were not in the training set).

Researchers in computational learning theory have proposed a number of interesting models of learning. Among these the Probably Approximately Correct (PAC) model and the Vapnik–Chervonenkis model are the most used. A machine learning algorithm (like neural networks) is said to be learnable in a model if its predictors under that model have good generalization power. In the above mentioned article, another connection is being made between data compression and learnability, after the example of the Relating Data Compression and Learnability article. The researchers in that article define both a new form of compression and a new learning algorithm based on that compression and show that the learnability of this algorithm is possible if and only if CH is true. Since CH is undecidable, the learnability of this new algorithm is also undecidable. It is not known if other algorithms, like the neural networks, also suffer from this equivalence.

Here is a video clip covering many of the concepts above. Because these concepts are not easily digestible in general, it would be beneficial to the reader to augment their understanding through this more animated video clip.

Another interesting problem is related to Conway's Game of Life. It should be known and appreciated by everyone, I am referring to it on my personal website.

The question of whether we can tell if a given pattern in the Game of Life will become stable, or it will die, or it will grow forever, is one of the most chewable normal-looking statements which are undecidable, more so than the \(G_2\) statement in Gödel's incompleteness theorem or the statement of the Continuum Hypothesis.

Could the Mind be more than Computation?

So far we have used the term computation informally. If you recall, the system \(F\), which appears in Gödel's theorems, had a stringent condition on provability, which we glossed over so far: it needed to be effectively axiomatized, in other words a computer in principle could enumerate all the formulas which are theorems of the system and no formulas which are not theorems. All the systems we have considered, FOL, PA, ZF, are effectively axiomatized.

Having such an effective axiomatization also meant that in principle the proofs of the theorems themselves could be done by a computer. And indeed, both Gödel's incompleteness theorems have been formulated in computer language and proven by automatic theorem provers; for example a proof with the Coq prover in 2004 and a proof with the Isabelle prover in 2014. But it's time to specify clearer what is meant by the term computation:

In the AI Versus Human Intelligence article we have seen how attempts to understand consciousness have brought the physician Stuart Hameroff and the physicist Sir Roger Penrose together. They were interested in finding out whether the human brain uses forms of non-standard (where standard means "as a Turing Machine") computation and proposed that one candidate was the quantum computation, facilitated by microtubules. Now that we are also familiar with foundational questions and have seen the role of computation and Gödel's theorems in these foundational questions, we can absorb some thoughts that are bringing all of these ideas altogether.

In the following clip, Sir Roger Penrose explains his conclusion that certain aspects of the human mind are not (standard forms of) computation, in particular that understanding and consciousness are more than computation, and uses the limitations of understanding exposed by Gödel's theorems to support that conclusion. We will discuss (more fully) consciousness in our very last topic article on Artificial Consciousness. The video clip is about 30 minutes long and it may require pausing and listening a few times, but the effort will be richly rewarded; there is an enormous amount of information which is relevant to our discussion of AI in the video.

Information Bottleneck Theory

Another active area of research in computational learning theory is a mathematical approach to understanding how the neural network algorithms learn. So all the concepts of learning have to be rigorously defined for them to be amenable to the definition-theorem-proof game that mathematics is based on. This formalization is easier for the supervised classification algorithms, which we have seen in the AI Main Concepts article. Any such algorithm is looking at a family of functions and attempts to learn a function from that family that would be a predictor for the problem at hand. The predictor is given labeled samples of the data from the problem domain, and it must learn how to label any other data from the problem domain.

Recently, an attempt has been made to explain learnability in deep neural networks through the Information Bottleneck Theory. In a neural network a measure of the mutual information between layers can be defined. The application of information bottleneck theory to deep networks is done by a splitting of the learning process into two phases: one phase in which a fitting is taking place, i.e., the amount of mutual information is increased between the input layers and the hidden layers, and another subsequent phase where compression is taking place, i.e., the amount of mutual information is decreased between the hidden layers and the output layer. The theory has been subjected to various challenges, and the results of these challenges are not clear yet. Some of these challenges revolve around the sensitivity of the compression phase to the activation function (either the tanh or the RELU, whose graphs are shown on the right). Nevertheless, the theory has generated much interest and much subsequent work.

The application of IB theory to deep learning has originated with a group led by Naftali Tishby. As you can see in the next video clip, the deep connection between learnability and compression is mentioned prominently. As a bonus to watching the video, you will get a few quips about the political implications of AI.

Gödel's 14 points

Without doubt, the mathematician who contributed the most to our understanding of the limitations of mathematics, and maybe of human knowledge in general (modulo the caveats in the Penrose video above), has been Kurt Gödel. His two incompleteness theorems represent some of the deepest results in all of science. Most of our article has revolved around this work on incompleteness and so it seems fitting to end this article with some of Gödel's deeper concerns.

In 1960 Gödel wrote a number of notes, not meant for publication, in which he adopted a more philosophical tone. The 14 points that he makes in those writings are of amazing depth and they are controversial, as all philosophical writings are. But coming from a man who brought such insight to how much we can know, the ideas he espouses here are astounding, and they have become very relevant for our understanding of artificial intelligence. You will have to read those 14 points (one link is below) and make up your own mind, as the reactions to it have been extraordinarily diverse. Gödel was eccentric and also interested in parapsychology; after you read his points, which may appear outlandish to many, you may find some connections between this article and the paragraph Is the human brain a quantum computer? in the AI Versus Human Intelligence background article.

Now that we will dare enter his magnificent world (or minefield for some), you should also know that much has been made of Gödel's ontological proof for the existence of God, which proof he has handed privately to collaborators around 1970, just before his death. Gödel hesitated to make this proof known for fear that it will lead to conclusions about his religiosity; he was only interested in showing that such proofs can be mathematically constructed. The proof has been checked for correctness, but remember that proofs and correctness are only relative to the system of axioms being used. So, if you are interested in Gödel's ontological proof (which you can find online), you would have to think for yourself if those axioms make sense to you. Anyway, reading through Gödel's philosophical viewpoint is a fitting ending to our article on foundational questions on artificial intelligence, since these 14 points have relevance to the deeper questions surrounding AI: