Matthias Schröder: The extensional and the intensional hierarchies over R do not coincide
Abstract: In functional programming, there are essentially two approaches to computability on the real numbers.The extensional approach assumes an idealistic functional language that contains the real numbers as a datatype. The intensional approach uses data structure of ordinary functional languages and encodes real numbers as streams using the signed-digit representation.
It is known that both approaches yield the same classes of Type-1 and Type-2 functionals over the reals. However, whether this is also the case for functionals of type greater than or equal to 3 was an open problem for a long time. Bauer, Escardo and Simpson [1] were the first to discover that there is a relationship to topological properties of the Kleene-Kreisel continuous functionals over the natural numbers N. Normann [2] came up with a purely topological condition on the Kleene-Kreisel spaces that is equivalent to the Coincidence Problem.
In this talk, I will show that the Kleene-Kreisel space NNN does not satisfy Normann's equivalence condition. By Normann's result, this proves that the extensional hierarchy and the intensional hierarchy of functionals over the reals do not agree from the first previously unknown level on. I will also present an example of a Type-3 functional that is 'extensional', but not 'intensional'.
References:
- [1] A.Bauer, M.Escardo, A.Simpson: Comparing Functional Paradigms for Exact Real-number Computation. Proc. ICALP '02, Lecture Notes in Computer Science 2380 (2002), 488--500.
- [2] D.Normann: Comparing Hierarchies of Total Functionals. Logical Methods in Computer Science 1 (2:4) (2005), 1--28.
