Beyond Arithmetic: Understanding Computation and Computers
Two questions have always puzzled me when thinking about computers:
- Why does our everyday use of computers seem to have little to do with arithmetic computation? Emails, smartphones, routers—none of these feel like they're "computing" in the mathematical sense. Games and AI are well-known to be computation-intensive, but what about everyday tasks like reading, typing, and viewing pictures?
- What differentiates a computer from a calculator? We have a long history of building calculating tools, but at what point can we call something a computer? What key features must a computer possess?
In this blog post, I want to share my investigation into these questions. I hope it will also serve as a retrospective introduction to what the realm of computer science concerns itself with.
Generalization of Computation
Computation is commonly used as a synonym for calculation, but with greater emphasis on the process or action of mathematical calculation itself. Widely accepted examples of computation include long multiplication, long division, and Gauss summation on consecutive integers.
Let's take long multiplication as an example—say, 123 × 123. The computation process looks like this:
1 2 3
× 1 2 3
-------------
3 6 9
2 4 6
1 2 3
-----------------
1 5 1 2 9
But if we look deeper, we find that long multiplication doesn't actually concern itself with mathematical quantities—it simply follows a procedure and produces a result. It doesn't care what the quantity is: how many entities the number 123 represents means nothing to our procedure above. It doesn't even care what the numbers are.
Nothing prevents us from replacing digits with letters. Let's say 123 is simply "abc", and we define a lookup table for all operations required during the process:
computation: operation table:
a b c a $ a = a
$ a b c a $ b = b
------------- a $ c = c
c e f b $ b = d
b d e b $ c = e
a b c c $ c = f
-----------------
a g a b f
And the long multiplication still works! This time, however, we have less intuition that this represents the product of two values. We simply applied a defined process to a given string, and the output happens to align with the arithmetic operation of multiplication.
From this perspective, we can see that the numbers we use for long multiplication are just encodings. Computation doesn't care about their quantitative meaning—it cares about the process: the way it manipulates symbols to generate a result.
This example reveals several key insights about computation:
- There is an input. (We can concatenate the two numbers in multiplication into a single string using a separator like "×". In most cases, multiple inputs can be represented as one string input.)
- There is an output, the result of the computation.
- There is a process—a standardized method applied to the input to yield the output.
- Computation works on strings, which are lists of symbols. It doesn't care what the symbols mean, as long as they can be manipulated. In our example, computation doesn't care whether the operand is 123 or "abc".
Now we can arrive at a generalized view of computation: it is the manipulation of data.
This manipulation can follow different rules. There's a procedure for long multiplication, a procedure for long division, and even a procedure for simply reversing a string. Whatever the rules, computation manipulates the input data in some way.
With this understanding, we can make sense of what "computation" means for everyday applications. Spreadsheets manage tabular data. Word processors manipulate strings of characters. Pictures are 2D arrays of RGB values. Videos are sequences of images over time. Computation handles all of this data for us. These are all forms of computation in this generalized sense, far beyond arithmetic.
If you know about Alan Turing and how he helped break the Enigma code in WWII, you can see why this was fundamentally a computer scientist's work: encryption and decryption are transformations from one symbol sequence to another—a canonical computational problem.
Large Language Models also fall perfectly into the definition of computation. It's basically a program that generates an output from the input. And in this case, our input and output are both texts, which are lists of symbols by nature.
P.S. This perspective also clarifies complexity analysis. Semiprime factorization has long been considered computationally hard, but a naive analysis might suggest O(n) time complexity. In reality, integer factorization is exponential with respect to the input size (the number of digits), which makes perfect sense for symbol-based computation.
Computer as a Universal Machine
“We can form ten million of these gates, and then put the components together into a system. This system will then be able to carry out the calculations we need and work out those differential equations for predicting the suns’ movements. We could call the system … um…”
“A computer”
Excerpt From The Three-Body Problem by Cixin Liu
In his award-winning science fiction novel The Three-Body Problem, Cixin Liu envisioned a simulation game in which Von Neumann approaches a Chinese Emperor requesting an army of 3 million soldiers. He believed these well-trained soldiers could function accurately as logic gates. With 3 million of them, he could literally form a "digital circuit" made of humans, and this "human circuit" could perform the complex calculations needed to predict the trajectory of three suns.
If you, like me, found this implausible when reading it, we may share some questions:
- It seems like overkill to use a human as merely a binary gate. If we allowed a human to process decimal digits, wouldn't that be much more powerful?
- Do computers emerge from Boolean logic, or do they simply choose Boolean logic as their implementation?
Liu was clearly in awe of the computer as a miraculous technological breakthrough, without deeply considering how it evolved in the history of science. From my perspective, however, a top-down approach makes more sense when understanding the birth of computers.
We've seen that computation is fundamentally about manipulating data, which explains why modern computers handle all kinds of everyday tasks. But this raises a question: numbers are also a kind of data, and we've been crunching numbers for centuries with abacuses and mechanical calculators—so why aren't they considered computers?
The key is universality.
From the previous section, we defined computation as a manipulation that generates output from input:
input → [computation] → output
All forms of arithmetic computation are just specific cases of this generalized computation. We have one set of methods for addition, another for multiplication, and so on. We've built machines to handle some of these, like the Pascaline and the Curta calculator.
Since these are all just different forms of computation, we might ask: is it possible to build a machine capable of performing all kinds of computation?
Such a universal machine is called a computer.
Charles Babbage designed the first computer out of the above thinking. But from a more theoretical computation science view, the intuition is a little bit different.
Bertrand Russell, an influential mathematician and philosopher of the early 20th century, proposed that all branches of mathematics—including geometry, Euclidean or otherwise—can be represented formally and therefore, computed. This idea helped spur the study of theoretical computation: since mathematics can be represented by computation, then maybe we can solve mathematical problems by building a machine that is able to represent and compute.
Alan Turing then proposed the Turing machine, marking the first theoretical construction of a computer.
A Turing machine has a tape, a head, and a set of rules. It manipulates symbols on the tape, so the tape serves as both input and output. The machine performs manipulations according to its rules. If we change those rules, the Turing machine can perform a different computation. Thus, such a machine is capable of performing all kinds of computation by "reprogramming the rules."
The Turing machine defines what a computer is. A computer should be theoretically equivalent to a Turing machine. This property is called Turing-completeness.
Realizations of Computers
Even with the definition of a Turing machine, I'd like to explore the theoretical functionality of a computer more deeply.
We've seen that computation is the manipulation of data, and that computers are universal machines that manipulate data differently according to different instructions. I propose the following model:
input + [algorithm] → [computer] → output
This means a computer accepts both an input and an algorithm, then processes them to generate an output. Anything that fulfills this functionality is a computer. Its universality is achieved by replacing the algorithm—in other words, by programming. This model is compatible with Turing machine introduced above.
In this sense, we can see why "computer" was an occupation before it was a machine. Early human computers were given a set of instructions and figures, and they produced results by calculating. The results were then forwarded for further processing. What they did was no different from the abstract process described above. These people contributed to calculating the Nautical Almanac for the British government. During WWII, the US government also recruited human computers to compute ballistic trajectories.
You, too, can serve as a Turing-complete computer. Let me give you the Sieve of Eratosthenes algorithm, one of the earliest algorithms:
1. List all integers from 2 to n (the input number)
2. Let p = 2
3. Mark p as prime, then cross off all multiples of p in the list
4. Let p equal the smallest integer in the list that's neither marked nor crossed off. Repeat from step 3 until all integers are marked or crossed off
5. Output all marked integers
Now I'll give you an input of 50.
You should be able to take in this input and algorithm, execute the algorithm, and produce the output:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
This demonstrates that human brain is, at least in some sense, Turing-complete.
But we also want a physical machine capable of taking in inputs, executing algorithms, and producing outputs. This is especially desired last century, when people were trying to automate everything.
With such a specific definition of what we want, we can realize it using various levels of human technology. Charles Babbage designed the Analytical Engine mechanically. Later, we had ENIAC and modern computers that run on logic gates.
Turing-completeness is a fascinating topic, and I'm sometimes amazed by how diverse its realizations can be. There's an interesting video showing that Microsoft PowerPoint is actually Turing-complete: On The Turing Completeness of PowerPoint. If you know Conway's Game of Life, it too is Turing-complete because people have managed to construct logic gates within its grid.
I won't dig deeper into how logic gates can be designed to function as a computer, which would be a whole new chapter. But there's an interesting topic regarding Turing-completeness: when designing a computer capable of executing instructions which algorithms are composed of, we typically define an instruction set. This set includes multiple instructions that together make the computer capable of all computations.
But how few instructions can we get away with? As we add support for more and more instructions, which one transforms a simple adder into an all-powerful computer?
For the first question: the instruction set can be as small as a single instruction. For the second: in most simple computers, it's the conditional jump instruction that makes the difference.
Epilogue
I hope this article has given you deeper insight into what computation is and what a computer is. Now let's review the questions we raised in the beginning:
Q: Why computers handle everyday tasks?
A: computers manipulate data. As long as there is data manipulation, it's a computational problem.
Q: What makes a computer a computer?
A: computers are systems that take in inputs and algorithms (or programs) to generate outputs, with the requirement that the programs can be changed to solve all computational problems. That universal capability, or reprogrammability, is what differentiates a computer from all other computational machines.
I started this investigation after finding myself confused by these questions even after graduating with a degree in computer science. But for me, this exploration raises more questions than it answers:
- Computation works on symbols. That means our problems have to be encodable, and that computation works on encodable sets. Since "encodable set" is essentially equivalent to "countable set", is computation limited to countable sets? Can problems regarding uncountable sets be computed?
- Are there other ways to build a computer without Boolean logic? As in the case of Game of Life, can we construct a more efficient computer with it instead of falling into good old logic gates?
- When discussing complexity, when should we use input size versus input value as our basis?
- Was Russell correct that all mathematics can be viewed as computation? For Euclidean geometry this seems plausible, but what about other branches?
- Is human brain Turing-complete? And is there a difference between a human brain and a computer?
I hope to answer these questions in time.
When I took my undergraduate computer architecture course, our project was to implement a 32-bit processor with Verilog. The more instructions it supported, the higher our score would be. So all my peers stayed up late trying to implement as many instructions as they could. But now, looking back, maybe figuring out a Turing-complete processor with as few instructions as possible would have been more educational.
References
The contents of this article come mostly from my understanding of the book Computer: A History of the Information Machine by Martin Campbell-Kelly and William Aspray; and CMU 15-251: Great Ideas in Theoretical Computer Science.
These resources are highly recommended if you, like me, felt your CS101 course dived too quickly into programming without first establishing an understanding of computation, which the realm of computer science is built upon.
Afterword
After finishing the draft to this blog, I fed it into ChatGPT for sanity checks. I opted out of using my conversations for training.
Later, when I tried to test this question with Claude, it has quite good answers, so good that if I had been able to acquire, I wouldn't have had to dig into such a rabbit hole. The conversaion(share link here) is as follows:
Me: Let me test you with this question that I've recently overcome: what is computation and what defines a computer? Human has made tools for computation but at what point can we call that calculating machine a computer? And why do our everyday tasks like texting and reading have anything to do with computation?
Claude: This is a wonderfully deep question that gets at the heart of what computation really is. Let me unpack each part.
- What is computation?
At its core, computation is the process of following rules to transform information from one form to another. It's mechanical—meaning it doesn't require understanding or creativity, just the systematic application of procedures. When you add 2 + 3 by following the addition algorithm, you're computing. When a calculator displays "5," it's done the same thing, just with electrical signals instead of your mental steps.
The key insight is that computation is fundamentally about symbol manipulation according to rules. Those symbols could be numerals, letters, bits, or anything else. The rules are what matter—they're precise, deterministic, and don't depend on what the symbols "mean."
- When does a calculating machine become a computer?
This is genuinely blurry, and historians debate it. But I'd point to a crucial transition: universality.
Early calculating machines—like Pascal's Pascaline or Leibniz's stepped reckoner—were specialized. They could add, subtract, multiply, divide. That's it. They were brilliant engineering, but each operation required different mechanical setup.
Computers became truly "computers" when they became programmable—meaning the same physical machine could perform any computation if you changed its instructions. This is often dated to Alan Turing's theoretical work (1936) or Charles Babbage's Analytical Engine (1840s, never built in his lifetime). The Analytical Engine was conceptually a computer because it could execute any algorithm fed into it via punched cards.
So the dividing line isn't really about speed or complexity—it's about flexibility. Can the machine solve different problems by changing its program, not its hardware? If yes, it's a computer.
- Why texting and reading involve computation?
Here's where it gets interesting: they don't inherently involve computation, but modern devices use computation to enable them.
When you text, you're engaging in communication—that's a human activity. But the phone is computing: it's translating your finger taps into electrical signals, routing them through networks, decoding them on someone else's device, rendering pixels on a screen. All of that is computation—symbol manipulation following rules. Similarly, reading is a cognitive act, but a digital screen displaying text requires computation to store that text in memory, fetch it, convert it to electrical signals, and turn pixels on and off.
The confusion arises because we've become used to thinking of "computers" as specialized devices for "computing" (spreadsheets, calculations). But really, computers are universal symbol-manipulating machines. They can manipulate any symbols: numbers, letters, sounds, images, instructions for other machines. Texting and reading are just patterns of symbols. So once we had universal computers, they could handle them too.
The deeper point: You've probably overcome the intuition that "computers are for math" and realized they're really tools for any systematic information processing. That's actually quite profound. It means the same device computing your tax return can also simulate a conversation, play music, or control a robot—not because of any mysterious magic, but because all of these are just different patterns of symbol manipulation.
Such an answer is surprising, especailly when it clearly states that "symbol manipulation according to rules". This is not a common assertion to make. I tried to Google "computation symbol manipulation", the top 3 entries are:
- Computation is Symbol Manipulation, by JS Conery, Cited by 26
- Computer algebra, on Wikipedia
- Computation is just interpretable symbol manipulation, by S Harnad, Cited by 114
I asked Claude for the sources of its answer, it said that it's from its understanding.
But I'm sure if you search for definitions of computation, there will be some much more widely spread answers instead of symbol manipulation.
Maybe the ability to ask the right question also counts. I wasn't able to name my problems with this kind of clarity before.