Some things are too long and technical to just go on a social media post. Some things don’t really fit the mold of my blog either. Today’s subject is one of these things.

I blog infrequently, mostly because I like my blogs to be about things I think I’ve understood to a degree that goes well beyond what meets the eye of the fleeting observer. This post is almost the opposite: it’s about things I don’t claim to understand well but which intrigue me.

This journey started with an article on Mind Matters, called “Why I Doubt That AI Can Match the Human Mind”. And it basically says three things:

• Computers can generate theorems from axioms, but cannot generate axioms
• Computers can do first-order logic, but not second-order logic (and the article seems to claim that somehow this statement is the same as the first one)
• Humans can do both (and more)

From those statements (as if they were axioms), it claims, follows (as if this were a theorem):

• Machines cannot match humans in cognitive ability

I will not go into the validity of the argument, because I actually doubt the statements it is based on. I got intrigued to find out more about (a) what is the difference between first-order and second-order logic really? and (b) why, supposedly, can’t computers do the latter? (or can they?)

As far as I understand it, zeroth-order-logic deals with statements about specific things, first-order-logic makes statements about members of sets, and second-order logic deals with sets (as members of other sets). So a (random) example of a first-order logic statement would be:

For all x and for all y, the product xy is not prime.

A lot is implied here, like for example the “domain” from which x and y can be chosen (which thing is allowed to be an x, and which type of thing is allowed to be a y in this sentence?) If they are drawn from the set of natural numbers, the statement is not generally true (if for example on of them equals one and the other is a prime number). If it’s the natural numbers excluding “1”, the statement is trivially true. If they are allowed to be real numbers or drawn from any other set, the statement is potentially meaningless (if xy isn’t a natural number, the question whether it is prime is moot). So you see it’s about things as members of sets, exactly as we said first-order logic should be. And then it’s decidable by formal proof. It becomes “computable”.

A second-order logic statement, on the other hand, would be

There exists a set P such that “5” and “7” are members of the set P.

We would also need to define from which set of sets the set P can be chosen, so as to make this statement a concrete and precise one. Thus it is a statements about sets as members of a set, and thus second-order logic. This example statement happens to be super easy for a computer or a human to prove by simply giving one (of infinitely many possible) examples, such as the set that simply contains the numbers 5 and 7, the set of natural numbers, the set of real numbers, the set of prime numbers, and infinitely many others; so the statement that (at least one) such set exists is provably true; But this is a special case: an existence proof of an existence statement can always be made by giving one example if the statement is true to begin with. Trickier to prove are the (correct) “non-existance” statements (such as “there is no green swan” or “there is no even prime number other than 2”).

Now it is fair to ask whether this first-order vs. second-order logic distinction is true in terms of computer’s intrinsic abilities, i.e. in terms of computability of statements in both first and second-order logic. Valid questions would be:

• Can computers even deal with first-order logic in general?
• Is it true that second-order logic is, if not uncomputable, at least much harder in principle?

And it is here that I must strongly disagree with the article. First, Gödel’s completness theorem, which is about first-order logic (!), proves that no (deterministic) process (and therefore no deterministic machine) can ever deal with all first-order-logic, even within one single (deductive) first-order logic system. There is no (sufficiently “interesting”) system of first order logic such that all well-posed statements therein are decidable (in the sense that we can determine within the system whether they are true or false). In fact, we now know, some decades after the original proof, that the set of undecidable statements in such a first-order logic is infinitely many times larger (namely uncountably infinite) than the set of decidable statements (which are countable)!

The halting problem goes further: The statement “this algorithm will never stop” is zeroth-order logic, and yet in general uncomputable! The article even admits as much, without drawing the obvious conclusion that there is no progression of difficulty of computation in principle, from 0th, to 1st, to 2nd order logic. But I’m getting ahead of myself. We still have to deal with 2nd-order logic and the question of whether it is in principle less computable than first-order logic. Well: we’ve already proved that some second-order logic statements are so easy to prove that “even” a computer can do it. We have also shown that the infinite number of computable first-order logic statements is infinitely smaller than the infinite number of non-computable first-order logic statements (check Cantor to convince yourself that such a statement about the relation of two infinities makes sense sometimes). So, even if there were infinitely as many second-order logic statements that are uncomputable than the number of of computable ones (which we now know exist!), it’s no worse than it already is for first-order logic!

