|This article is an orphan, as no other articles link to it. Please introduce links to this page from ; try the Find link tool for suggestions. (September 2011)|
Dyadic Encoding is a form of binary encoding defined by Smullyan 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."
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 set)
- dya(2n + 1) = dya(n)'1' Odd numbers
- dya(2n + 2) = dya(n)'2' Even numbers
|Natural Number||Dyadic Encoding|
- Smullyan, R. M. (1961). Theory of formal systems. Princeton, N. J.: Princeton Univ. Press.
- Classes of Predictable Computable Functions by Robert W. Ritchie