کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421990 | 684999 | 2008 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
How Incomputable is the Separable Hahn-Banach Theorem?
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 221, 25 December 2008, Pages 85-102
Journal: Electronic Notes in Theoretical Computer Science - Volume 221, 25 December 2008, Pages 85-102