Warum verwenden Computer das Binärzahlensystem (0,1)?

31

Warum verwenden Computer das Binärzahlensystem (0,1)? Warum verwenden sie stattdessen kein ternäres Zahlensystem (0,1,2) oder ein anderes Zahlensystem?

Rai Ammad Khan
quelle
9
Dies ist eine Frage zur Elektrotechnik. Anscheinend sind binäre Gatter einfacher zu implementieren. Im IIRC war irgendwann ein ternärbasierter Computer gebaut worden.
Yuval Filmus
7
Welche Nachforschungen haben Sie angestellt? Wenn ich den Titel Ihrer Frage in Google eingebe, erhalte ich Suchergebnisse mit mehreren Antworten auf Ihre Frage. Auch der Wikipedia-Artikel über Binärzahlen und Binärcode enthält eine kurze Erklärung. Wir erwarten, dass Sie eine erhebliche Menge an Nachforschungen anstellen, bevor Sie hier nachfragen. Mir scheint, Sie haben noch nicht einmal Grundlagenforschung betrieben, bevor Sie gefragt haben. Das Durchsuchen von Google und Wikipedia ist ein absolutes Minimum.
DW
Größere Basen erwiesen sich insgesamt als nicht nützlich.
Raphael
@ Raphael: Ternary hat
Mooing Duck
2
Ich werde dies als Kommentar setzen, da es bereits eine akzeptierte Antwort gibt. Es ist außerordentlich schwierig, elektronische Geräte zu bauen, die aufgrund von Herstellungstoleranzen zuverlässig zwischen zehn Werten unterscheiden. Es ist relativ einfach, elektronische Geräte zu bauen, die zwischen zwei Werten unterscheiden. Die kurze Antwort lautet also, dass Computer aus Gründen der Zuverlässigkeit eine binäre Darstellung verwenden . Ich habe eine detailliertere Antwort für diejenigen geschrieben, die sich interessieren
Bob Brown

Antworten:

31

Da wir in der Informatik sind, antworte ich so: Sie tun es nicht.

Was meinen wir mit einem "Computer"? Es gibt viele Definitionen, aber in der Informatik als Wissenschaft ist die Turing-Maschine die gebräuchlichste.

Eine Turingmaschine wird durch mehrere Aspekte definiert: eine Statusmenge, eine Übergangstabelle, eine Stoppmenge und ein für unsere Diskussion wichtiges Alphabet. Dieses Alphabet bezieht sich auf die Symbole, die das Gerät als Eingabe lesen und auf das Band schreiben kann. (Sie könnten verschiedene Eingabe- und Bandalphabete haben, aber lassen Sie uns diesbezüglich keine Sorgen machen.)

Ich kann also eine Turing-Maschine mit dem eingegebenen Alphabet oder oder{0,1}{a,b}{0,1,2}, or {,}. It doesn't matter. The fact is, I can use any alphabet I choose to encode data.

So, I can say that 0001001 is 9, or I can say that ↑↑↑↓↑↑↓ is 9. It doesn't matter, since they're just symbols we can distinguish.

The trick is that binary is enough. Any sequence of bits can be interpreted as a number, so you can convert from binary to any other system and back.

But, it turns out unary is enough too. You can encode 9 as 111111111. This isn't particularly efficient, but it has the same computational power.

Things get even crazier when you look into alternate models of computation, like the Lambda calculus. Here, you can view numbers as functions. In fact, you can view everything as functions. Things are encoded not as bits, 0s and 1s, but as closed mathematical functions with no mutable state. See the Church numerals for how you can do numbers this way.

The point is that, 0s and 1s is a completely hardware specific issue, and the choice is arbitrary. What encoding you're using isn't particularly relevant to computer science, outside of a few subfields like operating systems or networking.

jmite
quelle
What about input encoding in 2-counters machines. It seems to matter. Are you sure you can dismiss so radically encoding issues? And I would hardly agree that complexity is a non-issue; but is lambda calculus a proper way to address it?
babou
I'll admit that there are complexity problems when you use unary. But the choice of binary vs ternary or anything like that is somewhat arbitrary. It's not like the choice of encoding doesn't matter, but there's not some law dictating why we use a particular one. It's dictated mostly by either convenience or by hardware requirements, which are somewhat outside of computational science.
jmite
1
"So, I can make a Turing machine with input alphabet". I think you should write "tape alphabet" here instead of "input alphabet". The interesting part is what is used for computation and not for input. Furthermore I disagree with unary being enough. A TM with unary tape alphabet is almost useless, because the tape is constant.
Simon S
Regarding the last sentence: design and study of computer hardware and architecture are also part of computer science.
Kaveh
2
You may want to add the point that going from unary to binary cuts down the size of your numbers to their logarithm, which is a serious improvement, while going further doesn't gain as much (only a linear factor).
reinierpost
23

Some other things to consider:

