نظریه محاسبهپذیری شاخهای از منطق ریاضی و علوم کامپیوتر است که به مطالعه این میپردازد که کدام مسائل را میتوان به صورت الگوریتمی حل کرد. مسئله توقف، که توسط آلن تورینگ معرفی شد، سنگ بنای این نظریه است و بیان میکند که هیچ الگوریتم کلی برای تعیین توقف هر برنامهای وجود ندارد. بازی سگ آبی پرکار یک تجسم مستقیم از این مسئله است. تابع سگ آبی، `BB(n)`، به عنوان سریعترین تابع غیرقابل محاسبه شناخته میشود. یعنی هیچ الگوریتمی وجود ندارد که بتواند مقادیر `BB(n)` را برای هر `n` دلخواه محاسبه کند. این مقاله نشان میدهد که چگونه تلاش برای یافتن این مقادیر، محققان را به مرزهای محاسبهپذیری میکشاند.
آیا تا به حال سعی کردهاید عدد بعدی در یک دنباله را حدس بزنید؟ این یکی را امتحان کنید: ۱، ۶، ۲۱، ۱۰۷، ۴۷,۱۷۶,۸۷۰… عدد بعدی چیست؟ اگر گیج شدهاید، تنها نیستید. این یک دنباله معمولی نیست؛ اینها پنج عدد اول «سگ آبی پرکار» (Busy Beaver) هستند و سفری به کرانههای مطلق محاسبات و ریاضیات … Read more