Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421990 | Electronic Notes in Theoretical Computer Science | 2008 | 18 Pages |
Abstract
We investigate some basic connections between reverse mathematics and computable analysis. In particular, we show how to use Weak König's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multi-valued function Sep and through the definition of a natural notion of reducibility for multi-valued functions, we obtain a computational counterpart of the subsystem of second order arithmetic WKL0. We study analogies and differences between WKL0 and the class of Sep-computable multi-valued functions. We use these notions to provide a method to determine the computational complexity of the Hahn-Banach Extension Theorem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics