The Four Colour Theorem: The first time machines mogged mathematicians | Hacker News Reader

The Four Colour Theorem: The first time machines mogged mathematicians

newsletter.pessimistsarchive.org

89 pointslist50 comments

https://celebratio.org/Appel_KI/article/796/#sender

That takes me back to an early 1980s incident where I was criticized for an early computer-generated proof. This was when I was building a program verifier at an aerospace company. We had the first SAT solver, the Oppen-Nelson simplifier, and the first constructive theorem prover, the Boyer-Moore prover.[1] I wanted to show that the four axioms of arrays, which the simplifier assumed to be true, were valid in Boyer-Moore theory.

Boyer and Moore had warned me of the soundness risks of adding axioms to their prover. So I tried to prove them from basic Boyer-Moore theory, which is close to the Peano axioms. Boyer-Moore theory is LISP-like in form. You start with (ZERO) and (ADD1 X). So two is represented as (ADD1 (ADD1 (ZERO))). It's all lists of tuples at the bottom.

Equality is strict. (EQUAL A B) is true only if the representations of both A and B are identical. This creates a problem. An array can be represented as a list of (index, value), but for EQUAL to work, the list has to be ordered by subscript and each subscript unique. So storing into an array is represented as insertion into an ordered list. That generates a lot of special cases.

Accessing an array is a linear list search by recursion:

    (DEFN selecta (A I)
        (IF (EQUAL (array-elt-subscript A) I) 
            (array-elt-value A) 
            (IF (EQUAL (array-prev A) (empty-array)) 
                (UNDEFINED)
                (selecta (array-prev A) I))))

That's around line 3276 in [2]. The other definitions of array operations are similarly simple. Then we get to proving the classic four axioms of arrays.

Around 3000 lines later, the classic four "axioms" of arrays have been proved. Much grinding through special cases. It's a neat result, but bulky.

So I submitted a paper to JACM. Reviewer comments included "I hate to see something this complicated at the foundations of computer science", and just "This is unnecessary." People were really upset by all that case analysis.

The theoretical problem was that I didn't have set theory. I could have built up set theory first, before array theory, then used set theory to prove array theory. That probably would have made mathematicians happier. Or not. Set theory is traditionally axiomatic, but it can be built up from constructive Boyer-Moore tuple theory if desired.

I didn't argue with the reviewers. I probably could have found a more elegant path to this result, by creating intermediate lemmas, rather than letting the prover grind through the cases on automatic. But I wasn't going for a PhD. I had real work to do at an aerospace company.

So, I've been beaten on by the academic community for a bulky machine proof. Today, nobody would be bothered by this approach. It's only a few thousand lines, and a human can follow it. You can be too early.

(You can still run this prover today. I converted it to GNU Common LISP a decade ago. It takes about one second on a modern machine to go from the Peano-like axioms to array theory. It took 45 minutes on the VAX 11/780 I was using back in the early 1980s.)

[1] https://github.com/John-Nagle/nqthm

[2] https://github.com/John-Nagle/pasv/blob/master/src/work/temp...

thank you for sharing this story :) I’ve recently been enthralled with ACL2

I understand ACL2 now runs on SBCL.

The problem of the proof was that we knew that FCT was true, but we had no idea why. A good/elegant proof teaches us something new about how that problem is related to other problems. It isn't just about getting a true/false answer to the conjecture.

Indeed, and the computer aided proof discouraged research into the insightful proof a lot of mathematicians think is probably out there to find. "Proved but not insightfully" is a problem status some mathematicians are starting to think of as closer to "open" than "closed", which is a good thing IMO. (I am not a mathematician, though)

Maybe the new heuristic auto tactics will lower the cost of finding the human proof of the four color theorem enough to be affordable in the current environment.

> the computer aided proof discouraged research into the insightful proof a lot of mathematicians think is probably out there to find

Kempe's reduction technique, on which the eventual proof still depended (at least spiritually? I think?), did contain true insight with reach beyond the original problem statement (e.g., Chaitin/register allocation).

I submit that "clever way to soundly reduce to finite set and check" is itself probably one of the more important types of insight in mathematics. Actually, all of my favorite mathematics, from an aesthetic perspective, has exactly this flavor. That's down to taste, of course, but it is sort of a fundamental/powerful move in modern mathematics. The beauty of that insight can only be appreciated once you're willing to accept that boring case checking is tractable.

