Dyadic Encoding
Dyadic Encoding is a form of binary encoding defined by Smullyan[1] commonly used in computational complexity theory '1's and '2's that is bijective and has the "technical advantage, not shared by binary, of setting up a one-to-one correspondence between finite strings and numbers."[2]
Dyadic encoding works by using a recursive definition of concatenating strings of '1's and '2's together using the following formula.
- dya(0) = ξ (empty string)
- dya(2n + 1) = dya(n)'1' Odd numbers
- dya(2n + 2) = dya(n)'2' Even numbers
For example:
| Natural Number | Dyadic Encoding |
|---|---|
| 0 | ξ (empty string) |
| 1 | 1 |
| 2 | 2 |
| 3 | 11 |
| 4 | 12 |
| 5 | 21 |
| 6 | 22 |
| 7 | 111 |
The numerical value [math]\displaystyle{ n }[/math] of a string [math]\displaystyle{ d_k\cdots d_2d_1 }[/math] with [math]\displaystyle{ d_i\in\lbrace 1,2 \rbrace }[/math] is given by [math]\displaystyle{ n=d_k \cdot 2^{k-1}+\ldots+d_2 \cdot 2+d_1 }[/math]. As the above recursive construction implies, each positive integer is uniquely represented in this way.
References
- ↑ Smullyan, R. M. (1961). Theory of formal systems. Princeton, N. J.: Princeton Univ. Press. https://archive.org/details/theoryofformalsy0000smul.
- ↑ Classes of Predictable Computable Functions by Robert W. Ritchie
Computational complexity theory
 |
