Information Theory

Von Neumann said that there are two parts to information theory: the rigorous and the probabilistic. The probabilistic part is probably more important for modern computing machinery, but the rigorous part is a necessary preliminary to it. The rigorous part of information theory is just a different way of dealing with formal logics.

He then explained some of the basic ideas of formal logic. He discussed briefly truth-functional connectives such as "and", "not", "if ... then" and "not both" and their interdefinability. He explained the idea of a variable and the quantifiers "all" and "some". He concluded: "If you have this machinery, you can express anything that is dealt with in mathematics; or that is dealt with in any subject, for that matter, as long as it' s dealt with sharply."

I am not going to go into this subject, because in order to make a theory of information, another machinery which is quite closely related to this but looks somewhat different, is more cogent. This is connected with the work of McCulloch and Pitts, on the one hand, and the logician Turing on the other. Both endeavors in the subject replace formal logics as indicated here and as classically pursued by the discussion of certain fictitious mechanisms or axiomatic paper automata, which are merely outlined, but which nobody is particularly concerned to build. Both of them show that their fictitious mechnisms are exactly co-extensional with formal logics; in other words, that what their automata can do can be described in logical terms and, conversely, that anything which can be described rigorously in logical terms can also be done by automata. [Von Neumann was assuming that a finite McCulloch-Pitts neuron net is supplied with an infinite blank tape. The result to which he referred is the equivalence of Turing computability, λ-definability, and general recursiveness. See Turing's "Computability and λ-Definability."]

⇒ Algebra + Statistics = ?