Logical Approaches to Computational Barriers

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 |