# What are the mathematical concepts a computer implements?

I am well aware of theoretical work on the topic of algorithms, pioneered by Turing and Churchill as far as I know. Computers implement a large, but finite, set of algorithms. My question goes into a different direction, though.

Imagine a primitive computer with a working memory of 8 bits and that can do addition. If the addition is allowed to overflow, this machine would be a real-world implementation of a finite set with 32 elements and further, an additive group.

I guess it's noteworthy that this is not more and not less than an obvious interpretation of the machine. In reality, the machine is just levers and switches. In the case of digital computers, it's the interpretation of currents and voltages as 0 and 1 that turns the circuitry into a problem solving tool.

But what does a modern computer implement mathematically?

Memory-wise, any computer still strictly implements a finite, explicit set.

A computer cannot implement real numbers. It cannot even implement the natural numbers ... because of their countable infinity. It can implement a finite set of rational numbers (that than again approximate real numbers like PI and e well enought for all practical purposes).

Computers cannot implement (a finite set of) imaginary numbers ... or can they? There's of course no i in the digital code per se, but by implementing Q² (as approximation of R²) and the rule for complex multiplication, complex numbers aren't a challenge for a computer at all.

Now it gets weirder.

There is software like Wolfram Mathematica that can do symbolic calculation. This implies, elements of the finite set do represent without any problem arbitrary mathematical concepts.

In Haskell, I routinely work with Algebraic Datatypes, and even recursive ones. There doesn't seem to be an imposed limit: even self-reference is fine.

While possibilities seem endless, there was the counter-example of R, the real numbers, already.

So back to the question: Can a general statement be made about mathematical concepts implemented by a computer?

• Can I ask about the scope of "modern computer" in your question? A natural response to your question might be to point out that Ethernet and WiFi imply that a core aspect to computing in the present era is the Connected Modularity of physical devices to one another, and the implementation of TCP/IP suggests that the finiteness assumption may not apply for modern distributed computing, thanks to what Michael Dummett called an "Indefinitely Extensible" view of the transfinite. But I don't know if this is in scope for what you want to consider. Jul 2 at 22:12
• Before, you should ask, what are the mathematical concepts an abacus implements? Jul 3 at 5:06
• Turing's work answers this. Computer is a rule-following apparatus. Computer is a human. Turing remarked that a human with infinite time and memory is effectively a universal computer. It implements nothing, only follows rule. We understand things, and then encode them on this rule following device to "calculate". What computer can/cannot do is a topic of computability theory.
– Ajax
Jul 3 at 18:02
• @Ajax I'd prefer your comment be an answer, so I could properly reply there. A computer is not a human. Computers vary in there capacity to represent mathematical concepts. People keep suggesting the Abacus as the simplest example. Computers today still are not universal problem solvers. (Unfortunately neither a universal nor a specialist problem solver is a thing in terms of mathematics and thus not an answer to my question either) Jul 3 at 21:21

It's a great question. How do finite, imprecise, error-prone real-world objects, such as an abacus or a computer, touch the infinite perfect realm of mathematics?

Try this analogy. Suppose you have an infinite group, with a⊙b defined for every pair of elements. Now suppose you take a finite subset S of the group elements, and define a new operation ⊗, where a⊗b is defined as a⊙b only when a, b, and a⊙b are all elements of S, with a⊗b undefined otherwise.

This is analogous to a computer that is only able to represent arithmetic on a finite set of numbers.

Now, ⊗ is finite, but it is a subset of an infinite relation. If the pattern of ⊗ was "completed," we would have ⊙. Even if a computer only physically implements ⊗, we can associate ⊗ with ⊙, and say that to implement ⊗ is to implement a part of the infinite ⊙, thereby "touching" infinity.

Of course, to implement ⊗ is also to implement a part of many other possible relations besides ⊙. We could say that ⊗ "touches" infinity in many different ways, but we are picking out one particular way, ⊙, of interest.

I hope this gives a little bit of an idea.

To really make it rigorous we would need a formal model of what a physical silicon computer is, as part of a larger physical universe - some mathematical formalism to track the computer's internal state and position as the whole universe changes over time. Then we would need some way of mapping the computer's physical state to logical, symbolic states and propositions. Making all this rigorous is a challenging task and I'm not aware it has been solved.

• when discussing this earlier, I came up with the abacus, too. It's a much simpler object yet it already seems to represent numbers in the physical world. Jul 2 at 22:07
• maybe we can turn the question around: why is a machine based on rudimentary logical operations on an explicit set (the memory) so useful to us? It seems to implement part of the rigor of math. Unlike brains computers are exact machines. Jul 2 at 22:10

Partial answer: A computer does not implement mathematical, economic or any other type of concepts. It is our reason which gives the input and output symbols of mathematical or economic sense. For example, your money in the bank is just represented by a nanometer-scale-size magnetized surface. Do computers implement an economic concept in such physical fact? Certainly, not.

Regarding the tool:

You can use any tool to represent mathematical concepts. For example, you can use water to make a mathematical addition: if you get 100 cups of water, put them in a pool, and add another 200 cups of water, what will you get? A bunch of water. In order to understand the result, you need to divide it, and fast, otherwise, water will evaporate, might drain, etc. And you need to be very precise, otherwise you might easily get more or less than 300 cups of water.

So, with water, you don't get precise answers. So, you can try rocks. Now, that will be more precise. But carrying rocks is not easy. So, you can use an abacus. But performing thousands of operations is slow. In final terms, we've found that the best tool to perform operations that represent economic or mathematical concepts is the computer.

Regarding mathematical concepts:

Now, perhaps the key question is this: how are mathematical, or economic concepts, associated with a computer?

A computer, like a bunch of rocks, a pool of water or an abacus, is just a system, that is, a group of interrelated parts with inputs and outputs. Normally, systems are considered black boxes, that is, entities which we dont need to understand on the inside. We just need to understand how to interact with systems (black boxes) by means of their inputs and outputs.

You cannot, evidently, throw 100 cups of water over a computer keyboard and expect the system to register a representation of the integer number 100. And you cannot expect the printer to output 300 cups of water. But you can learn to interact with the system, like the first time you use the new coffee machine in the office. Put a coin here, choose the coffee with this button, give a little kick if it stucks, and voilà the coffee.

With computers, there's a typical language we've developed, which implies: how to give concepts, or meanings, of a representation; how to feed them to the computer by means of the inputs; how to get the outputs, and how to give the output symbols of conceptual meaning. As you see, the computer does not implement mathematical concepts. It just perform computations which yields bunches of bits that are represented in some form.

With a computer, or with an abacus, you can perform operations if you, and only you, know how to represent your subjective concepts into computational terms. Can you get the square root of love, calculate its market value in bitcoin, and transfer it to a bank account? Up to you.

Excluding the computers subject, any concept in the brain can be represented with symbols. I can represent seven dollars with seven rocks, and make mathematical operations with that. I can represent infinity, or even the empty group with a pebble. The problem here is to make proper usage of the symbols and concepts. And that's a different subject: mathematics.

Mathematics has precisely such goal. Key information: mathematics is a language and a tool. A language, which allows the representation of mathematical concepts, and a tool, which allows processing such concepts and obtaining results. When you use an abacus, you are using beads to represent mathematical concepts (in the simplest case, positive integers) and make mathematical operations (math is also a tool) by moving beads following certain rules.