So recently I've been involved in a discussion and I was told that literally the only thing computer can do is addition. Is that true? What about logic operations? Aren't they performerd by physical logic gates?
4
-
1$\begingroup$ Computers can do more than only add. For example, in addition to logical operations that you mention, they can execute branching instructions. Besides, addition is ultimately implemented using logic gates (just like every other digital computation). If $x$ and $y$ are one-bit numbers then $a+b$ can be represented using two bits $z_1 z_0$, where $z_0 = x \oplus y = (x \wedge \overline{y}) \vee (\overline{x} \wedge y)$ and $z_1 = x \wedge y$. See, e.g., here. $\endgroup$– StevenApr 26, 2022 at 16:19
-
1$\begingroup$ Computers essentially do NAND operations ($\overline{a\land b}$) in logical gates. This is enough to implement any computation in the world. $\endgroup$– Yves DaoustApr 26, 2022 at 16:46
-
$\begingroup$ As @YvesDaoust indicated, in the CMOS process, arithmetic and logic circuits, including addition circuits, are essentially built out of NAND, NOR, and NOT gates for reasons of solid state physics. Non-monotonic gates (e.g. XOR) are possible if you appropriately buffer the output, but details. Whoever told you that was wrong; a look at any CPU's instruction set reveals a lot of logic and bit manipulation instructions. However, more complex functional units are often made from adder circuits these days, such as multiplication units. See, for example, en.wikipedia.org/wiki/Wallace_tree $\endgroup$– PseudonymApr 26, 2022 at 17:15
-
$\begingroup$ See en.wikipedia.org/wiki/Instruction_set_architecture $\endgroup$– JuhoApr 26, 2022 at 18:33
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
You know something about logic gates since I see them in your question. I believe that computers can do much more than add, but let me play devil's advocate and try to show you that we could think of most of what computers do is adding.
So the main logic gates in classical computers (the ones that use electricity) are "and gates", "or gates", and "not gates". The "and gate" takes two bits and produces a one if both input bits are 1. We could say that this computes the addition of two bits and outputs a one if adding the two bits equals 2. We can prove this by checking each case. If both bits are 0, then clearly their addition does not equal 2, so it outputs a zero. If only one of the bits is 1, and the other bit is zero, these bits only sum to 1 and so the output is also a zero. Finally, if both input bits are 1, their sum is 2 since 1+1=2, and so the gate outputs a 1.
"Or gates" produce an output of 1 if the sum of the input bits is 1 or more. So checking our cases, if both bits are zero, than the sum is 0 and so the output is 0. If the inputs are 1 and 0, then the sum is 1 and so the output is 1. If both input bits are 1, then the sum is 2 and the output is 1.
The "not gate" may be the trickiest gate to think of in terms of addition. The not gate only has one input. It basically switches the input, so its output is "not" its input. We can think of this as adding one, but with a carry bit. If the input is 0, then the output is 0 + 1 = 1. The tricky part is when the input is 1. We can do this, but only in "binary". In binary, adding one plus one gives you 2, but 2 in binary is written as 10, so that the ones digit is zero, as desired.
I think that for arithmetic, @Pseudonym's links show you how to do that.
Their are instructions that tell the computer to go to different parts of the computer program or code. A lot of these use comparison, which use the logic gates I mentioned above, and Boolean algebra. For example, the computer may use an instruction that tells the computer to go to a different part of its instructions if a number is larger than 10. The computer does this by first adding -10 to the input, and then using Boolean algebra to test if this result is greater than zero, which is easy for a computer. It can use Boolean algebra and logic gates for this.
Computers also do things like copying registers (which are just numbers stored in the processor). While this doesn't involve addition, you could think of it as a way of putting a number into the computer's processor so that it can add something the next time that the processor does something.
Well, hopefully this wasn't boring, and that you learned something. There are many ways to think of a computer, and scientists have actually put a fair amount of time into actually defining what a computer is. What scientists came up with is a Turing machine, named after Alan Turing.
$\begingroup$
$\endgroup$
Computers can perform any algorithm using only addition (or even using only the x86 MOV instruction).
But what they have is a set of instructions aiming to maximize performance.
A computer that only use the add operator will be slow in doing multiplication. To get around this, computers have hardware-implemented functions performing binary multiplication and division. But actually the most of instructions executed in the hardware by the code are moves, branches and add/sub operations, as you can see in SPEC CPU2017 Benchmarks.
Logic gates are part of the processor components, but also can be implemented in software, for example: to compare two numbers for equality we can subtract them and check if the result is zero.
$\begingroup$
$\endgroup$
I think the comments answer your question. To add some more context, it also depends on what you define as a computer. If you consider FPGAs and ASICs computers, then there are hard-coded circuits that can perform a variety of logic operations with transistors.
$\begingroup$
$\endgroup$
1
If “the only thing a computer can do is adding”, then a computer can do everything it does just by adding.
But by adding you can’t change a 1 to a 0. There are many things you can’t do just by adding.
What you do need to do anything a computer can do: Perform a NAND operation. Select memory. Produce electrical signals that can be detected outside. (Open to suggestions what else would be needed).
$\begingroup$
$\endgroup$
Presumption: We're talking about CPU.
At the lowest level, we have only logic gates. [We may go even lower than that ;) ]. In that sense even add is a combination of logic operation, else CPUs have much more instructions besides addition.
For arithmetic: subtraction can be represented as a + (-b), multiplication as series of addition and division as series of subtraction. How do we represent negative numbers that's another topic (r's complement).
