Computability Theory

A3 Decadic Notation

There is a simple and natural one-to-one correspondence between the set of all strings

over a finite alphabet and the set of natural numbers. The key to the correspondence is

to use base-n notation, where n is the size of the alphabet, but without a 0 digit.

Suppose that 6 is a finite set of size n. We refer to 6 as the alphabet, we refer to

the members of 6 as letters, and we refer to finite strings of letters as words (over 6).

Let 6

∗

be the infinite set of all words (including the empty word λ). For example, if

6 = {1, 2}, then

6

∗

= {λ, 1, 2, 11, 12, 21, 22, 111, 112, 121, . . .}.

We assume that the members of the alphabet 6 are ordered in some way (referred

to as alphabetic order). Thus, we have a function v : 6 → {1, . . . , n}