4.5: How to Code a Sequence of Numbers
- Page ID
- 9704
Suppose we have a finite sequence of numbers, maybe
\[2, 4, 3, 5, 9\]
and we wish to code them up as a single number. An easy way to do this would be to code the sequence into the exponents of the first few prime numbers and then multiply them together:
\[2^2 \cdot 3^4 \cdot 5^3 \cdot 7^5 \cdot 11^9 = 1605016087126798500.\]
This would be easy, but unfortunately it will not suffice for our purposes, so we'll have to be a little sneakier. Fortunately, by being clever now, life will be simpler later, so it seems to be worth the effort.
You're probably thinking that it would be easy to decide if a number was a code for a sequence. Obviously \(72 = 2^3 3^2\) wants to be the code for the sequence \(3, 2\), and the number 10 is not a code number, since \(10 = 2 \cdot 5\) is not a product of the first few primes.
Sorry.
Your perfectly fine idea runs into trouble if we try to code up sequences that include the number 0. For example if we were to code up the sequence
\[1, 0, 1\]
we would get \(2^1 \cdot 3^0 \cdot 5^1 = 10\), and so 10 should be a code number. But your idea about coding things as exponents really was a good one, and we can save it if we just agree that whenever we wish to code a finite sequence of numbers \(a_1, a_2, \ldots, a_k\), we will use the exponents \(a_1 + 1, a_2 + 1, \ldots, a_k + 1\), which takes care of those pesky 0's. Furthermore, when we decode we will automatically subtract one from every exponent, so you'll never have to think about it. (Hey, that's why we, the authors, are paid the big bucks!)
The idea here is that a sequence of \(k\) natural numbers should be coded by a product of the first \(k\) primes raised to non-zero powers. So the empty sequence will, naturally, be coded by a product of the first 0 primes raised to some power. In other words, the code of the empty sequence will be the number 1. Let us make this more formal:
The function \(p\) is the function mapping the natural numbers to the natural numbers, where \(p \left( 0 \right) = 1\) and \(p \left( k \right)\) is the \(k^\text{th}\) prime for \(k \geq 1\). Thus \(p \left( 0 \right) = 1\), \(p \left( 1 \right) = 2\), \(p \left( 2 \right) = 3\), and so on. We will often write \(p_i\) instead of \(p \left( i \right)\).
Let \(\mathbb{N}^{< \mathbb{N}}\) denote the set of finite sequences of natural numbers.
We define the coding function \(\langle \cdot \rangle : \mathbb{N}^{M \mathbb{N}} \rightarrow \mathbb{N}\) by
\[\langle \left( a_1, a_2, \ldots, a_k \right) \rangle = \begin{cases} \begin{array}{ll} 1 & \text{if} \: k = 0 \\ \Pi_{i=1}^k p_i^{a_i + 1} & \text{if} \: k > 0 \end{array} \end{cases}\]
where \(p_i\) is the \(i^\text{th}\) prime number.
We will write \(\langle a_1, a_2, \ldots, a_k \rangle\) rather than \(\langle \left( a_1, a_2, \ldots, a_k \right) \rangle\).
It would be pointless to be able to code up sequences without being able to decode them, and the next functions that we define will let us do that. But before getting there, we need to acknowledge that we will be depending on the Fundamental Theorem of Arithmetic, which states that every positive integer greater than one can be expressed in exactly one way (up to order) as a product of primes. The proof of this theorem (first proven by Euclid) is nontrivial and beyond the scope of this book, but is certainly worth looking up. But we will happily remember that the theorem is true, and use it freely.
There is, however, a messy detail with which we have to deal, and we might as well deal with it now.
Our decoding functions will have to be total functions, by which we mean that each of the functions will have domain \(\mathbb{N}\). But lots of natural numbers are not the code of sequences, and we have to figure out how to deal with such numbers. To make the definitions that are coming up reasonable, and to save us more difficulties later, we start by defining the set of numbers that are codes.
Let \(C = \{ a \in \mathbb{N} | \left( \exists s \in \mathbb{N}^{< \mathbb{N}} \right) a = \langle s \rangle \}\). We will call \(C\) the set of code numbers.
Notice that it is easy to check whether or not \(a \in C\). All we need to do is factor \(a\) and see if either \(a = 1\) or if \(a\) is a product of the first few primes.
Now we can get along to uncoding:
The function \(| \cdot | : \mathbb{N} \rightarrow \mathbb{N}\) is defined by
\[| a | = \begin{cases} \begin{array}{ll} k & \text{if} \: a \in C \: \text{and} \: a = \langle a_1, a_2, \ldots, a_k \rangle \\ 0 & \text{otherwise} \end{array} \end{cases}\]
If \(a\) is a code number, we will say that \(| a |\) is the length of \(a\).
Chaff: Ok, where did we use the Fundamental Theorem of Arithmetic?
Notice that we have defined the function \(| \cdot |\) in such a way that its domain is the entire set of natural numbers. Since lots of natural numbers will not be codes of finite sequences, we have had to make a choice about how we would define our length function on those numbers. So, by definition, if \(a\) is any number that is not of the form \(p_1^{a_1 + 1} p_2^{a_2 + 1} \ldots p_k^{a_k + 1}\), then \(| a | = 0\). But we will not talk about the length of such a number.
Please be careful about the difference between \(| a |\) and \(| \langle a \rangle |\). See Exercise 2.
For each \(i \in \mathbb{N}\) with \(i \geq 1\), let \(\left( \cdot \right)_i\) be the function with domain \(\mathbb{N}\) and codomain \(\mathbb{N}\) defined by
\[\left( a \right)_i = \begin{cases} \begin{array}{ll} a_i & \text{if} \: a \in C \: \text{and} \: a = \langle a_1, a_2, \ldots, a_k \rangle \: \text{and} \: 1 \leq i \leq k \\ 0 & \text{otherwise} \end{array} \end{cases}\]
The skeptical (and sharp-eyed) reader will have noticed another little detail here. Consider the number \(a = 10\). We have agreed that 10 does not code up a sequence, and thus Definition 4.5.5 tells us that \(| 10 | = 0\). However, if we use our decoding function that we have just defined, maybe looking for the seventh term of the sequence, and we plug in the input 10, we find \(\left( 10 \right)_7 = 0\). This is slightly annoying, since the casual observer might think that 10 is supposed to code a sequence of length 0, but beyond aggravating the authors, this side effect will not bother us at all.
We will also need to be able to put the codes of two sequences together, one after the other, and the next function allows us to do so.
The function \(^\frown : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) is defined by
\[a ^\frown b = \begin{cases} \begin{array}{ll} \langle a_1, \ldots, a_k, b_1, \ldots, b_l \rangle & \text{if} \: a = \langle a_1, \ldots, a_k \rangle \: \text{and} \: b = \langle b_1, \ldots, b_l \rangle, \\ & \: \: \: \: \text{with} \: \left( a_1, \ldots a_k \right) \in \mathbb{N}^{< \mathbb{N}} \: \text{and} \\ & \: \: \: \: \left( b_1, \ldots, b_l \right) \in \mathbb{N}^{< \mathbb{N}} \\ 0 & \text{otherwise} \end{array} \end{cases}\]
It might be worthwhile to work through an example at this point. Suppose we wished to compute \(793800 ^\frown 73500\). We would first do a lot of factoring to find that \(793800 = 2^3 3^4 5^2 7^2\), so \(793800 = \langle 2, 3, 1, 1 \rangle\). Similarly, \(73500 = \langle 1, 0, 2, 1 \rangle\). So, by definition
\[793800 ^\frown 73500 = \langle 2, 3, 1, 1, 1, 0, 2, 1 \rangle = 2^3 3^4 5^2 7^2 11^2 13^1 17^3 19^2 = 2214592288108200,\]
while \(793801 ^\frown 73500 = 0\).
The functions introduced above allow us to code finite sequences and, given a code number \(a\), decode it. In other words, if \(a \in C\) and \(a = \langle a_1, \ldots, a_k \rangle\), then for each \i\) such that \(1 \leq i \leq | a |\), \(\left( a \right)_i = a_i\).
At this point, we have built all of the coding apparatus that we will need. Whether we approach incompleteness through formulas or through computations, we will be able to code and decode the objects and sequences of the objects. We have built the infrastructure. In Chapters 5 and 6 we will apply the coding to formulas, while in Chapter 7 we use the coding on computations. Both routes lead us to incompleteness.
Exercises
- Compute the following:
(a) \(\langle 3, 0, 4, 2, 1 \rangle\)
(b) \(\left( 16910355000 \right)_3\)
(c) \(| 16910355000 |\)
(d)\(\left( 16910355000 \right)_{42}\)
(e) \(\langle 2, 7, 1, 8 \rangle ^\frown \langle 2, 8, 1 \rangle\)
(f) \(17 ^\frown 42\) - Find a number \(a\) such that \(| a | \neq | \langle a \rangle |\) or prove that no such \(a\) exists. Then find a number \(b\) such that \(| b | = | \langle b \rangle |\) or prove that no such \(b\) exists.