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:16:21 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

3 sources
Here's the Boyer-Moore theorem prover[1] from around 1980 doing that.[2] The proofs are fully automatic but you have to ask it to prove the theorems in an order so that the theorems you need for each step are already done. Otherwise it gets lost trying different paths. This is runnable; 8 years ago I ported it to GNU Common LISP. Takes under a second now. Took 45 minutes in 1980. This is pure constructive mathematics. No existence proofs. Everything is computable. The first theorem: X + 0 = X In Boyer-Moore notation: (PROVE-LEMMA PLUS-0 (REWRITE) (EQUAL (PLUS X 0) (FIX X))) FIX is just if it's a number, then the number, else 0. That makes the function total. The second theorem: X + (Y + 1) = (1 + (X + Y) (PROVE-LEMMA PLUS-ADD1 (REWRITE) (EQUAL (PLUS X (ADD1 Y)) (I
Read the rest
F (NUMBERP Y) (ADD1 (PLUS X Y)) (ADD1 X)))) ADD1 is a primitive of Boyer-Moore theory. ADD is actually recursive ADD1. The user just lists the proof goals. Here's the input file.[3] The proofs are all automatic. This is more automation than many modern provers seem to have. Toward the end, it proves McCarthy's theory of arrays, something I wrote. McCarthy stated those as axioms, but they are in fact provable. The proofs are clunky because there's no set theory yet. I should have built up constructive set theory first, but I didn't realize that back then. [1] https://github.com/John-Nagle/nqthm [2] https://github.com/John-Nagle/pasv/blob/master/src/work/temp... [3] https://github.com/John-Nagle/pasv/blob/master/src/work/temp...
In Natural Number Game: build the basic theory of the natural numbers from scratch
I've written in Common LISP. Here's my port of the Boyer-Moore theorem prover to CLisp.[1] I've used original INTERLISP. I've used a Symbolics LISP machine. I once did a lot of work in Franz LISP.[2] And I'm partially responsible for AutoCAD going with AutoLISP as a scripting language. I've even taken a class from John McCarthy himself, at Stanford. All that was decades ago. I haven't written a new program in LISP in decades. (In later years Python, Go, Rust, C++, and when forced, JavaScript.) * Early thinking was that programs needed to be able to modify themselves. This turned out to be a niche feature. It was a holdover from the early days of programming, where storing into the code was considered a normal activity. Von Neumann was into that. To index into an array, load instructions were modified in place. Once index registers were in
Read the rest
vented, that mostly became unnecessary. Languages can be too dynamic. You pay a price for that. Python suffers from the design feature that anything can store into anything at any time. This blocks most compile-time optimizations. * Lists as a primitive are OK, but modifying lists all the time isn't what you really want. Most languages have settled on a useful set of collections today, and their implementations, especially hashes, are highly optimized. Python pretty much got this right, and other languages now use roughly Python's various collection types. * Saving the entire state of the system, instead of having source files, was a really bad idea for anything that had more than one person working on it. * The overly clever macro system makes code hard to maintain. (I tried to port [2] to Common LISP. Got about half way. It has the original Oppen-Nelson simplifier inside, the first of what's now called a SAT solver. Originally written in MACLISP (MIT's Project MAC, not Apple Macintosh), and ported to Franz LISP by Oppen and Nelson, it has too many clever macros that I wasn't able to completely figure out a decade ago.) This is a generic problem with macro systems, of course, which is why C deliberately had a weak macro system. LISP is a blast from the path. It's fun for retro reasons, but things have moved on. [1] https://github.com/John-Nagle/nqthm [2] https://github.com/John-Nagle/pasv/tree/master/src/CPC4
In Why is Common Lisp not the most popular programming language?
His argument against infinities is interesting. He's making an argument for finite constructive mathematics. It's interesting to see that coming around again. Several decades ago, when I was working on early program proof of correctness, I spent a lot of time with the original Boyer-Moore theorem prover. This is a constructive theory of mathematics, similar to the Piano axioms. It really is possible to have useful mathematics without undecidablity. But you have to give up infinity. Boyer-Moore theory has recursion, but all recursions must have an upper bound. There must be some nonnegative integer that gets smaller with each recursion. Set theory is possible in the Boyer-Moore system. Boyer and Moore usually added the traditional axioms of set theory. But I tried doing without that to get to a McCarthy-like theory of arrays without set th
Read the rest
eory first. Arrays had a concrete representation as an ordered sequence of (index, value) tuples. The sequence has to be ordered so that array equality works. So all the functions for operating on arrays are rather clunky. Here's the sequence of machine proofs for that.[3] Back then, mathematicians hated such approaches. Infinity is a useful trick for handling the edge cases within the main case. Formulas become simpler. You can do things on blackboards with chalk more easily. Constructive math is boring and kind of ugly, because there's a lot of case analysis. But it's sound. You can avoid undecidability and Russel's class of all classes paradox. You don't actually need infinities for much of mathematics. Today there's more acceptance of machine proofs and case analysis. Everybody has computers, after all. I'm not a mathematician; I just used formal math as a tool to improve programs. This is a problem for the theorists. (A few years ago, I converted the original Boyer-Moore code to run under Gnu Common LISP, so it can be run today.[2] Proving the basics of number theory now takes under a second. It took about 45 minutes in 1981.) [1] https://sites.math.rutgers.edu/~zeilberg/Opinion160.html [2] https://github.com/John-Nagle/nqthm [3] https://github.com/John-Nagle/pasv/blob/master/src/work/temp...
In Opinions of Doron Zeilberger

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.