Algorithmic Randomness and Complexity

به طور شهودی، دنباله‌ای مانند 101010101010101010… تصادفی به نظر نمی‌رسد، در حالی که 101101011101010100… که با استفاده از پرتاب سکه به‌دست می‌آید، تصادفی به نظر نمی‌رسد. چگونه می توانیم این شهود را با این واقعیت که هر دو از نظر آماری به یک اندازه محتمل هستند، تطبیق دهیم؟ این که بگوییم یک شیء ریاضی منفرد مانند یک عدد واقعی تصادفی است یا اینکه بگوییم یک واقعی از دیگری تصادفی تر است به چه معناست؟ و چه رابطه ای بین تصادفی بودن و قدرت محاسباتی وجود دارد. نظریه تصادفی بودن الگوریتمی از ابزارهای تئوری محاسباتی و نظریه اطلاعات الگوریتمی برای پاسخگویی به سوالاتی از این قبیل استفاده می کند. بسیاری از این نظریه را می توان به عنوان بررسی روابط بین سه مفهوم اساسی مشاهده کرد: محاسبه پذیری نسبی، که با مفاهیمی مانند کاهش پذیری تورینگ سنجیده می شود. محتوای اطلاعاتی که با مفاهیمی مانند پیچیدگی کلموگروف اندازه گیری می شود. و تصادفی بودن اشیاء منفرد، همانطور که برای اولین بار توسط Martin-Löf با موفقیت تعریف شد. اگرچه تصادفی بودن الگوریتمی برای چندین دهه مورد مطالعه قرار گرفته است، افزایش چشمگیر علاقه در این منطقه، که از اواخر دهه 1990 شروع شد، منجر به پیشرفت های قابل توجهی شده است. این اولین درمان جامع این حوزه مهم است که هم به عنوان یک ابزار مرجع برای کارشناسان و هم راهنمایی برای تازه واردان طراحی شده است. این بخش وسیعی از کار در منطقه را بررسی می کند و بیشتر نتایج و تکنیک های اصلی خود را به طور عمیق ارائه می دهد. سازمان آن طوری طراحی شده است که خواننده را از طریق این حجم وسیع از کار راهنمایی کند، زمینه را برای مفاهیم و قضایای متعدد آن فراهم کند، اهمیت آنها را مورد بحث قرار دهد و تعاملات آنها را برجسته کند. این شامل بحث در مورد بعد مؤثر است که به ما امکان می دهد مفاهیمی مانند بعد هاسدورف را به واقعیات فردی اختصاص دهیم، و مقدمه ای متمرکز اما مفصل به نظریه محاسبه پذیری. این مورد برای محققان و دانشجویان در تئوری محاسباتی، نظریه اطلاعات الگوریتمی، و علوم کامپیوتر نظری خواهد بود.

Intuitively, a sequence such as 101010101010101010… does not seem random, whereas 101101011101010100…, obtained using coin tosses, does. How can we reconcile this intuition with the fact that both are statistically equally likely? What does it mean to say that an individual mathematical object such as a real number is random, or to say that one real is more random than another? And what is the relationship between randomness and computational power. The theory of algorithmic randomness uses tools from computability theory and algorithmic information theory to address questions such as these. Much of this theory can be seen as exploring the relationships between three fundamental concepts: relative computability, as measured by notions such as Turing reducibility; information content, as measured by notions such as Kolmogorov complexity; and randomness of individual objects, as first successfully defined by Martin-Löf. Although algorithmic randomness has been studied for several decades, a dramatic upsurge of interest in the area, starting in the late 1990s, has led to significant advances. This is the first comprehensive treatment of this important field, designed to be both a reference tool for experts and a guide for newcomers. It surveys a broad section of work in the area, and presents most of its major results and techniques in depth. Its organization is designed to guide the reader through this large body of work, providing context for its many concepts and theorems, discussing their significance, and highlighting their interactions. It includes a discussion of effective dimension, which allows us to assign concepts like Hausdorff dimension to individual reals, and a focused but detailed introduction to computability theory. It will be of interest to researchers and students in computability theory, algorithmic information theory, and theoretical computer science.