Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
An Analysis of Urysohn and Tietze-Urysohn Lemmas according to Borel Computability

Speaker: Guido Gherardi
Slot: Array, 15:10-15:30, col. 1


K. Weihrauch has studied the computational
properties of Urysohn and Urysohn-Tietze Lemmas within the
framework of TTE-theory of computation. He proved that with
respect to negative information both lemmas cannot in general
determine computable single valued mappings. In this paper we
reconsider the same problem with respect to positive information.
We will see that also in this case both Urysohn Lemma and
Dieudonn\'e version of Tietze-Urysohn Lemma define in general
incomputable functions. We will then analyze the degree of their
incomputability (or more precisely, of the incomputability of
their realizations in Baire space) as is meant in the theory of
Borel computability. In particular, we will see that in $\bbbr$
Urysohn function is $\fS_2$-complete, while
Dieudonn\'e function is $\fS_3$-computable. 

websites: Arnold Beckmann 2006-04-19