Basic Concepts 2 – Number Systems

File:Babylonian numerals.svg

In one of the next articles, I am going to need several number systems, like decimal, binary (or dual) and ternary. If you are familiar with the idea, you can safely skip this article.

There are different ways to construct a notation for natural numbers. One could represent natural numbers using just one sign. One could write 1 as |, 2 as ||, 3 as |||, 4 as |||| and so on. However, in such a notation, the strings of characters to represent numbers would become very long and difficult to read. Addition and subtraction would be easy in such a notation, but it would not really be convenient. Since ancient times, people have tried to find notations for numbers that are more compact. An early attempt, from Babylonian cuneiform, can be seen on the picture above. Here a new sign is introduced for “10”. Later, the invention of the zero made possible the place value systems we are using today.

We are used to represent natural numbers in the decimal number system. This system to write numbers uses 10 different digits: 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. When we write numbers down using this system, each digit in a number has a different place value. The rightmost digit has the place value 1, each following digit has a place value that is 10 times the place value of the digit before it, so the place values are 1, 10, 100, 1000 and so on. These are powers of 10.

In the same way, we can write natural numbers as binary numbers. Here the base of the system is not 10 but 2. We have only two digits: 0 and 1. The place values of the digits are powers of 2, i.e. we start again with a place value of 1, and double the place value with each further digit. So the place values are 1, 2, 4, 8, 16, 32 etc.

Numbers written in the binary system are sequences of only ones and zeros. To calculate the decimal value of a dual number, you have to multiply each digit with its place value and add the results, for example, the number 100111 is (“decoding” it from right to left): 1 * 1 + 1 * 2 + 1* 4 + 0 * 8 + 0 * 16 + 1 * 32 = 39.

Binary counting goes: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, and so on. (read: zero, one, zero-one, one-one etc., note that binary 10 is not ten, but two.

To calculate the binary representation of a decimal number like 39, you have to divide it by 2 (the base of the binary system) with a remainder. Then you divide the result again, and so on, until you arrive at 0. The remainder gives you the next digit, from right to left:

39 / 2 = 19 remainder 1

19 / 2 = 9 remainder 1

9 / 2 = 4 remainder 1

4 / 2 = 2 remainder 0

2 / 2 = 1 remainder 0

1 / 2 = 0 remainder 1

Result: 100111 (one-zero-zero-one-one-one).

Binary numbers are inconvenient for humans to use since they tend to become quite long and confusing to read. But the binary system is commonly used inside computers because it is easy to build hardware parts that can switch between just two states in order to store or process numbers or other data.

In the ternary system, we represent numbers using three digits: 0, 1 and 2. The place values are powers of 3, starting with 1 and increasing threefold with each successive place, so they are 1, 3, 9, 27, 81 etc. The procedures for converting from ternary numbers to decimal and vice versa are analogous to the binary system. In converting ternary numbers to decimal numbers, you have to multiply each digit with its ternary place value and then add. To go from decimal numbers to ternary numbers, you divide by three, with remainder. For example, to get the ternary representation of the decimal number 18 we calculate:

18 / 3 = 6 remainder 0

6 / 3 = 2 remainder 0

2 / 3 = 0 remainder 2

Result: 200 (two-zero-zero)

The ternary system is unusual, but I am going to use it for a special purpose in one of the next articles – to define a simple and fast way to produce Gödel numbers (I will then explain what that is).

(The picture is from https://commons.wikimedia.org/wiki/File:Babylonian_numerals.svg)

Advertisements

8 comments

  1. I am tagging this article as “Mathematics” and “Philosophy”. It is not philosophical in itself, but I am going to use these concepts in an argumentation that has philosophical implications. Inside this line of thought, the concepts from this article are just a small technical detail, but I want to divide the whole line of thought into very small, almost trivial steps so that people without much mathematical background can follow the argument.
    The whole line of thought is simple, but formulated the way normally used in mathematics, all these small technical details are skipped, so it becomes difficult to understand for people who don’t know them. I want to pick up the people where they are standing. If you find this stuff trivial, just skip it.

  2. Next, I am going to sketch how any data is represented in binary form inside computers. I will then show how mapping the binary data onto ternary numbers can provide an easy and efficient way to define Gödel numbers for such data. Gödel numbers enable us to replace all programs that transform arbitrary types of data with equivalent programs that have natural numbers as their inputs and outputs. I will have to take a closer look into the concept of programs. I will intuitively discuss computability and Turing machines, but will not give an exact description of them (somebody interested in that can find that in textbooks or online). I will discuss Turing enumerability and then show, by using the diagonal method, that the set of all programs calculating total functions of natural numbers is not Turing enumerable. We can map this result back into programs calculating functions on arbitrary data. A program enumerating other programs may be viewed as a learning algorithm. A program calculating a total function can be interpreted as a piece of knowledge…

  3. “In the ternary system, we represent numbers using three digits: 0, 1 and 3.”

    Isn’t it 0, 1, and 2?

    1. LOL.
      Thanks for proofreading, I have corrected it.
      I could pretend now that was a test if anybody was really reading this, but it wasn’t. 🙂 I guess it was actually a typing error.

      1. I think I see where you’re going with this series. It reminds me of a series I wrote last fall:
        http://logosconcarne.com/2015/11/13/information-processing/
        (There’s an index to the previous posts at the end of that post.)

        One thing I love about number bases is that you can use a base large enough to encode text as a number. If you use base 256, you can just use UTF-8 as your symbol set. That allows you to treat any text (globally!) as a single ginormous number.

        A seriously ginormous number, but an integer nonetheless. Which means the natural number line is dotted with viable texts, some written and some yet to be written.

        The number line in its entirety contains every text possible, including ones with misspellings, but most of them pure gibberish. Jorge Luis Borges wrote a story, The Library of Babel, which references the idea. Every number is a text in some encoding scheme.

        1. My next post will be about Gödel numbers. One way to define them is to treat each character in a text as a digit. If you have a character set with n digits, you can use an n+1-ary number system, avoiding leading zeros that would lead to ambiguity. I am going to do that with binary data (hence I need the ternary numbers). Of course there are many shemes you can use to define Gödel numbers but this one is easy and could be efficiently implemented in both directions.
          Borge’s story is in my library, but I don’t have it at hand (I am currently spending the week in another city for reasons of work).

          1. You’re assigning Gödel numbers to binary data through an encoding? I don’t understand why not use the (binary) number formed by the data itself?

            1. To asign different Gödel numbers to binary sequences with different numbers of leading zeros, just see the article I have just published this moment: https://creativisticphilosophy.wordpress.com/2016/02/29/basic-concepts-4-godel-numbers/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: