Tunguska

Navigation

Documentation

Table of contents

  1. Manual
  2. Ternary glossary
  3. Articles
    1. Ternary logic: Introduction
    2. Ternary mathematics: Balanced bases
    3. Ternary logic: Operators 1
    4. Ternary logic: Operators 2 (Formalizing True-Unknown-False)
  4. Further reading

1. Manual

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

Trit
Ternary analog to bit. The extra 'r' is added for obvious reason. Now only Norwegians giggle at the word.
Tryte
Ternary analog to byte. In this machine, 6 trits, a total of 729 states (-364 through 364).
Word
2 trytes, in this machine 12 trits, with a total of 531441 states (-265720 through 265720).

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 aNaN-1...a1a0 is determined by the series

N = Σ 3nan = 3NaN + 3N-1aN-1 + ... + 31a1 + 30a0

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.

910 = 1003b = 109b
1010 = 1013b = 119b
1110 = 11A3b = 129b
1210 = 1103b = 139b
1310 = 1113b = 149b
1410 = 1AAA3b = 2D9b
1510 = 1AA03b = 2C9b
410 = 113b = 49b
-210 = A13b = B9b

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.

O(S,True) = O(S, False) (1)
O(S,True) ≠ O(S, False) (2)
In (1), it is not hard to convince yourself that the latter argument does not matter, it will always have the same value, then we do not need to know whether the latter argument is true or false -- we automatically know the result.

(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.


©opy(direction) 2008 Viktor Lofgren <vlofgren(Q)gmail.com>
Get tunguska at SourceForge.net. Fast, secure and Free Open Source software downloads