Theoretical Computer Science
big-list encoding examples
Updated Sat, 21 May 2022 06:45:24 GMT

Examples in which the size of the alphabet ($\geq 2$) used for an encoding matters

Let $\Sigma$ be an alphabet, ie a nonempty finite set. A string is any finite sequence of elements (characters) from $\Sigma$. As an example, $ \{0, 1\}$ is the binary alphabet and $0110$ is a string for this alphabet.

Usually, as long as $\Sigma$ contains more than 1 element, the exact number of elements in $\Sigma$ doesn't matter: at best we end up with a different constant somewhere. In other words, it doesn't really matter if we use the binary alphabet, the numbers, the Latin alphabet or Unicode.

Are there examples of situations in which it matters how large the alphabet is?

The reason I'm interested in this is because I happened to stumble upon one such example:

For any alphabet $\Sigma$ we define the random oracle $O_{\Sigma}$ to be an oracle that returns random elements from $\Sigma$, such that every element has an equal chance of being returned (so the chance for every element is $\frac{1}{|\Sigma|}$).

For some alphabets $\Sigma_1$ and $\Sigma_2$ - possibly of different sizes - consider the class of oracle machines with access to $O_{\Sigma_1}$. We're interested in the oracle machines in this class that behave the same as $O_{\Sigma_2}$. In other words, we want to convert an oracle $O_{\Sigma_1}$ into an oracle $O_{\Sigma_2}$ using a Turing machine. We will call such a Turing machine a conversion program.

Let $\Sigma_1 = \{ 0, 1 \}$ and $\Sigma = \{ 0, 1, 2, 3 \}$. Converting $O_{\Sigma_1}$ into an oracle $O_{\Sigma_2}$ is easy: we query $O_{\Sigma_1}$ twice, converting the results as follows: $00 \rightarrow 0$, $01 \rightarrow 1$, $10 \rightarrow 2$, $11 \rightarrow 3$. Clearly, this program runs in $O(1)$ time.

Now let $\Sigma_1 = \{ 0, 1 \}$ and $\Sigma = \{ 0, 1, 2 \}$. For these two languages, all conversion programs run in $O(\infty)$ time, ie there are no conversion programs from $O_{\Sigma_1}$ to $O_{\Sigma_2}$ that run in $O(1)$ time.

This can be proven by contradiction: suppose there exists a conversion program $C$ from $O_{\Sigma_1}$ to $O_{\Sigma_2}$ running in $O(1)$ time. This means there is a $d \in \mathbb{N}$ such that $C$ makes at most $d$ queries to $\Sigma_1$.

$C$ may make less than $d$ queries in certain execution paths. We can easily construct a conversion program $C'$ that executes $C$, keeping track of how many times an oracle query was made. Let $k$ be the number of oracle queries. $C'$ then makes $d-k$ additional oracle queries, discarding the results, returning what $C$ would have returned.

This way, there are exactly $|\Sigma_1|^d = 2^d$ execution paths for $C'$. Exactly $\frac{1}{|\Sigma_2|} = \frac{1}{3}$ of these execution paths will result in $C'$ returning $0$. However, $\frac{2^d}{3}$ is not an integer number, so we have a contradiction. Hence, no such program exists.

More generally, if we have alphabets $\Sigma_1$ and $\Sigma_2$ with $|\Sigma_1|=n$ and $|\Sigma_2|=k$, then there exists a conversion program from $O_{\Sigma_1}$ to $O_{\Sigma_2}$ if and only if all the primes appearing in the prime factorisation of $n$ also appear in the prime factorisation of $k$ (so the exponents of the primes in the factorisation doesn't matter).

A consequence of this is that if we have a random number generator generating a binary string of length $l$, we can't use that random number generator to generate a number in $\{0, 1, 2\}$ with exactly equal probability.

I thought up the above problem when standing in the supermarket, pondering what to have for dinner. I wondered if I could use coin tosses to decide between choice A, B and C. As it turns out, that is impossible.


There are some examples in formal language theory where 2-character and 3-character alphabets give qualitatively different behaviors. Kozen gives the following nice example (paraphrased):

Let the alphabet be $\Sigma$ = {1,..,k} with the standard numerical ordering, and define sort(x) to be the permutation of the word x in which the letters of x appear in sorted order. Extend sort(A) = { sort(x) | x $\in$ A }, and consider the following claim:

If A is context-free then sort(A) is context-free.

This claim is true for k = 2, but false for k $\ge$ 3.

External Links

External links referenced by this document: