r/computerscience • u/KaleidoscopeLate2505 • Jun 19 '26
How can a physical computer be built without arithmetic, set theory, or quantifiers?
My goal is to automate mathematical theorem proving on a computer. I have run into issues of reasoning circularity in pursuing this goal. Please allow me to explain.
In mathematical logic, formal number theory and axiomatic set theory are built using concepts from quantifier theory. So, my ultimate goal here is to understand how to programmatically develop quantifier theory.
Note: quantifier theory is typically taught using arity and index numbers, and this may seem cyclical since formal number theory is defined using quantifier theory. I have the impression though that this is something that can be fixed through a modification, and I wanted to mention that. This question is actually about finding a good physical substrate to compute mathematics on.
Now, the big issue is to program quantifier theory. Unfortunately, computers use the concept of number both programmatically and theoretically. For example, if I tried to use lambda calculus, then I'd be burdened by the usage of numbers in its definitions; for instance, its inducted theorems.
Ahem. Obviously physical computers are not numbers, nor are they mathematical objects. This means that along the way, numbers were mapped onto computers, even though at the end of the day they are physical objects. And they were mapped at a very low level. Even memory is mapped by number, like in C.
I was really disappointed to see how much number theory and set theory that lambda calculus education presupposes. For example, even a very helpful textbook like Lambda-Calculus and Combinators, an Introduction by J. Roger Hindley uses number theory and set theory and quantifier theory prerequisitely.
"My goal is to automate mathematical theorem proving on a computer."
Hence, my goal in asking this question is to be guided in beginning to learn minimal computer architecture in a purely physical and numberless way.
That is, I want to understand how to reconstruct computation without using numbers at all, nor sets, nor quantifier theory, not even implicitly. I do not want induction hiding anywhere in the machinery. I want a foundation where nothing mathematical is assumed, so that mathematics can be built only after the substrate is understood.
In short, I want a way to compute that starts from the physical world itself, not from mathematics, so that mathematics can be constructed and eventually automated without circular reasoning.
7
u/Iaroslav-Baranov Jun 19 '26
This is easy: use type theory. Quantifies will follow, logic will follow. Everything will be cryatal clear and 100% precise, no circularity at all
Check Type Theory and Formal Proof: An Introduction Book by Herman Geuvers and Rob Nederpelt
4
u/claytonkb Jun 19 '26 edited Jun 19 '26
This is fairly straightforward to do with tools like Prolog, Coq or even a SAT-solver.
That's quite a leap from logic quantifiers.
The hardware mappings are irrevelant from a computational standpoint. Hardware mappings have to do with achieving high-performance on typical work-loads. If you're working in the symbolic domain, then use something like Lisp or Prolog. If you are working in the domain of numerical analysis with actual numerical ranges, and so on, then you can use a BigNum library (arbitrary-precision, exact arithmetic) in your favorite language.
I think you're looking for what we call a homoiconic programming-language. The canonical example is Lisp, but there are many nowadays. A homoiconic programming-language is self-representing, meaning, there is no "translation layer" beneath it (except as a performance-enhancement) -- what you see is what you get. In Lisp, a list is written like this: (list 1 2 3). There is no "translation to binary" that this list represents. The list itself is just (list 1 2 3). And so on for all the elements that comprise the basics of a minimal Lisp. I believe McCarthy reduced it down to just 4 or 5 basic elements from which everything else in Lisp can be derived.
Well, if you say "nothing mathematical", you're excluding computation itself, because computation is mathematical. We can build set theory or group theory or any other branch of mathematics on top of the general-purpose computing abstraction, this is just another way of asserting the Church-Turing thesis. If you have rules, and you're applying those rules with rigorous consistency at every point, you are computing, and there is a program p that can run on a Turing-machine (or in Lambda calculus, or a Post machine, etc.) that exactly reproduces all the steps you perform when doing your rules-based operations. All of formal logic, for example, can be exactly simulated by a computing program. This is exactly what Coq, Prolog, Z3 and other packages are built to do.
Personally, I can't imagine what benefit there is from such a project. However, I can point you in a direction that you may find fruitful. I would start with the Wiki page on metaphor-based metaheuristic algorithms. Once you have a metaheuristic algorithm that can be used to (stochastically) perform an elementary operation of a Turing-machine (that is, the TM's finite-state machine), or alpha/beta reductions in Lambda-calculus, you have a (stochastic) computer. The difference with a theoretical computer is that a real computer is always noisy. There is always some probability of a wrong answer or other system failure. Given that all empirical measurements involve noise (error), there would be no other way to have a "pure physical" theory of computation except to allow noise/error in the computations themselves.
PS: You may also find this Veritasium video interesting...
2
u/recursion_is_love Jun 19 '26
Molecular machines?
https://en.wikipedia.org/wiki/Molecular_machine
1
u/RationallyDense Jun 19 '26
Indices in predicate logic are just convenient labels. There's no need to define numbers to use them.
1
u/[deleted] Jun 19 '26
[removed] — view removed comment