New Computational Paradigms: Changing Conceptions of What is Computable

در سال‌های اخیر، محاسبه‌پذیری کلاسیک فراتر از محدوده اصلی خود گسترش یافته است تا به مسائل مربوط به محاسبه‌پذیری و پیچیدگی در جبر، تجزیه و تحلیل و فیزیک بپردازد. ارتباط عمیق بین \"محاسبات\" و \"اثبات\" بسیاری از مهمترین کارها را در ریاضیات سازنده و منطق ریاضی در 70 سال گذشته ایجاد کرده است. علاوه بر این، نیاز فزاینده‌ای برای پرداختن به قابلیت محاسبات در دنیای واقعی (مانند محاسبات بر روی داده‌های پیوسته، محاسبات بیولوژیکی، و مدل‌های فیزیکی) تمرکز را بر پارادایم‌های محاسباتی جدیدی که مبتنی بر مدل‌های بیولوژیکی و فیزیکی هستند، کرده است. این مدل‌ها به پرسش‌های مربوط به کارایی به شیوه‌ای کاملاً جدید پاسخ می‌دهند و حتی به اصطلاح سد تورینگ، یعنی خط بین تصمیم‌پذیر و غیرقابل تصمیم‌گیری را تهدید می‌کنند.

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

این کتاب برای محققان و فارغ التحصیلان مناسب است. دانشجویان ریاضیات، فلسفه و علوم کامپیوتر با علاقه خاصی به منطق و مسائل اساسی. مفیدترین مقالات برای دانشجویان تحصیلات تکمیلی، مقالات نظرسنجی در مورد تجزیه و تحلیل قابل محاسبه و محاسبات بیولوژیکی است. منطق دانان و فیزیکدانان نظری نیز از این کتاب بهره خواهند برد.

In recent years, classical computability has expanded beyond its original scope to address issues related to computability and complexity in algebra, analysis, and physics. The deep interconnection between "computation" and "proof" has originated much of the most significant work in constructive mathematics and mathematical logic of the last 70 years. Moreover, the increasingly compelling necessity to deal with computability in the real world (such as computing on continuous data, biological computing, and physical models) has brought focus to new paradigms of computation that are based on biological and physical models. These models address questions of efficiency in a radically new way and even threaten to move the so-called Turing barrier, i.e. the line between the decidable and the un-decidable.

This book examines new developments in the theory and practice of computation from a mathematical perspective, with topics ranging from classical computability to complexity, from biocomputing to quantum computing. The book opens with an introduction by Andrew Hodges, the Turing biographer, who analyzes the pioneering work that anticipated recent developments concerning computation’s allegedly new paradigms. The remaining material covers traditional topics in computability theory such as relative computability, theory of numberings, and domain theory, in addition to topics on the relationships between proof theory, computability, and complexity theory. New paradigms of computation arising from biology and quantum physics are also discussed, as well as the computability of the real numbers and its related issues.

This book is suitable for researchers and graduate students in mathematics, philosophy, and computer science with a special interest in logic and foundational issues. Most useful to graduate students are the survey papers on computable analysis and biological computing. Logicians and theoretical physicists will also benefit from this book.