The proof about the number of uncomputable first-order logic statements is relatively simple. It relies on Cantor’s diagonal argument in the same way as the proof that the set of real numbers is infinitely larger than the set of natural (or any other countable set of) numbers (first-order logic), or that the set of uncomputable halting problems is infinitely larger than the set of computable ones (zeroth-order logic). In fairness, and interestingly, even though they are an infinitely larger group of statements than the decidable ones (the undecidable ones are an uncountable infinite, whereas the deciable ones are countable), in general the undecidable ones take some effort to come up with (in zeroth, first, and second-order logic; in a similar way it’s “harder” to come up with an irrational number than a rational one). However, constructing second-order logic statements which are hard to prove by computer is just as hard as constructing first-order ones (the examples of Gödel’s undecidability). As far as I know, they are all essentially variations of the Epimenides paradox (the Cretan who states that “all Cretans always lie”, which isn’t really a paradox at all and yet it is always used as the paradigmatic example; go figure that one out!), such as “there exists a set of sets which don’t contain themselves”, which truly is a paradox which humans can immediately recognise as as necessarily false (such a set cannot exist, as it can neither contain itself, nor can it not contain itself; Since there is a thing that must be contained and must also not be contained in the same set, it cannot be a set). I can also buy that a computer might have difficulty with it, but I say “might”, as really I’m not so sure: The equivalent zeroth-order-logic statement is “The barber of Seville shaves all men who don’t shave themselves, and no others”, which is really identical in structure, and — I would guess and assert — easily computable as “impossible”, that is to say simply, and necessarily “false”.

It may well be true that we don’t have a ready programming language that is tailor-made for second-order-logic problems (at least a quick glance at the list on https://en.wikipedia.org/wiki/Set_theoretic_programming convinced me of that), this may well reflect a lack of a need rather than a lack of theoretical possibilities. Set theory is fundamentally a theory of “properties”, because any property can be the arbitrarily set as the the property defining membership in a given set, and membership in a set can be seen as a “property”). Second-order logic is about properties of sets, and first-order-logic is about properties of things that aren’t sets themselves. But in both cases, the statemetns usually start with a quantifier like “for all” or “there exists a”, and they go on like “for all x there exist a y such that…” or “for all x there exists no y such that…”. It’s the such that part which talks about properties, or relations, of these x‘s and y‘s, which may be set or not. I don’t think computability has anything to do with the question of whether they are sets or not.

Now, therefore, we know that the set of undecidable first-order-logic statements is infinitely many times larger than the set of decidable ones. I believe the same is true about second-order-logic statements. If the article had simply said “there are formally undecidable statements which humans have no difficulty at all in informally deciding”, or, even beyond that, “the set of uncomputable statements is infinitely many times larger than the set of computable statements”, as well as “humans don’t in general have a big problem deciding on the truth of falsehood of well-formed, non-computable statements”, I would have signed up for it straight away. And yes, maybe, that is a limitation on AI. I doubt event that, however! I don’t think computability is relevant to machine learning, which deals with all kinds of fuzzy logic pretty well, and can perfectly incorporat pseudo-random, or even actually random events in its algorithms without breaking their power (rather the opposite is true!). Beyond that, the set of uncomputable statements is generally not all that relevant in life. Most statements we have to make decisions on aren’t even logical statements at all, aren’t well-formed or well defined, and are using fuzzy concepts in their vocabulary. So in life, computability really doesn’t seem to matter much at all. Yet AI and LLMs in parituclar seem to have no great difficulty with everyday statements being evaluated in (often) useful ways.

So I don’t think the concept of computability is hugely relevant to machine learning. Perhaps the statement that “computers will never be able to (informally) decide on formally undecidable statements” is formally undecidable 😉 Yet it seems to be both obviously wrong, to us as humans, judging from how well AI deals with all kinds of “fuzzy” logic, and also not that relevant to our real lives. So perhaps we’ll live. Most likely, so will AI.