AI and Math

• by Steve Cross
• June 11, 2023

Why Computers Can’t Do Mathematics

Though computers do nothing but crunch numbers, they can’t do mathematics research very well yet, including proving theorems or even validating proofs of theorems.

According to Professor Robert Solovay of UC Berkeley in an interview around 1991, computers had limited success in finding proofs in Sentential Calculus that were faster than brute force calculations.

And they couldn’t even verify proofs in fields like topology according to UCB topologist and geometer Robion Kirby in another interview around that time, the reason being that topology isn’t even completely axiomatized, and topologists proceed like physicists, making plausible statements that aren’t phrased in the formal systems accessible to computer verification.

And more recently UCB professor Eduard Frenkel, author of Love and Math, in a podcast points out that computers can’t invent or discover concepts like complex numbers (yet!?).

And I thought, even more convincingly, computers can’t come up with concepts like the Infinite Sets of Cantor, or  Zermelo-Fraenkel Set Theory to resolve the contradictions of early twentieth century mathematics.

Yet as we see below, that is exactly the field where chatGPT seemed to shine, answering questions of an interested layman, though this could be an illusion – little more than the summary of a deep search engine, or the output of a massively parallel flock of robotic parrots.

How dangerous are the new chatbots like chatGPT and Bard?

Since they can’t do math as well as Matlab or Wolfram Alpha at the time of this writing, why is there so much concern about the threat they pose? I never heard any fear of these products, and why does a chatbot pose more of a threat than Alpha-Zero of Google’s Deep Mind, that can beat the world’s best Go player and is 4,000 strength at Chess? Or IBN Watson’s ability to win the game of Jeopardy against a world champion for eleven years now?

Aren’t these much more representative of superior military capabilities than NLP systems, that Noam Chomsky dismisses as “no major scientific breakthrough” – just a glorified autocomplete, but instead of autocompleting a phrase it can autocomplete a whole story or novel? Apparently the main concern for the near future is that they might flood the Internet with false images and text.

Enter AI merging chatbots and Wolfram Alpha

That seems to be in the works, and a great merge of verbal and math skills, even if the net result is a glorified CAS system that can talk like a Barbie Doll or Chatty Cathy – it still might make a good R&D assistant – maybe more D than R.

Studying Math with chatGPT

One way to study chatGPT is to question it like a black box and try to figure out what is in its code. This sort of question and answer approach is how AI developed in the first place.

When asked what is thinking rather than mere table-lookup, one of the original definitions was the abilitty to figure out the question from the answer rather than answer a question, and some of the early AI experiments may have been the inspiration for the game of Jeopardy.

So IBM Watson’s victory in Jeopardy could be viewed as bringing it back home.

chatGPT could do Abstract math better than Concrete math

So when I interrogated chatGPT about different problems in math I was surprised and delighted to find that chatGPT answered questions I had about the abstract field of set theory but balked at some simpler proofs in a concrete field like graph theory, when it made false statements and invalid inferences about problems from the undergraduate level textbook, Pearls in Graph Theory by Ringel and Hartsfield.

Here is a discussion between me and chatGPT about the P vs NP question of complexity theory, followed by commentary. chatGPT’s answers are in bold type.

User:

Regarding the P vs NP question, an article by computer scientist Scott Aaranson showed why it is futile to try to prove that P != NP.

Donald Knuth agreed that this problem is way beyond human capability but surprised the world in his belief or suspicion that P = NP contrary to the consensus of the computer science community, in a footnote on page 1 of fascicle 4 of The Art of Computer Programming.

Given these facts, why do computer scientists and mathematicians still study the P vs. NP question?

ChatGPT

Computer scientists and mathematicians continue to study the P vs. NP question because it is a fundamental question in the field of theoretical computer science and mathematics. It has implications for many practical applications in computer science, such as cryptography and optimization, and a resolution of the question could lead to breakthroughs in these areas.

Although it is widely believed that P is not equal to NP, a proof of this would provide important insights into the nature of efficient computation and could have significant implications for our understanding of mathematics and computer science. On the other hand, a proof that P is equal to NP would have enormous practical consequences, as it would mean that many computationally difficult problems could be solved efficiently, revolutionizing many fields.

Despite the challenges involved in solving the P vs. NP problem, researchers continue to make progress in developing algorithms that solve problems more efficiently and in refining our understanding of the computational complexity of problems. Even if a solution to the P vs. NP problem is not found in the near future, the pursuit of the problem has led to significant advances in many areas of computer science and mathematics.

User:

I suggest you study why no one will ever prove P != NP.

It requires showing the non-existence of an infinite number of algorithms in a finite proof.

But the only access to infinity in the axioms of Zermelo-Fraenkel set theory is the axiom of infinity, or essentially mathematical induction.

And the reason this can’t possibly work is that the algorithms have increasing computational complexity going toward infinity, while a proof by induction requires that all the work has been done in the base and inductive step, so the assertion doesn’t get increasingly complex as n increases.

To use the domino analogy of mathematical induction, it is like turning over the first domino, which does all the necessary conversion of potential energy into kinetic energy.

But in the case of the P vs NP question, the dominos increase in weight really fast and go to infinity, showing that mathematical induction is impossible by analogy, but more rigorously with Zermelo-Frankel set theory.

On the other hand, if P = NP, a proof might be theoretically possible, but way beyond human capability in the opinion of Donald Knuth in the article cited. And science isn’t a democracy – his voice counts more than group opinion since he did more computer science than anyone else in the 20th and early 21st centuries.

ChatGPT

You bring up a good point about the limitations of mathematical induction and its inability to prove the non-existence of an infinite number of algorithms in a finite proof. This is one reason why proving P ≠ NP is considered such a challenging problem. However, just because it may be difficult or even impossible to prove something doesn’t mean that it isn’t worth studying or trying to understand.

The P vs. NP question is important because it has implications for many real-world problems, such as cryptography, optimization, and machine learning. If it turns out that P = NP, then it would mean that many of these problems could be solved much more efficiently than currently believed, which would have significant practical implications.

Furthermore, even if we may never be able to definitively answer the P vs. NP question, studying it can still lead to important insights and advances in computer science and mathematics. For example, research into complexity theory, approximation algorithms, and heuristics has already led to many important discoveries and applications. So even if we may never definitively resolve the P vs. NP question, studying it can still have great value.

Commentary – chatGPT is giving the opinions of its training data, based on libraries of math and other information up to 2021, apparently citing majority opinion.

Knuth’s comment came before this, but is too cryptic for most people to sort out what it means for this millennium problem.

Conclusion – outlook for the near future

I think the most common use of chatbots in the near future is as a much improved search engine, a great research assistant but not yet independent thinker.

Clearly chatGPT doesn’t “understand” Aaronson’s argument, but just gives the most probable next word according to its parse tree and new training data.

In the next post I will give another surprising example of how chatGPT explained an even more advanced concept to me in set theory and  botched elementary questions in graph theory that ask for a proof, though it was able to correct this with interactive prompting.

Why Computers Can’t Do Mathematics Though computers do nothing but crunch numbers, they can’t do mathematics research very well yet, including proving theorems or even validating proofs of theorems. According to Professor Robert Solovay of UC Berkeley in an interview around 1991, computers had limited success in finding proofs in Sentential Calculus that were faster…