Kurt Gödel Research Center

2016 seminar talk: A Normal Form Theorem of Computation on Real Numbers

Talk held by Yue Yang (National University of Singapore, Singapore) at the KGRC seminar on 2016-04-14.

Abstract

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.