A General Theory of Information and Computation
In the coming years I will write down a final summary of some of the research projects I have been working on for the past 45 years. The a preliminary version of the first report on the interaction between Information and Computation has been published this week on arXiv. It offers a new perspective on information theor by treating it as a purely mathematical subject. I'll be teaching a class on part of the material at the ILLC in Amsterdam in January and hope to publish a more robust version in a journal later that year. Some results:
- It offers unifying perspective on information theory developing the subject as a purely mathematical theory (so no narratives about systems of messages or strings of symbols etc.).
- It offers a detailed analysis of the ‘flow of information’ through computational operations: starting with primitive recursion, via elementary arithmetic to polynomial functions and Diophantine equations. So via the MRDP-theorem it is really a general theory about information and computation.
- The theory leads to many new insights and has interesting applications.
1) Flow of information through more complex recursive functions like addition and multiplication is not trivial. Most striking observation: information efficiency of addition is not associative: depending on how we compute a sum of a set of numbers we loose different amounts of information during the process.
2) The theory facilitates a simple information theoretical proof of the Fueter-Polya conjecture: that states that the Cantor pairing function is the only polynomial function that maps N to NxN bijctively.
3) This make the Cantor pairing function a universal measuring device that allows us to study infinite collections of partitions of the set natural numbers. More specifically: via the Cantor pairing function and its generalization we can split any data set into any other amount of data sets with constant costs.
4) This allows us to measure the information in multi dimensional data sets like database tables directly without any conversion costs.
5) On the down side it shows us that there us no hope of finding an optimal split of a data set in a model part and an ad hoc part: In any theory that contains elementary arithmetic these splits come for free. So two-part code optimization does not work for computational theories rich enough to model elementary arithmetic. This point will be addressed in depth in another paper.
6) Using the Cantor function we can describe a polynomial time computable bijection between the set of finite sets of natural numbers and N itself. Thus we have an objective estimate of information in sets of numbers.
7) Point 3) and 6) give us a tool to measure the information in dimensionless objects like large graphs directly without any conversion costs.
8) Combining point 1) and 6) we prove that there is no polynomial function that orders the set of finite sets of numbers on sums: i.e. on can search systematically search for ‘the n-th set of size k’ but not systematically for the ‘n-th set that adds up to k’.