# Projects under construction

In the past years I have worked on a number of projects but published little. Here is an overview of some of the projects:

## Information theory

**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’.**Time Symmetry in Turing Machines.**Just like in physics in Information theory it makes sense to study systems that live in negative time. I wrote a nice paper about this with Peter van Emde Boas. The work needs to be extended to a full overview of determnistic and non-deterministic computational architectures in positive and negative time. There appears to bee a whole Zoo of systems with different time symmetries. Here is a sketch of a taxonomy.**Meaningful Information and Creative Systems**. I'm currently working on a computational theory of meaning. I discovered that two-part code optimization is not a good technique for separating data in systems that contain elementary arithmatical functions (See the paper on Informartion and Computation: arXiv). So that part of the paper has to be rewritten. The idea is to develop a formal theory of creativity on the basis of this work and apply this to human cognition. See also my work on painting and visual information. Here is the Draft paper.**Information Conservation Principle.**Together with Amos Golan I investigated standard prefix-free Kolmogorov complexity in the context of Zellner’s information conservation principle (ICP). We showed that prefix-free Kolmogorov complexity K is not efficient in this sense and proposed a generalized version of Kolmogorov complexity. The paper was accepted at Cie 2014 but I'm not completely happy with the result so I decided to retract it. Here is the draft. In the mean time I have discovered the General Law of Conservation of Information (See the paper on Information and Computation arXiv). So the paper has to be rewritten.**Learning by Eaxample.**In order to solve the problems with the previous paper I developed a theory about learning by example: the meaning of an object is the complexity of the simplest example that identifies the object in a certain context. I was able to prove that this theory satisfies Zellners criterion under some strong conditions. I'll probably merge the two papers at some point in time. Here is the draft.**Storing information in a Computational Mechanism.**An investigation into the cost of storing data in a one tape Turing machine. It turns out to be superlinear under mild assumptions. The paper was accepted at Cie 2015 but I'm still not happy with it so I decided to retract it. Here is the paper. It does allow me to estimate the computing power of various computational models, so in that respect it will be a building block of the theory of meaning project described above.

## Philosophy

**Johan Andreas dėr Mouw.**The Dutch Poet\Philosopher Johan Andreas dėr Mouw (1863-1919) has been a life long inspiration for me. For the 2014 dėr Mouw symposium I wrote a philosphical analysis of his esthetics. Here is the paper(in Dutch). Inspired by dėr Mouws notion of absolute idealism I have had plans to write a monographs on the history of Solipisism for years. Here are some notes.

## Current Collaborative Projects

AAA Data Science, Using information theory and complex network theory to understand the structure of very large knowledge graphs, with Frank van Harmelen.

# Recent Collaborative Projects

- Complexity Measures for e-Science (Wp1, Wp2, Data2Semantics, P23, Commit) FInished in 2015.

- Atlas of Complexity Project (Supported by the Templeton Foundation) Finished 2014.