Tunguska the ternary computer emulator

Documentation is a bit sparse at this early stage, but a work-in-progress manual is available here [PDF warning!]. It is also bundled with the tunguska tarball in the doc subdirectory, so you don't have to download it separately if you've already downloaded Tunguska.

The manual contains an introduction to ternary computing, specifications of the machine, a quick start guide, and a brief overview of the functionality of Tunguska.

2. Ternary glossary

3. Articles

This section contains a small series of articles designed to introduce the basic concepts of ternary logic and mathematics. They were originally designed for a blog, but it fizzled out, and they fit this purpose just as well.

Most of this and more is also available in the manual, but these are less technical, and may be more suitable for a general crowd.

Ternary logic: Introduction

First, there was informal logic. Informal logic is basically how we all speak and thing on a day to day level.

Then, (butchering history for the sake of brevity) this man Boole came around and invented a system of formal logic called boolean logic. What he proposed was a two state system -- where things are either true or false. This is the form of logic computers think in, arguably, this brings forth some pretty rectangular logic. It completely breaks down when it's subjected to false dichotomies.

If you ask a computer "Have you stopped beating your wife yet?" -- it must either answer true or false. The computer must give a false answer! You can get around this problem by asking the computer "Can you answer the question 'Have you stopped beating your wife yet?' with your set of logical states?" before asking the question, but that is very alien to human thinking, we just don't walk around asking people if they are capable of answering a question before we ask the question, they will inform you of that when we ask the question itself.

Enter ternary logic. Ternary logic has three states, true, false, and a third state. The third state can be anything -- but it is very useful to assign unknown, or neither, or both. You can use quinary logic (5 state logic) and allow for all five states, but that becomes mathematically cumbersome: True-unknown-false-logic is powerful enough to encompass near human-like thinking, without becoming overly complex.

There are ways of extending standard boolean operators to encompass this new third state, I won't get into them in this post, but you can read more about them in the Tunguska Manual [Part II: Chapter 6].

Ternary mathematics: Balanced bases

Let's touch upon the subject of ternary mathematics. Computers with two states use base 2 (binary). Expressing three states in base 2 is cumbersome, wasteful and downright impractical, so it's easier to use base 3 (ternary or trinary). The naive implementation of the ternary base is to use the digits {0,1,2}, just like our workaday base 10, and digital base 2 -- but there is an extremely neat trick you can do with odd bases: You can balance them. Shift base 3 down one step, and use digits {-1, 0, 1} instead. The benefit of balanced bases is that they can express negative numbers extremely easy, with no wasted states.

Ponder instead a regular, unbalanced base: Binary. In binary, you have a separate bit to express the sign of a number. This gives rise to the very dubious state negative zero. To fix this, two's complement was invented. This fixes the problem of negative zero, but gives rise to a serious eyesore in the design: There will either be more possible positive numbers than negative, or more possible negative numbers than positive.

But! Balanced numbers don't suffer from this problem. They can inherently express sign, with perfect symmetry. In fact, the sign of the most significant digit determines the sign of the number.

There is no obscure voodoo in using a balanced base. All you need to do is shift down the digits, not the meaning of the exponents. In regular ternary, the value of a number a_Na_N-1...a₁a₀ is determined by the series

N = Σ 3ⁿa_n = 3^Na_N + 3^N-1a_N-1 + ... + 3¹a₁ + 3⁰a₀

The exact same series applies to balanced ternary. Balanced ternary has an undeniable intrinsic mathematical beauty to it. There is no need for a minus sign, in fact, the entire mathematical operation that is subtraction becomes merely addition of a negative number.

It's quite cumbersome to express large numbers in ternary, so for the same reason it's common to express binary numbers in hexadecimal, the balanced nonary (base 9) is of special interest. It is twice as compact as balance ternary. A problem I intentionally avoided in discussing negative ternary digits is how to express negative digits with traditional symbols. I'm bringing it up now when the need is even more pressing: Balanced nonary requires four negative digits. There are various conventions, some like to write the digits upside down (not feasible for people trapped in ASCII-land), the convention I prefer is to use A,B,C,D to express -1,-2,-3,-4. Another neat convention is to use Q,W,E,R for the same (because they are directly underneath 1-4 on a QWERTY keyboard.)

So, in closing, some examples of balanced ternary and balanced nonary digits.

9₁₀ = 100_3b = 10_9b
10₁₀ = 101_3b = 11_9b
11₁₀ = 11A_3b = 12_9b
12₁₀ = 110_3b = 13_9b
13₁₀ = 111_3b = 14_9b
14₁₀ = 1AAA_3b = 2D_9b
15₁₀ = 1AA0_3b = 2C_9b
4₁₀ = 11_3b = 4_9b
-2₁₀ = A1_3b = B_9b

