کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4608863 1338388 2008 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An explicit solution to Post's Problem over the reals
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات آنالیز ریاضی
پیش نمایش صفحه اول مقاله
An explicit solution to Post's Problem over the reals
چکیده انگلیسی

In the BSS model of real number computations we prove a concrete and explicit semi-decidable language to be undecidable yet not reducible from (and thus strictly easier than) the real Halting Language. This solution to Post's Problem over the reals significantly differs from its classical, discrete variant where advanced diagonalization techniques are only known to yield the existence of such intermediate Turing degrees. Then we strengthen the above result and show as well the existence of an uncountable number of incomparable semi-decidable Turing degrees below the real Halting Problem in the BSS model. Again, our proof will give concrete such problems representing these different degrees. Finally we show the corresponding result for the linear BSS model, that is over (R,+,-,<) rather than (R,+,-,×,÷,<).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Complexity - Volume 24, Issue 1, February 2008, Pages 3-15