عجیبترین اعداد دنیای ریاضی؛ از اعداد گنگ تا اعداد محاسبهناپذیر
عجیبترین اعداد دنیای ریاضی؛ از اعداد گنگ تا اعداد
محاسبهناپذیر
گرگوری چایتین، ریاضیدان آرژانتینی-آمریکایی از مسئلهی توقف برای تعریف یک عدد محاسبهناپذیر استفاده کرد. این عدد که ثابت چایتین Ω نامیده میشود، متناظر با این احتمال است که بر اساس آن مدل کامپیوتری (ماشین تورینگ) برای هر مقدار ورودی |Ω = –∑p½|p متوقف میشود که در آن p نماد تمام برنامههایی است که پس از یک اجرای متناهی متوقف میشوند و |p| طول برنامه را بر اساس واحد بیتی توصیف میکند.
بنابراین برای محاسبهی دقیق ثابت چایتین، باید بدانیم کدام برنامهها متوقف میشوند و کدامیک نمیشوند، که این کار بر اساس مسئلهی توقف، ممکن نیست. بااینحال، کریستین اس کلاود ریاضیدان و همکارانش، در محاسبهی اولین رقمهای ثابت چایتین عملکرد موفقی داشتند:
0.0157499939956247687….
بنابراین میتوان نتیجه گرفت که اگر برنامهای را بهصورت تصادفی به زبانی بسازید که کلاود و همکاران او از آن استفاده کردند، این برنامه با احتمال ۱٫۵۸ درصد در یک زمان اجرای متناهی حفظ میشود. حتی اگر نتیجه دقت بالایی داشته باشد، ثابت چایتین را نمیتوان با دقت محض محاسبه کرد.
عدد محاسبهناپذیر و سگ آبی مشغول
عدد محاسبهناپذیر دیگر از تابع «سگ آبی مشغول» (Busy Beaver) یا BB(n) به دست میآید. این تابع بزرگترین خروجی ممکن (بر اساس بیت) را که یک الگوریتم میتواند از n بیت تولید کند، محاسبه میکند.
برای مثال عدد محاسبهناپذیر از ساختار ذیل به دست میآید: ∑n½BB(n) . تاکنون تنها چهار رقم اول تابع سگ آبی مشغول شناخته شدهاند و دو رقم دیگر را میتوان تخمین زد.
