9 ms·
Tunguska: Ternary Computer Emulator (2008)
- jart 6y agoKnuth talks about this jokingly in TAOCP not expecting someone would actually do it. I looked at the screenshots and it's not obvious to me how they map back on to ternary. Like how do you have a hex editor when 16/3=5.333?
- grenoire 6y agoI think, based on this screenshot, it uses some form of nonary encoding: http://tunguska.sourceforge.net/shots/tunguskashot.png http://tunguska.sourceforge.net/shots/tunguskashot.png
- rowanG077 6y agoThe only reason we use hex is because we have binary. With ternary you would maybe use 12 as a base. That's better then 16 anyway since 12 can be divided by 2, 3, 4 and 6.
- klyrs 6y agoHex is 4 bits wide. Base 81 might be a good analog, 4 trits wide, if a bit unwieldy.
- woadwarrior01 6y agoPractical computers based on ternary architectures[1] have been built in the past. [1]: https://en.wikipedia.org/wiki/Setun https://en.wikipedia.org/wiki/Setun
- jart 6y agoYes, it mentions that computer in the footnotes of the Russian translation of TAOCP.
- deleted 6y ago[deleted]
- tyingq 6y agoI always found Charlieplexing[1] an interesting real-world use of tri-state logic. [1] https://en.wikipedia.org/wiki/Charlieplexing https://en.wikipedia.org/wiki/Charlieplexing
- bArray 6y agoFor sure! I remember building this design into a PCB and watching the brains of the inexperienced engineers explode! If you use high/low/input, you can even divide up the input using resistors to get even more input states.
- gwf 6y agoLooking at the documentation, it reads as if the architecture has a proper clock that synchronizes all computation. Furthermore, an emulator would naturally have a global notion of time, synchronously updating all internal states in a linear sweep. However, in hardware this model could be made clockless / asynchronous, such that computations go as fast as they can. The extra state of "unknown" can be interpreted as "not all required inputs are ready yet". Some care would be needed to buffer loops in a recurrent circuit, but that's about the only extra complication.
- shadowofneptune 6y agoThis project appears to be loosely inspired by the Setun series of computers made in the Soviet Union. I can't find any information in English about those being asynchronous designs. The choice of ternary appears to have been made to avoid the signed/unsigned distinction.
- theamk 6y agoI don’t think it will work with trinary numbers though, as in his design “unknown” is treated as “zero”. So if there is an adder which outputs “0”, there is bo way to tell if the computation was done and result was zero, or if it is still in progress.
- gwf 6y agoAgreed, not with this particular design. However, you can absolutely do this just ternary numbers. You loose the ability to encode 3^n states (and are stuck w/ just 2^n), but the middle state can then be repurposed to indicate if the computation is complete (or not) as of yet. I basically used this sort of design in a dual-rail logic framework which had 4 line-states per "data" line pair, two of which were real data bits, a third indicated unknown vs. unknown, and the fourth was unused. See https://core.ac.uk/download/pdf/82751815.pdf https://core.ac.uk/download/pdf/82751815.pdf, but beware that even though it doesn't look at all like ternary numbers in use, it absolute is.
- shadowofneptune 6y ago
- anonymousiam 6y agoThis may be the next phase of computing to keep Moore's Law on track. (Yes, I know it's not actually a law.) Flash memory has been using multi-state cells for a decade or more. All we need is a new ternary logic family (and FPGA/ASIC foundation library), and some good designers that aren't hung up on using only boolean logic.
- alain94040 6y agoHow do you propose to design physical gates that would handle ternary logic, in a way that is more efficient than the current boolean implementation?
- anonymousiam 6y agoGood question. After thinking about it for 30 seconds, I would say add a negative power rail go from there. All gates are analog circuits at the lowest level, so it would not be very difficult to come up a circuit design. I think the main obstacle would be the lack of ternary logic designers. VHDL/Verilog could probably be extended/enhanced to support ternary logic, but there would be a learning curve for the designers.
- theamk 6y agoI don't think that the problem is with the lack of designers. There are companies making specialized chips all the time, so if there were a way to create an efficient ternary circuits, then someone would have made one. For example, AI/neural networks do not care about base (they just need math), and they only need a few types of cells to be useful. But I have not heard of any applications of ternary there. Intuitively, I assume we'd still want to drive transistors to saturation, so we are not dependent on process parameters. Which means that each transistor still only handles two states, and we need two transistors for each trit. But if we have two transistors, we might as well use them for 2 bits and get even more state out of them.
- deleted 6y ago[deleted]
- anonymousiam 6y agoI remember playing with my DefCon 18 badge and thinking to myself, "This looks like ternary. I wonder what it does." After a few minutes groking the (provided, but obfuscated) badge source code, I plugged some values into bc (after setting obase=3), tried them forward and backward (both inverted and normal) and got the "Ninja Party Unlocked!" message on my badge. If only I had known the secret location of the party, I would have tried to get in.
- luizfelberti 6y agoI think ternary computers are an interesting thought excercise, but I've heard on multiple occasions people making serious comments about "ternary computers would be a revolution in computing/efficiency/<something>", and it always sounded like crackpot speculation to me. I'd be interested in hearing a sophisticated counter-argument if anybody has a good one. Here's my take on this: 1. Binary is that smallest base in which we can encode Shannon information, and thus yields to "bits" a more elegant foundation for computation. Choosing any other base sounds like it would be a very arbitrary choice, and to the best of my knowledge, the only other canonical base for computation that inherently makes sense (as in, not arbitrary) aside from the `bit` is the `nat`[0], but since it uses Euler's constant (a transcendental number) it would be (ironically) very unnatural to express "computation" in it. 2. By theorem, all bases are equivalent in power with respect to their capabilities of encoding information and processing/computing said information, and binary logic can be used to bootstrap any other multi-valued logic system desirable (goes for ternary logic and 64-bit integer computation alike). Thus, the decision to make a base-3 falls back pretty much entirely on circuit efficiency ... 3. The claims of computational efficiency, as far as I've been able to observe, are fallaciously constructed by studying their performance characteristics in abstract computer models that are completely detached from computational thermodynamics: 3a. Turing-machines, for example, fail to adequately model real-world constraints due to information locality being one-dimensional (while the real world is 3D). Von-Neumann computers (and other RAM based machine models) are IMO the largest infractor of this — there is no such thing as "RAM" in the real world: you can't access any address space irrespective of locality in O(1), such a computer would violate relativistic physics and thermodynamical constraints, RAM can only exist by making all memory access equally inneficient and mitigating that as much as possible with L3 caches and what not. Semiconductor engineers and chip designers inherently understand this and are aware of die-locality, most computer scientists and software engineers are completely oblivious to this and get to ignore it most of the time [1] 3b. This means that even though anyone can theorize an abstract machine where every discrete "tick" of time will perform a ternary operation in constant time, that doesn't mean such a machine can be efficiently reified if you move it out of the realm of abstraction. We could just as easily theorize a computer that uses base-1T (one trillion), and assume that all "trilliernary" operations execute instantly in discrete ticks of O(1), and voila! We have a computation device that can rival all of Google's data-centers! 3c. In the real world however, there are thermodynamic constraints on how information can "flow" across spacetime, and I have seen absolutely zero evidence that a ternary, trilliernary, or whatevernary logic gate can be constructed without introducing many new voltage levels or other circuit fuckery to counteract this, in a way that wouldn't completely wreck any purported efficiency. It's either that, or we'd implement whatevernary logic using binary gates (which is exactly what 64-bit integer arithmetic already is!) 4. Bottom line and TLDR is this: You can't get more computation[2] for free. Welcome to the real world. --- [0] https://en.wikipedia.org/wiki/Nat_(unit) https://en.wikipedia.org/wiki/Nat_(unit) [1] This is especially painful to watch when they are forced to deal with it, and these optimistic-assumptions clash with reality, as evidenced by NUMA bottlenecks wrt RAM/RDMA/GPUs/Disk access, a collective failure of most engineers to understand the CAP theorem or other concepts related to networking, and so on... [2] And by "computation" I mean it in the thermodynamical, relativistically-physical, information-theoretical kind of way. Physics is a thing we forget about way too often in computer science...
- webmaven 6y agoISTR that ternary computers require a three-phase AC power supply. Is this true? I'm not sure where I picked up the notion (and a cursory search doesn't seem to turn up any supporting evidence), so it's possible that I absorbed this idea from technobabble in some mid-80s or earlier SF novel or TV show.
- turminal 6y agoYour computer's components (other than the power supply) never get in contact with the AC. Components are powered by DC that comes out of the power supply. Laptops running on battery are completely powered by DC in a way. I'm not sure why would that differ in ternary computers.
- magicalhippo 6y agoThat sounds like technobabble. I can't imagine a computer relying on AC, and in any case you can create whatever you need using transistors. After all that's how 12V inverters do it. Heck here's a 12V to three-phase inverter[1] as a random example. [1]: https://www.sigineer.com/product-category/inverter-chargers/three-phase-inverter-charger/ https://www.sigineer.com/product-category/inverter-chargers/...
- patentatt 6y agoIt may be that they would utilize split power rails, and one way of making a split rail power supply is to use a center-tapped transformer, like many linear power supplies for audio amplifiers.
- FullyFunctional 6y agoThinking about Ternary is good at exposing the binary bias we have most programming [languages] (eg., we could have to come with with new concepts to replace &, |, ~, << etc). Worth remembering that the ENIAC was a decimal design but after careful consideration, von Neumann (and pals?) decided that using binary would be more efficient. (Decimal was popular for many reasons). Binary has great noise immunity and all other coding schemes are inherently worse. It's also a lot simpler to make binary gates than ternary.
- MaxBarraclough 6y ago> we could have to come with with new concepts to replace &, |, ~, << etc True, but I imagine it wouldn't impact typical high-level code that much.
- bArray 6y agoEven the states of the ternary computation seem to be up for grabs [1]. My first feeling was that the balanced ternary states would be nice, but as you start building trytes (i.e numbers) the representation doesn't seem great. I couldn't find anything after a very quick search, but if not already done, I want to start referring a ternary bit as a 'tit'! [1] https://en.wikipedia.org/wiki/Ternary_computer#Types_of_states https://en.wikipedia.org/wiki/Ternary_computer#Types_of_stat...
- henry_bone 6y agoIt's actually a trit[1], but I like your thinking. :-) [1] https://en.wikipedia.org/wiki/Trit_(computing) https://en.wikipedia.org/wiki/Trit_(computing)
- andai 6y agoSomewhere down tonight's ternary rabbit hole I found this wonderful Scientific American article, Third Base[0]: The Jewel in the Triple Crown “Perhaps the prettiest number system of all,” writes Donald E. Knuth in The Art of Computer Programming, “is the balanced ternary notation.” As in ordinary ternary numbers, the digits of a balanced ternary numeral are coefficients of powers of 3, but instead of coming from the set {0, 1, 2}, the digits are –1, 0 and 1. They are “balanced” because they are arranged symmetrically about zero. For notational convenience the negative digits are usually written with a vinculum, or overbar, instead of a prefixed minus sign. [0] (pdf) http://bit-player.org/wp-content/extras/bph-publications/AmSci-2001-11-Hayes-ternary.pdf http://bit-player.org/wp-content/extras/bph-publications/AmS...
- peter_d_sherman 6y agoHere's a great paper: "Brousentsov's Ternary Principle, Bergman's Number System and Ternary Mirror-symmetrical Arithmetic" by Alexy Stakhov: https://pdfs.semanticscholar.org/b946/f8ec0c0ffa12427d73940ca5f0ea8e379c8b.pdf https://pdfs.semanticscholar.org/b946/f8ec0c0ffa12427d73940c... Also available here (but apparently behind a registration/paywall of some sort...): https://www.researchgate.net/publication/220458145_Brousentsov's_Ternary_Principle_Bergman's_Number_System_and_Ternary_Mirror-symmetrical_Arithmetic https://www.researchgate.net/publication/220458145_Brousents... Or here: https://ieeexplore.ieee.org/document/8140230 https://ieeexplore.ieee.org/document/8140230 Or, just Google for "Brousentsov's Ternary Principle, Bergman's Number System and Ternary Mirror-symmetrical Arithmetic". Keywords: Ternary Symmetrical Number System, Ternary Tau, Base Phi, Golden Ratio, Fibonnacci, 3-Valued Logic, Number Systems With Transcendental/Irrational Bases, etc., etc.
- taylorfinley 6y agoWhile I acknowledge the considerable risk of being downvoted for schilling a shitcoin, I think if you're this deep in the comments on this subject you might find it interesting that IOTA uses the balanced ternary system. Their reasoning for doing so is explained here: https://iota.stackexchange.com/questions/8/why-does-iota-use-a-ternary-number-system https://iota.stackexchange.com/questions/8/why-does-iota-use...