Abstract solving of differential equations: One can prove that under certain boundedness conditions, unique smooth solutions of partial differential equations are computable from the parameters. Moreover, the proof itself essentially is a functional algorithm for doing so. Unfortunately, the algorithm is very inefficient: It is not even possible to obtain any time bounds at all. However, in numerical research specialized algorithms are written for specific differential equations (which can take months), and then run only a few times. Thus, there is a large degree of tolerance for inefficiency before the abstract algorithm would become useless. Goal of the project is to implement the abstract algorithm in order to test whether it produces results on any acceptable time scale. An implementation in a functional language would be rather straight-forward, alternatively the iRRAM package in C++ could be used as the basis. If you would like to learn more about this project suggestion, please contact me (Arno.Pauly@cl.cam.ac.uk). |

A Pauly: "A new introduction to the theory of represented spaces", arXiv:1204.3763, 2013
N. Mueller: "iRRAM - Exact Arithmetic in C++" |

The compendium of Weihrauch-degrees: Computable analysis [1] studies computability on real numbers, closed subsets of Hilbert spaces, probability measures and many more structures. Various problems turn out to be uncomputable. Just as Turing-reducibility is used to compare uncomputability of functions on the natural numbers, Weihrauch-reducibility [2] is used here. Unlike Turing-degrees, there are actually many natural and interesting Weihrauch-degrees - and we continue to identify more. The aim of the project is design and implement and online compendium for Weihrauch-degrees. With a database of degrees of interest as background, the compendium should be able to visually display the degree structure. Transitivity should be used to automatically combine reductions and separations results. Finally, there are some operations on Weihrauch-degrees (think Turing jump) which should be considered. Prior knowledge of a programming language suitable for web applications (Perl, Python, or maybe Java) would be useful. A certain interest in computability theory is required, but learning about Weihrauch-reducibility can easily be done as a (small) part of the project. If you would like to learn more about this project suggestion, please contact me (Arno.Pauly@cl.cam.ac.uk). |

[1] K. Weihrauch: Computable Analysis, Springer 2000.
[2] V. Brattka, M. de Brecht and A Pauly: "Closed Choice and a Uniform Low Basis Theorem", arXiv:1002.2800, 2010 |