برنامه‌هاي كامپيوتري فوق آهسته محدوديت‌هاي بنيادي رياضي را آشكار مي‌كنند

برنامه‌نويسان معمولا به‌دنبال حداقل‌سازي زمان اجراي كدهاي خود هستند؛ اما در سال ۱۹۶۲، تيبور رادو، رياضي‌دان مجارستاني، مسئله‌اي مخالف را مطرح كرد. او پرسيد: «برنامه‌ي ساده‌ي كامپيوتري قبل از توقف چه مدت اجرا مي‌شود؟» برخي برنامه‌ها به‌شدت ناكارآمد هستند؛ اما باز‌هم به كارشان ادامه مي‌دهند. رادو نام مستعار «سگ‌هاي آبي مشغول» (Busy Beaver) را به اين برنامه‌ها داد.

يافتن برنامه‌هاي سگ آبي مشغول از سال ۱۹۸۴ به يكي از معماهاي گمراه‌كننده براي برنامه‌نويسان و ازجمله سرگرمي‌هاي رياضي تبديل شد. بااين‌حال در سال‌هاي گذشته، بازي سگ آبي مشغول به موضوع پژوهشي هم تبديل شده است؛ زيرا با مفاهيم و مسائل بنيادي‌ باز رياضي در ارتباط بوده است. اسكات آرانسون، دانشمند كامپيوتر تئوري در دانشگاه آستين تگزاس مي‌گويد: «در رياضي، مرز بسيار باريكي بين سرگرمي و مسائل مهم وجود دارد.»

پژوهش جديد نشان مي‌دهد جست‌وجوي برنامه‌هاي كامپيوتري با زمان اجراي طولاني يا برنامه‌هاي آهسته مي‌تواند وضعيت دانش رياضي را متحول كند و نكات مهمي را آشكار كند. به‌گفته‌ي پژوهشگران، بازي سگ آبي مشغول شاخص منسجمي براي ارزيابي دشواري مسائل مشخص، از‌جمله حدس حل‌نشده‌ي گلدباخ و فرضيه‌ي ريمان است.

به‌طوركلي، بازي سگ آبي مشغول درباره‌ي رفتار ماشين‌هاي تورينگي است. ماشين‌هاي تورينگ كامپيوترهاي اوليه‌ و ايدئالي هستند كه در سال ۱۹۳۶، آلان تورينگ تعريف كرد. ماشين تورينگ عمليات را روي رشته‌ي نوار متناهي انجام مي‌دهد كه به مربع‌هايي تقسيم شده است. اين ماشين عمليات را براساس فهرستي از قوانين اجرا مي‌كند. اولين قانون بدين‌ترتيب است:

اگر مربعي شامل عدد ۰ باشد، آن را با عدد ۱ جايگزين كن و مربع را به‌سمت راست منتقل و قانون ۲ را مطالعه كن. اگر مربع شامل عدد ۱ باشد، ۱ را رها كن و يك مربع به‌سمت چپ برو و قانون ۳ را مطالعه كن.

هر قانون به اين سبك است: «ماجراجويي خود را انتخاب كن». برخي قوانين مي‌گويند به قوانين قبلي مراجعه كنيد و درنهايت، قانوني شامل دستورالعمل «توقف» خواهد بود. تورينگ ثابت كرد اين نوع ساده از كامپيوتر براساس دستورالعمل‌هاي ساده و زمان كافي، مي‌تواند محاسبات احتمالي را انجام دهد.

براساس تعريف تورينگ در سال ۱۹۳۶، ماشين تورينگ براي محاسبه‌ي هر چيزي در‌نهايت با دستور «توقف» روبه‌رو مي‌شود و در حلقه‌ي بي‌نهايت گرفتار نخواهد شد. باوجوداين، ثابت مي‌كند كه روش مطمئن و تكراري براي تفكيك ماشين‌هايي كه متوقف مي‌شوند، از ماشين‌هايي كه هميشه اجرا مي‌شوند، وجود ندارد.

نمايشي بصري از ماشين تورينگ پنج‌قانوني با آهسته‌ترين اجرا. هر ستون از پيكسل‌ها، نشان‌دهنده‌ي يك گام در محاسبات هستند كه از چپ به راست حركت مي‌كنند. مربع‌هاي سياه هم نشان‌دهنده‌ي موقعيت‌هايي هستند كه در آن‌ها ماشين عدد ۱ را چاپ كرده است. ستون سمت راست نشان‌دهنده‌ي وضعيت محاسبات در زمان توقف ماشين تورينگ است.