In that sense, the FCT gave us two really important insights -- first some profound insight from Kempe then an equally profound insight about the role of computers as a bicycle for human thought.

Yeah, not saying the proof was worthless, and the technique is indeed a genuine insight. However, there's likely to be a proof that explains why all the cases work out rather than it just being a crazy coincidence, and the existence of the proof did stifle further research into the now "solved" problem.

In hindsight, along with illustrating the potential of computers as a bicycle for the mind it also gave the first indication that if such proofs were to become very easy to produce they could also be used as a bulldozer to bury the mind.

> "The problem of the proof was that we knew that FCT was true"

Citation needed.

That was terrible phrasing. I meant "The problem with the proof was that although it showed that FCT was true, the proof did not explain why".

Yeah. On a similar note, without the computer aspect, I once had a prof tell me that he did not like character theory. If I remember right, there you calculate some numbers from a group and can prove some properties about it. But you gain no understanding of why those properties hold.

> the proof did not explain why

So humans do/did still have a role to play

Something as simple as the FCT may have an alternative intuitive proof that humans can relate to.

I do not think it is a given that humans or algorithms can find such a proof for any given problem.

My layman understanding of Godel's Incompleteness Theorem is that you are correct. It states that there are things that are true but no proof can exist (providable by human or AI provers).

Unless AI can explain why today.

I mean, I guess we still need people for the AI to explain it to.

Unless the existence of the reason is also proved.

I don't think it will be a problem for long, as AI systems evolve they will be able to find those elegant solutions and explanations for you in due time...

I doubt that. I don't think AI are trained to find elegant solutions, they are trained to find solutions. if you look at the things that OpenAI published, so seem to be micro improvements riddled with chaos. They are better solution, but they aren't drastic.

I have noticed this with autoresearch too, the solutions and improvments that you get are incremental and not groundbreaking. Humans, have a way find elegant solutions and also seem to solve that problem. Then again, beauty is in the eye of the beholder, and I might be wrong.

Yes, spot on. I think it has to do with the lack of emotion. Humans enjoy finding something beautiful.

Until elegance can be trained through RLVF, it will not be elegant. A lot of problems in AI seem to be finding ways to bring RLVF to more domains, as the current "spikiness" of AI seems to be mostly related to how effective RL is for a particular domain (if you need RLHF you are fucked and it's why it has not gotten better at writing and individual models still have "styles")

AI does not care for elegance. That's one of the problems with the bulk of AI generated code: even if it does the job it is between 3 and 5x as much code as you would normally use to do the same thing. And even if we conclude that this is fine as long as the tests pass it is a massive barrier to understanding. Good code is easy to read. AI generated code - the bulk of the AI generated code that I've been exposed to to date, to be more precise - is overly complicated. Elegance is to do that which needs doing, no more, no less.

AI cares for whatever you reward it for, but we don't seem to care about elegance much either.

Maybe the open problems are just by nature non-elegant and we human beings are bad at non-elegant mathmatics and found them either hard or not interesting before.

It does though. To reduce from infinitely many graphs to a finite number of cases there is a lot of insight by itself.

Exactly.

I didn’t know we had invented time machines yet. ;)

We haven’t yet but we had then :-)

Mandelbrot comes to mind when thinking about the positive aspects of having a machine do some heavy lifting and showing patterns you wouldn't have noticed otherwise.

I'm not involved with proofs in math a lot but having a computer help with formalizing large parts of software so they end up more secure is a plus imo.

I think a lot of great ideas like tree-width were developed in hope of simplifying the proof.

One of the most bizarre things from the past couple of years is how every single tech person that isnt living under a rock talks like a channer incel. It feels insane to me to see everyone say shit like "mogged", "-maxxing" or "-slop".

I still don't know what "mogged" means. "-maxxing" is ugly. "Slop" is the bon mot.

the title made me think of a much older machine that was used for calculating

https://en.wikipedia.org/wiki/Antikythera_mechanism

> I would like to conclude by telling a cautionary tale. Let us try and place the Antikythera Mechanism within the global context of ancient Greek thought. Firstly came the astronomers observing the motions of the heavenly bodies and collecting data. Secondly came the mathematicians inventing mathematical notation to describe the motions and fit the data. Thirdly came the technicians making mechanical models to simulate those mathematical constructions, like the Antikythera Mechanism. Fourthly came generations of students who learned their astronomy from these machines. Fifthly came scientists whose imagination had been so blinkered by generations of such learning that they actually believed that this was how the heavens worked. Sixthly came the authorities who insisted upon the received dogma. And so the human race was fooled into accepting the Ptolemaic system for a thousand years.

