Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof that all information can be coded in binary?

  1. Aug 15, 2015 #1
    I just got Pinter's book, "A Book of Abstract Algebra", for the modern algebra course that I'm taking. It's a very nice book, I'm enjoying reading through it so far.

    What's especially interesting is the connections to computer science and controls, mostly because I switched to math and physics out of electrical engineering. Anyway, in its introduction chapter on groups, it makes the following statement:

    (Emphasis mine).

    Out of curiosity, I am wondering if there exists a proof of this statement, that is, that any and every single piece of information in the universe, of arbitrary complexity and abstraction, could be encoded as a string of binary digits, assuming one could access that information and had a storage device large enough.

    Intuitively, I would say that it's obvious, a piece of information can be stored in every digit and in theory we can always increase the information capacity by adding digits, but I'm wondering if a rigorous proof exists.

    (Note: I put this in the abstract algebra section because it came up in an abstract algebra textbook, I will understand if the mods feel it is more appropriate in the computer science section).
  2. jcsd
  3. Aug 15, 2015 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    In order to prove it, first you'd have to define "information".
  4. Aug 15, 2015 #3
    I think the statement is intended to convey that "information of any type may be coded in this fashion", or more rigorously "finite information of any type may be represented by a finite binary string", rather than "the set of all sets of information..."

    You can't even measure the position and velocity of every proton in a drop of water, let alone encode it.
  5. Aug 15, 2015 #4


    User Avatar
    Science Advisor

    You could, for example, use Godel numbering to assign a number to every symbol, letter, or formula used in stating the "information", then write that number in binary notation.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Proof that all information can be coded in binary?
  1. Coding Theory. (Replies: 0)

  2. Pi in binary (Replies: 9)