HackerReposA FIELD GUIDE TO OPEN SOURCE
ProSponsor the shelf♧ 0
← Back to top all-time
John-Nagle
nqthm
Common Lisp2016–2026
John-Nagle / nqthm

nqthm

nqthm - the original Boyer-Moore theorem prover, from 1992

2Distinct people
20Mentions
0Explicit recommenders
61GitHub stars
REPOSITORY AT A GLANCE

What to know before exploring

What it is

nqthm - the original Boyer-Moore theorem prover, from 1992

GitHub

Where it is used

No documented product use has been verified yet.

What people are saying

No recommendation phrase was found in the indexed comments.

No classified warning is attached to this page. Read the discussions before treating silence as approval.

Also in these discussions

No other repository is repeatedly linked in the same discussions.

This week on Hacker News

Nov 9–Nov 16 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/16/2026, 3:59:04 AM UTC.

No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.

Mentions over time

HN mentions by year20 dated mentions

Observed mentions: 2016-08-07 04:41:56 UTC to 2026-10-14 02:32:10 UTC.

0123452016-01-01 00:00:00 UTC to 2017-01-01 00:00:00 UTC (exclusive): 4 mentions; 1 submissions, 3 comments20162017-01-01 00:00:00 UTC to 2018-01-01 00:00:00 UTC (exclusive): 5 mentions; 0 submissions, 5 comments2018-01-01 00:00:00 UTC to 2019-01-01 00:00:00 UTC (exclusive): 0 mentions; 0 submissions, 0 comments2019-01-01 00:00:00 UTC to 2020-01-01 00:00:00 UTC (exclusive): 1 mentions; 0 submissions, 1 comments2020-01-01 00:00:00 UTC to 2021-01-01 00:00:00 UTC (exclusive): 1 mentions; 0 submissions, 1 comments2021-01-01 00:00:00 UTC to 2022-01-01 00:00:00 UTC (exclusive): 1 mentions; 0 submissions, 1 comments20212022-01-01 00:00:00 UTC to 2023-01-01 00:00:00 UTC (exclusive): 1 mentions; 0 submissions, 1 comments2023-01-01 00:00:00 UTC to 2024-01-01 00:00:00 UTC (exclusive): 1 mentions; 0 submissions, 1 comments2024-01-01 00:00:00 UTC to 2025-01-01 00:00:00 UTC (exclusive): 3 mentions; 0 submissions, 3 comments2025-01-01 00:00:00 UTC to 2026-01-01 00:00:00 UTC (exclusive): 1 mentions; 0 submissions, 1 comments2026-01-01 00:00:00 UTC to 2027-01-01 00:00:00 UTC (exclusive): 2 mentions; 0 submissions, 2 comments. Incomplete calendar period.2026*

* An incomplete calendar period is marked with an outlined bar. Its count is not directly comparable with a full period.

Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.

View mention counts and date ranges
UTC ranges include their start and exclude their end. Select a period to filter the source evidence.
PeriodStart (UTC)End (exclusive, UTC)MentionsSubmissionsComments
20162016-01-01 00:00:00 UTC2017-01-01 00:00:00 UTC413
20172017-01-01 00:00:00 UTC2018-01-01 00:00:00 UTC505
20182018-01-01 00:00:00 UTC2019-01-01 00:00:00 UTC000
20192019-01-01 00:00:00 UTC2020-01-01 00:00:00 UTC101
20202020-01-01 00:00:00 UTC2021-01-01 00:00:00 UTC101
20212021-01-01 00:00:00 UTC2022-01-01 00:00:00 UTC101
20222022-01-01 00:00:00 UTC2023-01-01 00:00:00 UTC101
20232023-01-01 00:00:00 UTC2024-01-01 00:00:00 UTC101
20242024-01-01 00:00:00 UTC2025-01-01 00:00:00 UTC303
20252025-01-01 00:00:00 UTC2026-01-01 00:00:00 UTC101
2026 (partial)2026-01-01 00:00:00 UTC2027-01-01 00:00:00 UTC202

What Hacker News says

2 sources
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 bot
Read the rest
h 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...
In The Four Colour Theorem: The first time machines mogged mathematicians
I haven't seen the Lipton/Perlis/De Millo paper in years. I was around for that argument. Which really dates me. Those guys were pushing for mutation analysis.[1] That's a test for the test suite - you make some random change to the program and see if the test suite catches it. Fuzzing is related to that concept. It's taken way too long for verification to catch on. Here's where I was almost 50 years ago.[2] Part of the problem is that most of the interest came from people in love with the formalism. The notations used by most researchers were terrible, as is pointed out in the Lipton/Perlis/De Millo paper. You want a notation that matches the programming language. We had the basic architecture back then - use a SAT solver on the easy stuff, and something with some AI capability on the hard stuff. We had the Oppen-Nelson simplifier, the
Read the rest
first SAT solver, for the easy stuff. We had the Boyer-Moore prover for the hard stuff. It's Good Old Fashioned AI, and very good for the late 1970s. The SAT solver knocks off over 90% of the verification conditions. Then you want verification notation that creates hard but abstract problems for the AI solver. Like writing two asserts in a row, with the hard problem being to prove the second one from the first. We didn't have enough compute back then. It took about 45 minutes on a VAX 11/780 for the Boyer-Moore prover to build up number theory from something similar to the Peano axioms. Now it takes about a second. I ported the Boyer-Moore prover to GNU Common LISP a few years ago, just to see it live again.[3] With LLMs to do the grunt work, this is a lot less labor-intensive. And it's really needed to keep LLM garbage under control. Given a concrete goal against which to optimize, LLM coding is much more effective. Formal specifications are still hard to write, but there are many important areas of software for which the specification is simple but an efficient implementation is hard. File systems. Databases. Networking. Some kinds of control systems. Stuff that really needs to work right. [1] https://en.wikipedia.org/wiki/Mutation_testing [2] https://www.animats.com/papers/verifier/verifiermanual.pdf [3] https://github.com/John-Nagle/nqthm
In The Case Against Formal Verification, 50 Years Later

MAKE YOURSELF AT HOME

A few shortcuts

/
Search the collection
?
Open this guide
Esc
Close dialogs and navigation

Your saved repositories and interests stay in this browser.