کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951268 | 1441199 | 2017 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A small minimal aperiodic reversible Turing machine
ترجمه فارسی عنوان
دستگاه تورینگ کوچک قابل تنظیم کوچک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ماشین تورینگ، سیستم های پویا گسسته، دینامیک نمادین،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A simple reversible Turing machine with four states, three symbols and no halting configuration is constructed that has no periodic orbit, simplifying a construction by Blondel, Cassaigne and Nichitiu and positively answering a conjecture by Kari and Ollinger. The constructed machine has other interesting properties: it is symmetric both for space and time and has a topologically minimal associated dynamical system whose column shift is associated to a substitution. Using a particular embedding technique of an arbitrary reversible Turing machine into the one presented, it is proven that the problem of determining if a given reversible Turing machine without halting state has a periodic orbit is undecidable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 84, March 2017, Pages 288-301
Journal: Journal of Computer and System Sciences - Volume 84, March 2017, Pages 288-301
نویسندگان
Julien Cassaigne, Nicolas Ollinger, Rodrigo Torres-Avilés,