2 ms·
Back when I was working on proof of correctness, when that was a very new thing, I was using the Boyer-Moore theorem prover remotely on a large time-shared main
by Animats 5y ago
Back when I was working on proof of correctness, when that was a very new thing, I was using the Boyer-Moore theorem prover remotely on a large time-shared mainframe at SRI International. At the time, you needed a mainframe to run LISP. I was working on proofs of basic numeric functions for bounded arithmetic. So I was writing theorems with numbers such as 65536.
This caused the mainframe to run out of memory, page out to disk, and thrash, bringing other users to a crawl. It took a while to figure out why relatively simple theorems were doing this.
Boyer and Moore explained to me that the internal representation of numbers was exactly that of their constructive mathematics theory. 2 was (ADD1 (ADD1 (ZERO))). 65536 was a very long string of CONS cells. I was told that most of their theorems involved numbers like 1.
They went on to improve the number representation in their prover, after which it could prove useful theorems about bounded arithmetic.
(I still keep a copy of their prover around. It's on Github, at [1]. It's several thousand times faster on current hardware than it was on the DECSYSTEM 2060.)
[1] https://github.com/John-Nagle/nqthm https://github.com/John-Nagle/nqthm
- yjftsjthsd-h 5y ago> Boyer and Moore explained to me that the internal representation of numbers was exactly that of their constructive mathematics theory. 2 was (ADD1 (ADD1 (ZERO))). 65536 was a very long string of CONS cells. I was told that most of their theorems involved numbers like 1. Can we have a moment for the folks who managed to turn numerical purity into integers being O(n)? It's unbearably beautiful... And I do mean unbearably...
- gumby 5y ago> Can we have a moment for the folks who managed to turn numerical purity into integers being O(n)? It’s not an unreasonable approach given the application was automatic theorem proving: https://en.wikipedia.org/wiki/Peano_axioms https://en.wikipedia.org/wiki/Peano_axioms Both Boyer and Moore are quite sharp so I wouldn’t jump to the conclusion that they didn’t know what they were doing.
- shoo 5y agocould have been much worse: https://en.wikipedia.org/wiki/Dedekind_cut https://en.wikipedia.org/wiki/Dedekind_cut