Room P3.10, Mathematics Building

Manuel Campagnolo, ISA - TU Lisbon / SQIG - IT

A characterization of computable analysis on unbounded domains using differential equations

The functions of computable analysis are defined by enhancing normal Turing machines to deal with real number inputs. One can consider characterizations of these functions using function algebras, known as real recursive functions. Since there are numerous incompatible models of computation over the reals, it is interesting to find that the two very different models we consider can be set up to yield exactly the same functions. Bournez and Hainry used a function algebra to characterize computable analysis, restricted to the twice continuously differentiable functions with compact domains. Campagnolo and Ojakian found a different (and apparently more natural) function algebra that also yields computable analysis, with the same restriction. In this talk I will describe an improvement of earlier work, finding three function algebras characterizing computable analysis, removing the restriction to twice continuously differentiable functions and allowing unbounded domains. One of these function algebras is built upon the widely studied real primitive recursive functions. Furthermore, the proof uses the previously developed method of approximation, whose applicability is further evidenced by those results. This talk reports on joint work with Kerry Ojakian.