What is an Expanded Binary Number?

This question could also have been asked as What is the Expanded Binary Notation for a number?

---

The Expanded Binary Notation is one of the five numerical notations discussed in Chapter 2 of Sir Roger Penrose's book The Emperor's New Mind. The other four notations are Unary, Binary, Denary, and Machine State. The last one is not so much a numerical notation as it is the Transition Function for a Turing Machine, but it can be converted to any one of the other notations, and for that reason it can also be thought of as a numerical notation.

---

---

Expanded Binary numbers are similar to Binary Numbers. Both consist only of the digits 0 and 1. It is also quite easy to convert a Binary number to an Expanded Binary number, and vice versa.

---

---

To convert a Binary number to an Expanded Binary number, just follow these two steps:

---

Here are some examples of Binary Numbers converted to Expanded Binary Notation:

---

Also, there may be leading and/or trailing 0's with the number, and its value does not change.

For Example:

00101010110, 101010110000, 001010101100, and 00010101011000000, are all Expanded Binary representations of the same number 7.

---

Of course, the easiest way to convert a Binary Number (especially if it's very large) to an Expanded Binary Number is to use the Notation Converter Excel file which you can download from the Home page of this website.

---

---

To convert an Expanded Binary number to a Binary number, just follow these two steps:

---

Here are some examples of Expanded Binary Numbers converted to Binary Notation:

---

Of course, the easiest way to convert an Expanded Binary Number (especially if it's very large) to a Binary Number is to use the Notation Converter Excel file which you can download from the Home page of this website.

---

---

So, why do we even have the Expanded Binary notation? Couldn't we just get along fine with the Unary, Binary, and Denary notations?

---

In the Turing Machine that's described by Roger Penrose, the paper tape can only have the digits 0 and 1. For that reason, we cannot have data on the tape in Denary Notation.

We can use Unary Notation, and in fact, some of the examples that Roger Penrose gave in his book The Emperor's New Mind use Unary data. (Those same examples are also included in the Excel file that you can download from the Home page of this website.)

The difficulty with using Unary data, however, is that for very large numbers, the number of digits in a Unary number becomes unreasonably huge! (This is not a problem for the ideal Turing Machine, but it may be a difficulty for a human or for a real computer trying to simulate the Turing Machine.) So, the alternative that first comes to mind is to use Binary Numbers. After all, even very large numbers can be expressed in binary without having too many digits.

However, there is a problem with trying to use Binary numbers as data on the paper tape used by a Penrose Turing Machine. The only symbols allowed on the infintely-long paper tape used by this type of Turing Machine are 0 and 1. (In the Excel file that you can download from the Home page, you may see 0's, 1's, and blanks; however, the Turing Machine you then simulate won't be able to tell the difference between a 0 and a blank.)

Suppose you wanted your data to be the binary number 10. If there is no other data to the right of that number, then you will have infinitely many 0's to the right of it. So, how do you know your binary number isn't 100, or 1000, or 10000, etc.

The Expanded Binary Notation does not have this problem. Every number in Expanded Binary Notation ends in 110 so that you can easily tell where the number ends.

---

The Expanded Binary Notation also allows you to put two or more numbers on the tape as data, if that's what your Turing Machine requires. For example, suppose your Turing Machine expects two numbers on the paper tape, and suppose you want your two numbers to be 2 and 3. Then, you can put 1001101010110 and it's clear that your two numbers are 100110 and 1010110 and there's no problem. If you tried to do the same thing using Binary Numbers, you might try writing 1011 with infinitely many 0's to the left and right of this number, and you have no idea where your first number ends and where your second number begins.

---

Ok. So, it's clear how you can tell where an Expanded Binary Number ends. But, don't you also need something at the beginning of the Expanded Binary Number so that you can tell where it starts?

In your example above, your first Expanded Binary number is 100110. But how do you know that that is the entire number? Might it not be possible that, if you looked to the left of that number for about a million places, you might find a 1? Wouldn't that then be the first number, and in fact a very huge number?

---

That will never be a problem, and here's why: One rule to follow in using a Penrose Turing Machine is to place the Turing Machine's Read/Write Head to the left of all the data on the tape. That way, the Turing Machine knows that when it starts running, there is nothing but an infinite number of 0's to the left of the Read/Write Head. It starts running by executing the instruction 00R and moving to the right until it finds the first 1 on the tape, which it then knows is the first digit of the first number on the tape.

If the data on the tape consists of more than one Expanded Binary Number, then it can tell where the 2nd number begins because it knows where the 1st number ended; it can also tell where the 3rd number begins because it knows where the 2nd number ended, etc. Every number in the Expanded Binary Notation ends with 110.

---