Part of the reason for using a binary number system is that it's the lowest-base number system that can represent numbers in logarithmic, rather than linear, space. To uniquely distinguish between n different numbers in unary, the average length of representations must be proportional to at least n, since there is only one string of length k where k<n; 1+1+...+1=n. To uniquely distinguish between n different numbers in binary, the average length of representations must be proportional to at least log2n, since there are 2k binary numbers of length k; 1+2+...+n+12=n. Choosing a larger base improves on the space requirement by a constant factor; base 10 gets you n numbers with an average representation length of log10n, which is log1020.3 times the average length of a base two representation for all n. The difference between binary and unary is much greater; in fact, it's a function of n. You get a lot by choosing binary over unary; you get much less by choosing a higher base, by comparison.

There is some truth to the idea that it's easier to implement digital logic if we only have to distinguish two states. Electric signals are analog and, as such, can be interpreted to represent as many discrete states as you'd like... but you need more precise (hence expensive and finicky) hardware to reliably distinguish more states over the same range. This suggests choosing as low a base as you can.

Another potentially important consideration is that logic has classically been understood to involve two distinct values: true and false. Now, we have fancier logics than this, but a lot of mathematics and science still rests on pretty foundational notions. When you consider that computers are used to compute, and that logic is important for computation, it suggests having good support for at least two distinct states... but logic doesn't really require more than that.

Patrick87
quelle
9

One of the big reasons that most computer circuits use two states is that the quantity of circuitry necessary to distinguish between n different voltage levels is roughly proportional to n-1. Consequently, having three discernible states would require twice as much circuitry per signal, and having four would require three times as much. Tripling the amount of circuitry while only doubling the amount of information would represent a loss in efficiency.

Note that there are some places in computers where information is stored or communicated using more than two states per element. In a flash memory array, hundreds or thousands of memory cells may be serviced by one set of level-sensing circuitry. Using four levels per cell rather than two when storing a certain amount of information might more than triple the size of the level-sensing circuitry, but would cut by half the number of memory cells required. When communicating over 100-base-T or faster Ethernet, the cost of the circuitry necessary to detect multiple signal levels on the cable will likely be dwarfed by the cost of either having to use a cable with more wires or use cables that can handle more signal transitions per second without an unacceptable level of distortion.

supercat
quelle
9

There do exist quantum computers in research labs that use q-bit as the basic unit of information that can be both 0 and 1 simultaneously.
http://en.wikipedia.org/wiki/Quantum_computer

There have also been ternary quantum computers built as per this reference http://en.wikipedia.org/wiki/Ternary_computer

So, It is indeed possible to build alternative computing devices that do not rely on the binary number system. Fiber optic systems for example use 0 for dark and two different orthoganal polarizations of light as 1 and -1.

The reason why I mention these things is because I want to show that although binary numbers are sufficient for computing, there are alternative number systems that can be used for computing.

The binary number system is nice in these sense we can encode all integers xZ by using radix representation of numbers. http:// en.wikipedia.org/wiki/Radix These values can represent the ASCII code A=0x41=01000001, or the value could represent a machine instruction nop=0x90=0x10010000.

Gary D.
quelle
3
But they are still using a binary system, in quantum computing the state of superposition is not a third possible value. Also throwing out a quantum computing example is not helpful to the question asked.
lPlant
I didn't know about this..
Ali786
"q-bit as the basic unit of information that can be both 0 and 1 simultaneously." This is nonsense. Qubits are fundamentally different from normal bits, in that they represent a non-discrete (complex) value. They are incomparable for all practical purposes.
Discrete lizard
3

At the heart of the digital computers processing power is a transistor, which works like a switch. By raising the current at at the "gate" of the switch, it allows current to flow between the "collector" and "emitter" - the switch is turned on. The transistor will be designed to operate in one of two modes - fully on or fully off ('saturated') - with a clear division of what those states are. The transistor can switch between the two states quickly, will remain in the state with very limited errors.

This circuitry forms the basis for logic devices, such AND, NAND, OR, XOR and other functions. The NAND function being the most basic of the building blocks. These logic devices are assembled to provide processors which remain in a predictable state, and lots of transistors can be packed in a small space to provide the functionality needed.

A transistor can manage multiple, or varying states, but when operating in that manner they do not produce conventional "digital" computers - they do not tend to stay in a predictable state and they are prone to interference, saturation, osculation, etc - so they have limited applications in terms of computational abilities. Op-amps could be considered analog computers.

peeldog
quelle
-3

We only use binary(1,0) because we currently do not have the technology to create "switches" that can reliably hold more than two possible states. (Quantum computers aren't exactly on sale at the moment.) The binary system was chosen only because it is quite easy to distinguish the presence of an electric current from an absense of electric current, especially when working with trillions of such connections. And using any other number base in this system ridiculous, because the system would need to constantly convert between them. That's all there is to it.

Irfan Khan
quelle
2
This is true but isn't it all already included in the existing answers?
David Richerby