Ternary Logic: Operators 1

Extending boolean logic to encompass three states is a fairly simple affair, seeing as how it is trivial to infer many of the results from the results of our old faithful boolean logic. Assume we have some operator O, and we want to know what the result of O(S,Unknown) is, where S is a boolean state -- that is, true or false. We have two possibilities.

(1) → O(S, Unknown) = O(S,True) = O(S, False)

In (2), since we do not know the second argument, we can not tell the result of the operation.

(2) → O(S,Unknown) = Unknown

Let's apply this to extend the boolean OR operator to true-unknown-false logic. We know that

True OR True = True
False OR True = True
True OR False = True
False OR False = False

Since OR is commutative, I will only explore OR(True, Unknown) and OR(False, Unknown) -- order of argument does not matter.

OR(True, Unknown) falls under criteria (1), so OR(True, Unknown) = True. On the other hand, OR(True, False) falls under criteria (2), so OR(False, Unknown) = Unknown. We can use this result to infer that OR(Unknown, Unknown) = Unknown (criteria 2.)

So, the complete truth table for OR in true-unknown-false logic is

True OR True = True
False OR True = True
True OR False = True
False OR False = False
Unknown OR True = True
Unknown OR False = Unknown
True OR Unknown = True
False OR Unknown = Unknown
Unknown OR Unknown = Unknown

The same can be done for AND, with the following result:

True AND True = True
False AND True = False
True AND False = False
False AND False = False
Unknown AND True = Unknown
Unknown AND False = False
True AND Unknown = Unknown
False AND Unknown = False
Unknown AND Unknown = Unknown

The same can be done for XOR, but I'm pulling a Griffiths and leaving that as an exercise for the reader.

It should be said that this system of logic is only one of many possible systems. There is no right system -- only consistent and inconsistent systems (I'm using the term consistency pretty vaguely, for this purpose, let it mean consistent with boolean logic, and not contradicting itself). This system is consistent.

There are a considerable number of ternary operators. There are 16 boolean operators, where 8 of those are commutative. Now, hold on to your hat, because there are a whopping 19,683 ternary operators! This really shows how much more agile the ternary logic system is. 729 of these are commutative.

Ternary Logic: Operators 2 (Formalizing True-Unknown-False)

This post is a bit more mathematical than those before it. It is a requirement, due to the nature of it. If you don't understand it, don't fret. It's purpose is to lay down a more mathematical groundwork behind the system of logic I've been calling true-unknown-false.

Thus far, I've been using the word operator sloppily. In this context, is has nothing to do with mathematical operators. I will now define what I mean by the word. They are functions of sets, returning sets.

The set of all subsets of {T,F} except the zero set, and the set {T,F} itself—that is {{T}, {T,F}, {F}}—is the range and domain of ternary true-unknown-false operators. The objects I've been calling truth values so far are the sets {T}, {T,F}, {F} -- True, Unknown, False respectively.

Def.: A function O is a ternary operator if and only if it satisfies

O(A,B)=V

Where
A ⊆ {T,F}
B ⊆ {T,F}
V ⊆ {T,F}
A,B,V ≠ ∅

Let us define an extension to boolean logic.

Def.: A ternary operation O is an extension to boolean logic if and only if

O({T},{T}) ⊂ {T,F}
O({T},{F}) ⊂ {T,F}
O({F},{T}) ⊂ {T,F}
O({F},{F}) ⊂ {T,F}

or

O(A) ⊂ {T,F} ∀ A ∈ {T,F}x{T,F}

It's not that hard to convince yourself that there are 243 possible extensions to boolean logic, since four degrees of freedom are removed in the definition, there are five left, each with three possible states.

When that is out of the way, let us formalize the selection rule for the true-unknown-false extension to boolean logic.

Def.: A ternary operation O is a true-unknown-false extension if and only if

O(A,{T,F}) = O(A,{T}) ∪ O(A,{F})
O({T,F},B) = O({T},B) ∪ O({F},B)
O({T,F},{T,F}) = O({T,F},{T}) ∪ O({T,F},{T}) ∪
∪ O({T},{T,F}) ∪ O({F},{T,F})

This rule defines a single ternary extension to every boolean operator, making it somewhat obvious that there are a total of 16 ternary operators (one for each bivalent boolean function) that are true-unknown-false operators.

An interesting side note is that it's trivial to extend this system to quaternary true-unknown-false-neither by allowing the zero set in the range and domain.

4. Further reading

Wikipedia has several good articles on ternary logic, numeral systems and computing, which may be worth checking out.

Tunguska

Navigation

Documentation

Table of contents

1. Manual