Reversibility and Universality: Essays Presented to Kenichi Morita on the Occasion of his 70th Birthday

این کتاب ادای احترامی به ایده‌ها و دستاوردهای کنیچی موریتا در علم کامپیوتر نظری، برگشت‌پذیری و ماشین‌های ریاضی جهانی محاسباتی است. این یک منبع منحصر به فرد از اطلاعات در مورد جهانی بودن و برگشت پذیری در محاسبات ارائه می دهد و یک کتاب ضروری برای دانشمندان کامپیوتر، ریاضیدانان، فیزیکدانان و مهندسان است.

موریتا به دلیل آثارش در مورد خودکارهای پذیرنده زبان دو بعدی، پیچیدگی ماشین‌های تورینگ، جهانی بودن اتوماتای ​​سلولی، گرامرهای آرایه‌ای منظم و بدون زمینه، و تصمیم‌ناپذیری شهرت دارد. آثار پر تاثیر او شامل یافته‌هایی در مورد تولید موازی و تجزیه زبان‌های آرایه با استفاده از خودکارهای برگشت‌پذیر، ساخت خودکار برگشت‌پذیر از گیت‌های فردکین، حل مشکل هماهنگ‌سازی جوخه تیراندازی در اتوماتای ​​سلولی برگشت‌پذیر، خود بازتولید در فضاهای سلولی برگشت‌پذیر، جهانی است. ماشین‌های دو شمارنده برگشت‌پذیر، حل مسائل چند جمله‌ای غیر قطعی (NP) در اتوماتای ​​سلولی هذلولی، سیستم‌های P برگشت‌پذیر، یک عنصر منطقی برگشت‌پذیر جهانی جدید با حافظه، و برگشت‌پذیری در اتوماتای ​​سلولی ناهمزمان.

دستاوردهای کنیچی موریتا در برگشت‌پذیری، جهان‌شمولی و تئوری محاسبات در بیش از بیست مشارکت برجسته از همکاران، همکاران، دانشجویان و دوستان او تجلیل شده است. ساختارهای نظری ارائه شده در این کتاب از نظر تنوع و عمق بینش فکری شگفت‌انگیز هستند و به موارد زیر اشاره می‌کنند: اتوماتای ​​صف، اتوماتای ​​سلولی هذلولی، اتوماتای ​​معکوس آبلی، اتوماتای ​​سلولی حفظ اعداد، مدارهای براونی، اتوماتای ​​شیمیایی، دروازه‌های منطقی هم‌پیاده‌سازی شده محاسبات در شبکه‌های گروهی، آرایه‌های تصویر، ماشین‌های شمارنده برگشت‌پذیر جهانی، مدل‌های ورودی-موقعیت محدود پذیرندگان زبان، پیچیدگی توصیفی و تداوم خودکارهای سلولی، اتوماتای ​​سلولی پارتیشن‌بندی‌شده، الگوریتم‌های هماهنگ‌سازی جوخه تیراندازی، خودکارهای درختی غیرهمزمان برگشت‌پذیر، خودکارهای غیرهمزمان برگشت‌پذیر الگوریتم های فاکتورسازی Shor و مصرف انرژی اتوماتای ​​سلولی.

This book is a tribute to Kenichi Morita’s ideas and achievements in theoretical computer science, reversibility and computationally universal mathematical machines. It offers a unique source of information on universality and reversibility in computation and is an indispensable book for computer scientists, mathematicians, physicists and engineers.

Morita is renowned for his works on two-dimensional language accepting automata, complexity of Turing machines, universality of cellular automata, regular and context-free array grammars, and undecidability. His high-impact works include findings on parallel generation and parsing of array languages by means of reversible automata, construction of a reversible automaton from Fredkin gates, solving a firing squad synchronization problem in reversible cellular automata, self-reproduction in reversible cellular spaces, universal reversible two-counter machines, solution of nondeterministic polynomial (NP) problems in hyperbolic cellular automata, reversible P-systems, a new universal reversible logic element with memory, and reversibility in asynchronous cellular automata.

Kenichi Morita’s achievements in reversibility, universality and theory of computation are celebrated in over twenty high-profile contributions from his colleagues, collaborators, students and friends. The theoretical constructs presented in this book are amazing in their diversity and depth of intellectual insight, addressing: queue automata, hyperbolic cellular automata, Abelian invertible automata, number-conserving cellular automata, Brownian circuits, chemical automata, logical gates implemented via glider collisions, computation in swarm networks, picture arrays, universal reversible counter machines, input-position-restricted models of language acceptors, descriptional complexity and persistence of cellular automata, partitioned cellular automata, firing squad synchronization algorithms, reversible asynchronous automata, reversible simulations of ranking trees, Shor’s factorization algorithms, and power consumption of cellular automata.