Dyadic Encoding

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 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

References

  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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Minkowski's question mark function — Minkowski question mark function. ?(x) is on the left and ?(x) x is on the right. In …   Wikipedia

  • Interpersonal deception theory — (IDT) attempts to explain the manner in which individuals deal with actual or perceived deception on the conscious and subconscious levels while engaged in face to face communication. Communication is not static; it is influenced not only by one… …   Wikipedia

  • Data compression — Source coding redirects here. For the term in computer programming, see Source code. In computer science and information theory, data compression, source coding or bit rate reduction is the process of encoding information using fewer bits than… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Augmentative and alternative communication — An AAC user indicates a series of numbers on an eye gaze communication board in order to convey a word. Augmentative an …   Wikipedia

  • Quaternion — Quaternions, in mathematics, are a non commutative extension of complex numbers. They were first described by the Irish mathematician Sir William Rowan Hamilton in 1843 and applied to mechanics in three dimensional space. They find uses in both… …   Wikipedia

  • Binary numeral system — Numeral systems by culture Hindu Arabic numerals Western Arabic (Hindu numerals) Eastern Arabic Indian family Tamil Burmese Khmer Lao Mongolian Thai East Asian numerals Chinese Japanese Suzhou Korean Vietnamese …   Wikipedia

  • Simply typed lambda calculus — The simply typed lambda calculus (lambda^ o) is a typed interpretation of the lambda calculus with only one type combinator: o (function type). It is the canonical and simplest example of a typed lambda calculus. The simply typed lambda calculus… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”