Information is physical
Landauer's principle pertains to the lower limit of energy consumption of a computation. It holds that "any logically irreversible manipulation of information, such as the erasure of a bit, must be accompanied by a corresponding entropy increase". Typically this increase takes the form of energy imported into the computer, converted to heat, and dissipated into the environment.
The aim of this thesis is to write an introduction to Landauer's principle for computer scientists. It may also cover related topics such as Maxwell's daemon or reversible computation.
Circuit Complexity
Circuit complexity is a branch of computational complexity theory that classifies functions according to the size of the Boolean circuits that compute them. This is in contrast to the Turing machine based measures that consider the amount of time or space used for the computation.
The aim of this thesis is to write an introduction to circuit complexity that could be given to interested students in the "Berechenbarkeit und Komplexität" lecture.
Proof Complexity
Complexity theory usually measure the cost of solving a computational problem.
In the same spirit, proof complexity studies which is cost of proving a statement in a formal proof system.
This cost is measured by analyzing which is the minimum length that a proof of the statement has.
In this project we will study an introduction to proof complexity and its connections to the P vs NP problem.
Bioinspired Models of Computation
A model of computation is a mathematical object that allows us to study the limits and cost of computing.
The ubiquitous model of computation is Turing Machines, which was proposed by Alan Turing after a exhaustive analysis of what "computing" means.
However, there are other models of computation whose inspiration comes from Biology.
Examples of these models are membrane computing, inspired in the inner structure of cells; cellular automata, inspired in life itself; or virus machines, inspired in the trasmission and replication of viruses.
In this project we will study these biology-inspired models, from a mathematical point of view.
Programming Language Semantics
Assume we are given an algorithm A in a programming language designed to fulfill a task T.
How do we know that after executing A the task T has been correctly fulfilled?
Algorithms are purely syntactical objects (pieces of text), so to understand their execution better we can assign them a meaning (a semantics).
In this project we will define multiple semantics models for programming languages and we will show that they are equivalent.
Degrees of unsolvability
The halting problem is the canonical example of a problem that is unsolvable. But how complex is it compared to other unsolvable problems?
Turing reductions allow us to compare the difficulty of unsolvable problems to each other. This allows us to sort all programs into Turing degrees (or degrees of unsolvability) of programs that are of the same difficulty. The resulting structure of (reducibility) relations between these equivalence classes is quite complicated, and has been a fruitful area of study.
In this project we will describe some of the properties of this structure of unsolvability degrees, including that there exists a computably enumerable degree strictly between that of the computable sets and that of the halting problem (Post's problem).
Other topics in the area of logic and theoretical computer science are also possible. If you would like to propose a topic for a thesis, please contact us.
