A Normal Form Theorem of Computation on Real Numbers

14.04.2016 15:00 - 16:30

Y. Yang (National U of Singapore, SG)

We define a class of computable functions over real numbers using functional schemes similar to the class of primitive and partial recursive functions defined by Gödel and Kleene. We show that this class of functions can also be characterized by master-slave machines. The proof of the characterization gives a normal form theorem in the style of Kleene; and the equivalence itself illustrates that this characterization is a natural combination of two most influential theories of computation over real numbers, namely, the type-two theory of effectivity (TTE) (see, for example, Weihrauch's book) and the Blum-Shub-Smale model of computation (BSS).

This is a joint work with Keng Meng Ng from Nanyang Technological University, Singapore and Nazanin Tavana from Amirkabir University of Technology, Iran.

Organiser:

KGRC

Location:
SR 101, 2. St., Währinger Str. 25