Logic, computability and learning theory

This research project is in mathematical logic and theoretical computer science, more specifically, in the areas of computability and complexity, learning theory, and artificial intelligence. Interestingly, the theory of computation was begun before there were any electronic computers, starting with the work of Kurt Gödel in Vienna in the 1930`s. The history of the subject has revealed that the phenomenon of noncomputability and undecidability pervades all of mathematics and computer science, so the subject remains highly relevant. In complexity theory, one looks at how difficult it is to perform computations, measured in for example time steps. The most important problem is the notorious P versus NP question. Although few people believe that the classes P and NP are equal, nobody to date has been able to prove that they are different. Equality of the two classes would imply disastrous things, such as the possibility of easily breaking all secure internet communication and encrypted bank codes, as well as many happy things, such as the ability of solving search problems in graph theory in a feasible way. An important theme in artificial intelligence is the theory of learning. We can hardly expect a computer to perform intelligent tasks if we do not give it the opportunity to incorporate new information, and the ability to manipulate and interpret data, i.e. ``learn``. Since the 1960`s a large research effort has been spent by people from various disciplines to study models of learning. These studies have revealed intricate connections between artificial intelligence, logic, computability theory, and statistics. Besides a large number of technical issues with a practical potential, this work also comes with a strong philosophical flavour. This is no surprise, because the problem of teaching a computer to learn almost immediately brings us to the question how humans come to knowledge. This research project combines all of the above areas. It investigates logical inference problems connected to learning theory, and the power of various learning models and the connections between them. Furthermore, it incorporates a study of various computability theoretic problems connected to the theory of learning, in particular, problems related to the theory of randomness.