> Today we are in danger of making the same mistake over computers. Our present generation is able to view them with an appropriate skepticism when necessary. But our children's children may be brought up within a society dominated by computers, that they may actually believe this is how our brains work. We do not want the human race to be fooled again for another thousand years.

-- E.C. Zeeman, Gears from the Greeks, January 1986, http://zakuski.utsa.edu/~gokhman/ecz/gears_from_the_greeks.p... (https://web.archive.org/web/20250502052226/http://zakuski.ut...)

Applying this to today seems like a stretch. Short of some sort of mythical dark age style destruction of knowledge, what we have today benefits from widespread use of writing and other forms of communication which didn't exist back then.

It seems like the biggest risks come from willful ignorance of history, which we do see in some quarters but by no means all.

The context of the whole essay was more about the way we have a tendency to confuse models with reality, in particular the way we build human-like machines based on contemporary theories about how humans work, then later fall into the assumption the theories were accurate simply because the machines are indeed useful. It's a pernicious kind of self-reinforcing confirmation bias. And it applies at least as much to AI, and LLMs specifically, as any earlier example. Whether or not one believes LLMs strongly parallel certain human mental processes, or even if in fact they do, surely we must admit there's much more undiscovered complexity and phenomena, and the pursuit of discovering those phenomena is going to be hampered to some extent by our investment in understanding them in terms of these otherwise successful tools we've built.

I think the same happens now with AI generating code. Nobody will read every line. that's part of the process from now on.

The human who commits a bad change still takes the fall though. Automation doesn't absolve accountability.

But people think it does, and it’s annoying. The past months I’ve often found mistakes and then heard the response along the lines of “oh Claude wrote that”.

It’s used as an excuse, and then the conversation just moves on. I don’t see a lot of accountability being taken. If anything, senior leadership sees it as a sign of adoption and accepts a certain level of risk.

What is "taking accountability" supposed to look like in this case?

As an aside, trying to enforce some cultural more without the backing of senior leadership is a waste of time. You should probably follow your colleagues example and get a better return on your time with Claude and stop caring. If you are the only one at your company who cares and you aren't the largest shareholder I have to ask under what economic theory you are operating. Unless you work for a charity or something you should probably either find a new job or stop complaining about the relative luxury of being handed a fistful of money just to be able to say "Claude wrote that".

Apparently no one at your company cares, so why do you?

> What is "taking accountability" supposed to look like in this case?

Admitting that you didn't validate the AI output carefully enough, and committing to do better in future.

> Apparently no one at your company cares, so why do you?

I'm not the other commenter, but this is part of my job. I'm often called in to deal with issues that have been created by bad developers, offshore developers, contractors or consultants who've helicoptered in and out, and now AI.

The basic requirements are the same in all these cases: identify the problem, recommend and/or implement fixes, and recommend process improvements.

Sometimes those improvements involve negative effects for the people perpetuating these issues.

It may not be wise to assume you can abdicate all responsibility for your work if you're somewhere that does, in the end, care about results.

The rate of output from LLMs is very high compared to most developers' capacity to review every line, especially when they are often working on multiple tasks from multiple projects all on the same day. The directive to increase code churning is coming from the top since upper management believes everything tech CEOs advertise to them, and there is increasing anxiety across tech, mathematics, finance, arts, etc. about getting replaced so people want to at least appear to be much more productive with AI. The new norm is fast becoming "There will be mistakes, but maybe not most of the time. We'll deal with it when we get there, and since we're all on the same boat, let's spread out the blame or try to ignore it since you never know when it might happen to you."

To be fair, this was always the case as there was never any guarantee of bug-free code in general, but the difference today is mainly in volume.

And the code they produce is hard to review because it isn't written in the way a human would write it. Overly verbose, overly complex, using lots of theoretically interesting constructs but unnecessary for the problem at hand. It's as if they get paid by the line.

You can to some degree curb these tendencies but I don't doubt that many people just give up at some point.

Yes, they do.

But this problem goes far deeper. People that hire someone else believe they have outsourced the responsibility, and not the work.

>[...] mogged [...]

Ixnay on the celinay ingolay.

There is now an opportunity for them to do it again by providing an easily understandable proof which isn't broken up into a large number of cases.

Reply on news.ycombinator.com