Dyadic Encoding

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 set)
  • dya(2n + 1) = dya(n)'1' Odd numbers
  • dya(2n + 2) = dya(n)'2' Even numbers

For example:

Natural Number Dyadic Encoding
1 1
2 2
3 11
4 12
5 21
6 22
7 111


  1. ^ Smullyan, R. M. (1961). Theory of formal systems. Princeton, N. J.: Princeton Univ. Press. 
  2. ^ Classes of Predictable Computable Functions by Robert W. Ritchie

Computational complexity theory