A FACT360 BLOG SERIES – PART 10
Professor Mark Bishop,
FACT360, Chief Scientific Adviser
[email protected]
Continuing his series of posts on ‘The Science of AI’ (read the first post here), FACT360’s Chief Scientific Adviser, Professor Mark Bishop discusses whether every problem is computable and what this means for generating insights from human communications…
Many of problems we encounter in our daily life are computable and lead themselves to solutions via a suitable computer program; problems ranging from the trivial (say, multiplying 17 by 23), to the decidedly non-trivial (e.g. accurately predicting the structures of almost every protein made by the human body[1]). Those of us working at the ‘bleeding edge’ of Artificial Intelligence, are very interested to learn if complex real-world problems – problems such as: Natural Language Understanding; Level-5 Autonomous Vehicles or Artificial General Intelligence … – are also computable. Because, if not, then there may exist arguments to show that some of these – the most challenging problems of AI – are in fact incomputable.
To begin to probe the position regarding the putative incomputable in AI, we must first enquire if every conceivable problem has a computable solution? The answer to which is a resounding “No!” But to understand why, we will need to visit a little elementary set theory.
…to understand why, we need to visit a little elementary set theory.
Sets can be finite or infinite. The notation |A| stands for the cardinality, or size, of the set A, (i.e. the number of elements in the set A). If A is a finite set, then |A| is a natural number (i.e. those used in counting; the positive integers: 1, 2 .. n). We can define the ordinals (‘ordinal numbers’) as being the ‘labels’ required to arrange the order of a collection of objects in a set. E.g. for finite sets of natural numbers, we can simply use a natural number as the ordinal value.
If the set A is infinite, then the cardinality of A, |A|, is a special kind of number known as a transfinite cardinal number. The first transfinite cardinal number is given the Hebrew letter name ℵ0 (“aleph zero”); the next is ℵ1 (“aleph one”), etc. Similarly, we are obliged to use ‘transfinite ordinal numbers’ to specify labels[2]; the smallest such infinite ordinal being w (“Omega”), the length, (or ‘order type’), of the natural numbers.
Georg Cantor’s (1878) ‘continuum hypothesis[3]’ asserts there are no intermediate cardinal numbers between ℵ0 and the cardinality of the continuum (the cardinality of the set of real numbers, ℝ): or, equivalently, that ℵ1 is the cardinality of the set of real numbers, ℝ.
When we are thinking more about the size (cardinality) of a set, rather than specifically about listing it, we refer to an ‘enumerable set’ as being countable. lf a set is enumerable and infinite, we say that it is ‘countably infinite’ (or, ‘enumerably infinite’). The cardinality (or size) of a countably infinite set is ℵ0. The set of natural numbers N is countably infinite.
Given two real numbers x and y, the notation [x, y[ stands for the set {z Î ℝ : x ≤ z and z < y} i.e., the set of all real numbers at least as large as x and strictly smaller than y. Now, perhaps surprisingly, not every set is countable.
The endnote[i] explains this in detail showing how it is possible for a number to exist in a set e.g. [0,1[ but not appear in the emuneration. For our purposes at this stage, we just have to appreciate that not every set is countable, however unintuitive this may seem.
Coming back to computation, it transpires that we can deploy a ingenious technique called ‘Gödel numbering[4]’ to map every Turing machine to a unique [Gödel] number, such that no two Turing machines will ever code to the same Gödel number. That is, all Turing machines are assigned a unique [Gödel] number and from that [Gödel] number, the entire Turing machine program can be recovered.
The bijective use of Gödel numbering to code arbitrary Turing machines demonstrates that there must be a countably infinite number of Turing machines and the Church-Turing thesis implies that a function f is computable if and only if it is Turing-computable. Hence there must be only a countably infinite number of [Turing] computable functions, ℵ0.
However, the total number of functions is uncountable. To see this, we show that A = f : N → N is uncountable.
First, let’s assume that A is countable and let f0, f1, f2, . . . be an enumeration of A. Let f : N → N such that f (n) = fn (n) + 1 if fn (n) is defined, n otherwise. Clearly f, as a parameter of one natural number N, must appear somewhere in the enumeration A. However, we very carefully defined f ≠ fn (for any n ≥ 0). Hence there is a contradiction and A must be uncountable; hence the number of functions over natural numbers is uncountable.
Since the number of computable functions is countably infinite but the number of ‘natural number functions’ is uncountable, the number of non-computable functions must also be uncountable. In fact, the size of the set of computable functions is ℵ0 and the size of the set of non-computable functions, the incomputable, is much larger; it is the next infinity, ℵ1.
There are arguments for several important problems in AI showing they cannot have computable solutions and we must all learn to moderate our expectations.
In summary, as a modest young teenager, I used to believe that if a problem was well-defined, it must have a computable solution; a solution which, given enough time and comprehension of the problem, I could arrive at. But given the above result – that there are massively more incomputable functions than computable ones – it is clearly an open question if any one particular problem does have a robust computable solution. Indeed, in blogs to follow, I will argue that that there exist robust a priori arguments to show that several important problems in AI that are of particular relevance to business – specifically, NLU, mathematical creativity and consciousness – cannot have computable solutions; in engaging these problems via computer, we must all learn to moderate our expectations.
Professor Mark Bishop is FACT360’s Chief Scientific Adviser and to see how these leading-edge scientific techniques can be applied in your organisation download our White Paper “The Science of FACT360”or get in touch [email protected].
[1] BBC News, “AI breakthrough could spark medical revolution”, https://www.bbc.co.uk/news/science-environment-57929095.
[2] This is because while any set has only one size (its cardinality), there are many non-isomorphic well-orderings of any infinite set. A well-ordered set is a totally ordered set (given any two elements one defines a smaller and a larger one in a coherent way), in which every non-empty subset of the set has a least element. In particular, there is no infinite decreasing sequence.
[3] In May this year (2021) new evidence emerged that the continuum hypothesis could be false and that there are more reals than ℵ1, in which case the size of the continuum will be a larger infinity, ℵ2. Asperó, D & Schindler, R. (2021), Martin’s Maximum++ implies Woodin’s axiom, Annals of Mathematics: 193 (2021), pp. 793-835: “We show that Martin’s Maximum++ implies Woodin’s ℙmax axiom (∗). This answers a question from the 1990s and amalgamates two prominent axioms of set theory which were both known to imply that there are ℵ2 many real numbers”.
[4] “Gödel numbering” is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number; its Gödel number; it was used by Kurt Gödel for the proof of his incompleteness theorems (1931).
[i] Consider the set [0, 1[ That is, the set of all real numbers that are written with ‘0’ to the left of the decimal point. If [0, 1[ is a countable set then there must exist an enumeration function: f : N → [0, 1[. The function f enumerates the interval [0, 1[ as follows:
f (0) = 0 ∙ a0,0 a0,1 a0,2 a0,3. . .
f (1) = 0 ∙ a1,0 a1,1 a1,2 a1,3. . .
f (2) = 0 ∙ a2,0 a2,1 a2,2 a2,3 . . .
. . .
Where [ai, j] specifies the jth digit of the ith real.
Now, we will construct a new, strange, real number b which clearly belongs to [0, 1[, but which provably cannot appear in the enumeration. To do this we need to ensure that, for each i Î N, we force bi = (ai, i + 1) mod 10. The point of doing this is to guarantee that we are choosing bi to be a different digit from ai,i. Finally, we choose b to be this real number:
b = 0 ∙ b0 b1 b2 b3. . .
By definition, it is easy to see that b Î [0, 1[ But given the function f, enumerating [0, 1[, it must be the case that:
b = f (k) for some k Î N.
Therefore, this must be true:
b = f (k) = 0 ∙ ak,0 ak,1 ak,2 ak,3. . .
In particular, it must be the case for the kth digit that:
bk = ak,k
However, bk was carefully defined so that:
bk ≠ ak,k
Hence, we have a contradiction, which means one of our assumptions must be false.
But the only assumption we have made – other than all the standard rules of mathematics – is that [0, 1[ is countable; so then, this assumption must be false. As a result of this argument, we know that the size of ℝ (which contains [0, 1[) is not ℵ0 but, in fact, turns out to be ℵ1.