[ad_1]

برنامه نویسان معمولاً می خواهند تا زمان لازم برای کد اجرای آنها به حداقل برسد. اما در سال 1962 ، ریاضیدان مجارستانی ، تیبور رادو ، مسئله مخالف را مطرح کرد. وی پرسید: چه مدت می تواند یک برنامه ساده رایانه ای قبل از خاتمه یافتن آن اجرا شود؟ او خوشحال بود که این برنامه ها را که حداکثر ناکارآمد اما هنوز هم عملکردی دارند “beavers مشغول” نامید.

داستان اصلی ، چاپ مجدد با اجازه از مجله کوانتا، یک نشریه مستقل تحریریه بنیاد سیمونز ، که مأموریت آن بهبود درک عمومی از علم با تأمل در تحولات تحقیق و روندهای ریاضیات و علوم فیزیکی و زندگی است.

پیدا کردن این برنامه ها برای برنامه نویسان و سایر علاقه مندان به ریاضیات یک معمای منحصر به فرد است زیرا از محبوبیت آن در آمریکایی علمیدر بخش “سرگرمی رایانه ای” در سال 1984. اما در چند سال گذشته ، بازی سریع بیور ، همانطور که شناخته شده است ، به خودی خود به یک موضوع مطالعه تبدیل شده است ، زیرا پیوندهایی به برخی از متعالی ترین مفاهیم و وظایف باز شده را فراهم می کند ریاضیات

اسکات آرونسون ، دانشمند علوم نظری در دانشگاه تگزاس در آستین که اخیراً مطالعه پیشرفت در BusyBeaverology را منتشر کرد ، گفت: “در ریاضیات ، یک بینش کاملاً بینشی وجود دارد که جالب و واقعی است.”

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

بازی رایانه ای بیشمار

بازی شلوغ بیور مربوط به رفتار ماشین های تورینگ است – رایانه های بدوی و ایده آل که آلن تورینگ در سال 1936 اختراع کرد. یک ماشین تورینگ روی یک نوار نوار بی پایان تقسیم شده به مربع عمل می کند. این کار را طبق لیستی از قوانین انجام دهید. قانون اول می تواند بگوید:

اگر مربع حاوی 0 است ، آن را با 1 جایگزین کنید ، یک مربع را به سمت راست حرکت داده و با قانون 2 مشورت کنید. اگر مربع شامل 1 است ، 1 را ترک کنید ، یک مربع را به سمت چپ حرکت داده و با قانون 3 مشورت کنید.

هر قاعده این انتخاب انشعابی سبک ماجراجویی را دارد. برخی از قوانین به شما می گویند که به قوانین قبلی برگردید. پس از همه ، یک قانون وجود دارد که شامل یک دستورالعمل “توقف” است. تورینگ ثابت کرد که این نوع ساده کامپیوتر قادر به انجام همه محاسبات ممکن با دستورالعمل های مناسب و زمان کافی است.

همانطور که تورینگ در سال 1936 اشاره کرد ، برای محاسبه چیزی ، یک ماشین تورینگ باید در نهایت متوقف شود – نمی تواند در یک چرخه بی پایان گیر کند. اما او همچنین ثابت کرد که هیچ روش قابل تکرار و قابل اعتمادی برای تمایز ماشین آلات متوقف شده از ماشین هایی که به راحتی برای همیشه کار می کنند وجود ندارد ، واقعیتی که به عنوان مشکل توقف شناخته می شود.

بازی شلوغ بیش از حد سال می کند: با توجه به تعدادی از قوانین ، حداکثر تعداد قدم هایی که دستگاه تورینگ می تواند قبل از متوقف شدن بردارد چیست؟

به عنوان مثال ، اگر فقط یک قانون مجاز هستید و می خواهید مطمئن شوید که دستگاه تورینگ متوقف می شود ، مجبور می شوید دستورالعمل توقف را فوراً روشن کنید. بنابراین ، تعداد بیور اشغال شده در یک ماشین با یک قاعده یا BB (1) 1 است.

اما افزودن فقط چند قانون دیگر بلافاصله تعداد دستگاههایی را که باید در نظر گرفته شود منفجر می کند. از بین 6561 ماشین ممکن با دو قانون ، اصلی که طولانی ترین عملکرد را دارد – شش مرحله – قبل از توقف ، بیبر شلوغ است. اما برخی دیگر فقط برای همیشه فرار می کنند. هیچکدام از آنها مشغول کشیش نیستند ، اما چگونه می توانید آنها را خاموش کنید؟ تورینگ ثابت کرده است که هیچ راهی وجود ندارد که به طور خودکار بفهمد که آیا ماشین در حال کار با هزار پله یا یک میلیون پله در نهایت متوقف خواهد شد.

به همین دلیل یافتن بیورهای شلوغ بسیار دشوار است. رویکرد مشترکی برای شناسایی طولانی ترین ماشین های تورینگ با تعداد دستورالعمل وجود ندارد. شما باید مشخصات هر مورد را خودتان معما کنید. به عبارت دیگر ، بازی شلوغ بیش از حد معمول “غیر اجباری” است.

[ad_2]

منبع: sadeh-news.ir