کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436473 | 690006 | 2008 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bounding lemmata for non-deterministic halting times of transfinite Turing machines
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We use the methods of descriptive set theory and generalized recursion theory to prove various Bounding Lemmata that contribute to a body of results on halting times of non-deterministic infinite time Turing machine computations. In particular we observe that there is a Uniform Bounding Lemma which states that if any total algorithm halts before the first ordinal admissible in the input x, then there is a recursive ordinal γ by which the algorithm halts on all inputs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 394, Issue 3, 8 April 2008, Pages 223-228
Journal: Theoretical Computer Science - Volume 394, Issue 3, 8 April 2008, Pages 223-228