کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950647 | 1364296 | 2017 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the computational power of networks of polarized evolutionary processors
ترجمه فارسی عنوان
در قدرت محاسباتی شبکه های پردازش تکاملی قطبی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پردازش تکاملی قطبی، نقشه برداری ارزیابی، شبکه پردازشگرهای تکاملی قطبی، سیستم 2-برچسب ماشین تورینگ،
ترجمه چکیده
ما یک نوع جدید از شبکه های پردازنده های تکاملی را در نظر می گیریم که به نظر می رسد مناسب تر برای اجرای نرم افزار و سخت افزار است. هر پردازنده و همچنین داده های ناوبری در سراسر شبکه اکنون قطعه قطعه شده اند. در حالی که قطبش هر پردازنده از قبل تعریف شده است، قطبی شدن داده ها به صورت پویا محاسبه می شود. در نتیجه، پروتکل ارتباط به طور طبیعی توسط این قطبش تعریف می شود. ما نشان می دهیم که سیستم های تگ می توانند توسط این شبکه ها با یک تعداد ثابت از گره شبیه سازی شوند، در حالی که ماشین های تورینگ توسط این شبکه ها با تعدادی گره بسته به صورت خطی در الفبای نوار ماشین تورینگ قابل شبیه سازی هستند. ما همچنین شبیه سازی ماشین های تورینگ را با شبکه های با تعداد ثابت گره پیشنهاد می کنیم، که در افزایش زمان محاسبات منعکس می شود. در نهایت، ما نشان می دهیم که هر شبکه می تواند توسط یک ماشین تورینگ شبیه سازی شده و در مورد پیچیدگی زمان این شبیه سازی بحث شود.
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider a new variant of networks of evolutionary processors which seems more suitable for a software and hardware implementation. Each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined, the data polarization is dynamically computed. Consequently, the protocol of communication is naturally defined by this polarization. We show that tag systems can be simulated by these networks with a constant number of nodes, while Turing machines can be efficiently simulated by these networks with a number of nodes depending linearly on the tape alphabet of the Turing machine. We also propose a simulation of Turing machines by networks with a constant number of nodes, which is reflected in an increase of the computation time. Finally, we show that every network can be simulated by a Turing machine and discuss the time complexity of this simulation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 253, Part 3, April 2017, Pages 371-380
Journal: Information and Computation - Volume 253, Part 3, April 2017, Pages 371-380
نویسندگان
Fernando Arroyo, Sandra Gómez Canaval, Victor Mitrana, Stefan Popescu,