بازي سگ آبي مشغول اين پرسش را مطرح مي‌كند: «با‌توجه‌به تعداد مشخصي از قوانين، حداكثر گام‌هايي كه ماشين تورينگ مي‌تواند قبل از توقف طي كند، چقدر است؟» براي مثال، اگر تنها يك قانون را مجاز كرده باشيد و بخواهيد از توقف ماشين تورينگ مطمئن شويد، بايد بلافاصله دستور توقف را در انديشه متخصصين بگيريد؛ در‌نتيجه، عدد سگ آبي مشغول براي ماشين تك‌قانوني يا (BB(1 برابر با يك است.

با اضافه‌كردن چند قانون بيشتر، تعداد ماشين‌ها هم افزايش مي‌يابند. از ميان ۶،۵۶۱ ماشين احتمالي داراي دو قانون، ماشيني كه در طولاني‌ترين زمان ممكن قبل از عمل توقف اجرا مي‌شود (شش مرحله)، سگ آبي مشغول است؛ اما برخي از ماشين‌هاي ديگر تا ابد ادامه پيدا مي‌كنند؛ درنتيجه، هيچ‌كدام از آن‌ها سگ آبي مشغول نيستند. چگونه مي‌توان اين ماشين‌ها را حذف كرد؟ تورينگ ثابت كرد هيچ روشي وجود ندارد كه به‌صورت خودكار نشان دهد ماشيني كه براي هزار يا يك‌ميليون گام اجرا مي‌شود، در‌نهايت، به‌پايان نخواهد رسيد؛ به‌همين‌دليل، يافتن سگ‌هاي آبي مشغول كار بسيار دشواري است.

روش كلي براي شناسايي ماشين‌هاي تورينگ با طولاني‌ترين اجرا و تعداد دلخواه دستورالعمل‌‌ها وجود ندارد. به‌بيان‌بهتر، بازي سگ آبي مشغول محاسبه‌ناپذير است. اثبات اين مسئله كه BB(2)=6 و BB(3)=107 به‌اندازه‌ي كافي دشوار بود؛ به‌طوري‌كه دانشجوي رادو، شن لين، با انجام اين پروژه در سال ۱۹۶۵ موفق شد مدرك دكتري بگيرد. رادو (BB(4 را كاملا نااميدكننده خواند؛ اما اين مسئله در‌نهايت در سال ۱۹۸۳ حل شد.

ويليام گاسارچ، دانشمند كامپيوتر دانشگاه مريلند و رياضي‌دانان ديگر به استفاده از بازي به‌عنوان مقياسي براي اندازه‌گيري دشواري مسائل باز مهم در رياضيات يا محاسبه‌ي معلوم‌هاي رياضي علاقه‌مند هستند. براي مثال، حدس گلدباخ اين پرسش را مطرح مي‌كند: «آيا هر عدد زوج صحيح بزرگ‌تر از دو جمع دو عدد اول است؟» اثبات اين حدس يكي از رويدادهاي مهم در انديشه متخصصينيه‌ي اعداد است و به رياضي‌دانان اجازه مي‌دهد به درك بهتري از توزيع اعداد اول برسند.

در سال ۲۰۱۵، يكي از متخصصان بدون نام گيت‌هاب با نام مستعار Code Golf Addict كدي براي ماشين تورينگ با ۲۷ قانون منتشر كرد. اين ماشين متوقف مي‌شود، اگر و تنها اگر حدس گلدباخ اشتباه باشد. اين ماشين با شمارش صعودي كل اعداد زوج صحيح بزرگ‌تر از چهار كار مي‌كند و براي هركدام، تمام روش‌هاي احتمالي براي دستيابي به عدد صحيح با جمع دو عدد ديگر را مطالعه مي‌كند كه آيا زوج به‌دست‌آمده اول هستند يا خير. اين ماشين با يافتن زوج مناسب اعداد اول به زوج عدد صحيح بعدي مي‌پردازد و فرايند فوق را تكرار مي‌كند. اگر يك عدد زوج پيدا كند كه حاصل جمع زوج اعداد اول نباشد، متوقف مي‌شود.

اجراي ماشين مذكور، روشي متخصصدي براي حل حدس گلدباخ نيست؛ زيرا نمي‌توان از توقف آن مطمئن بود؛ اما بازي سگ آبي مشغول تا اندازه‌اي بر اين مسئله تأكيد مي‌كند. اگر امكان محاسبه‌ي BB(27) وجود داشت، سقف انتظاري براي حل خودكار حدس گلدباخ به‌وجود مي‌آمد؛ زيرا BB(27) متناظر با حداكثر تعداد مراحلي است كه ماشين ۲۷ قانوني تورينگ مي‌تواند اجرا كند. اگر تعداد دقيق مراحل را مي‌دانستيم، مي‌توانستيم ماشين تورينگ را دقيقا براساس همان تعداد تنظيم كنيم. اگر ماشين تورينگ در آن نقطه متوقف شود، بدين‌معني است كه حدس گلدباخ اشتباه است؛ اما اگر مراحل زيادي را اجرا كند، مي‌توان با اطمينان گفت حدس صحيح هستند.

البته (BB(744 از‌انديشه متخصصين تعداد قوانين، بسيار بيشتر از (BB(27 است؛ اما كار با نمونه‌اي ساده‌تر مثل (BB(5، مي‌تواند به مطرح‌شدن پرسش‌هاي جديدي در زمينه‌ي انديشه متخصصينيه‌ي اعداد منجر شود كه در نوع خود جذاب هستند. براي مثال، رياضي‌داني به‌نام پاسكال ميشل در سال ۱۹۹۳ ثابت كرد ماشين تورينگ پنج‌قانوني رفتار مشابه با تابع حدس كولاتز دارد كه مسئله‌ي باز مشهوري در انديشه متخصصينيه‌ي اعداد است. آرانسون مي‌گويد:

بخش زيادي از رياضيات را مي‌توان با اين پرسش رمزنگاري كرد: آيا اين ماشين تورينگ متوقف مي‌شود يا خير؟ اگر تمام اعداد سگ آبي مشغول را بشناسيد، به تمام اين پرسش‌ها مي‌توانيد پاسخ دهيد.

اخيرا آرانسون از مقياس سگ آبي مشغول به‌منظور اندازه‌گيري «آستانه‌ي مجهوليت» براي كل سيستم‌هاي رياضي استفاده كرد. انديشه متخصصينيه‌هاي ناقص و مشهور گودل از ۱۹۳۱ نشان مي‌دهند هر مجموعه‌اي از قواعد اوليه كه بتوانند به‌عنوان مبنايي منطقي و احتمالي براي رياضيات عمل كنند، به يكي از اين دو سرنوشت دچار خواهند شد: ۱. قواعد مي‌توانند ناسازگار باشند و به تناقض‌هايي مثل ۰=۱ منجر شوند؛ ۲. قواعد مي‌توانند ناقص باشند و برخي از قضيه‌هاي صحيح عددي را نتوانند اثبات كنند (مثلا اين حقيقت كه ۲+۲=۴ است). سيستم بديهي شالوده‌ي كل رياضيات مدرن به‌عنوان انديشه متخصصينيه‌ي مجموعه‌ي زرملوفرانكل (ZF) شناخته مي‌شود و محدوديت‌هاي گودلي دارد. حالا آرانسون مي‌خواهد از بازي سگ آبي مشغول براي شناسايي موقعيت اين سيستم‌ها استفاده كند.

در سال ۲۰۱۶، آرانسون و دانشجوي او، آدام يديديا، نوعي ماشيني تورينگ با ۷،۹۱۰ قانون را تعريف كردند. اين ماشين فقط زماني متوقف مي‌شود كه انديشه متخصصينيه‌ي مجموعه‌ي ZF ناسازگار باشد؛ يعني (BB(7910 محاسبه‌اي است كه قواعد انديشه متخصصينيه‌ي ZF را ناديده مي‌گيرد. با اين قواعد، نمي‌توان درستي نتيجه‌ي (BB(7910 را ثابت كرد و براي مثال، نشان داد نتيجه‌ي ۲+۲=۴ است، نه ۵.

اورير نوعي ماشين ساده‌تر با ۷۴۸ قانون طراحي كرد. اين ماشين صرفا زماني متوقف مي‌شود كه ZF ناسازگار باشد. به‌طور‌كلي، آستانه‌هاي مجهوليت اين‌چنيني قطعا وجود دارند و به‌گفته‌ي آرانسون، اين چشم‌اندازي از جهان است كه از زمان گودل وجود داشته و تابع سگ آبي مشغول روشي براي پياده‌سازي آن‌ها در نمونه‌هاي واقعي است.