کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428689 | 686879 | 2009 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Decision problems for Turing machines
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We answer two questions posed by Castro and Cucker (1989) in [1], giving the exact complexities of two decision problems about cardinalities of ω-languages of Turing machines. Firstly, it is -complete to determine whether the ω-language of a given Turing machine is countably infinite, where is the class of 2-differences of -sets. Secondly, it is -complete to determine whether the ω-language of a given Turing machine is uncountable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 109, Issues 23–24, 15 November 2009, Pages 1223-1226
Journal: Information Processing Letters - Volume 109, Issues 23–24, 15 November 2009, Pages 1223-1226