ثابت چایتین

ثابت چایتین یا عدد اُمگای چایتین (انگلیسی: Chaitin's constant) در نظریهٔ اطلاعات الگوریتمی، که به آن احتمال توقف نیز گفته می‌شود، یک عدد حقیقی است که به‌طور غیررسمی بیانگر احتمال متوقف‌شدن یک برنامهٔ ساخته‌شده به‌صورت تصادفی است. این اعداد بر پایهٔ ساختاری که توسط گرگوری چایتین ارائه شده شکل می‌گیرند.

اگرچه بی‌نهایت احتمال توقف (به‌ازای هر روش کدگذاری برنامه‌ها یک احتمال) وجود دارد، معمولاً از حرف Ω برای اشاره به آن‌ها استفاده می‌شود، گویی تنها عددی واحد وجود دارد. از آن‌جا که مقدار Ω به شیوهٔ کدگذاری برنامه‌ها وابسته است، هنگامی که به کدگذاری خاصی اشاره نمی‌شود، گاه از آن با عنوان «ساخت چایتین» (Chaitin's construction) یاد می‌شود.

هر احتمال توقف، یک عدد حقیقی نرمالِ ترافرازنده و محاسبه‌ناپذیر است؛ یعنی هیچ الگوریتمی برای محاسبهٔ ارقام آن وجود ندارد. ضمناً هر احتمال توقف از نوع تصادفی مارتین–لوف است؛ یعنی حتی هیچ الگوریتمی وجود ندارد که بتواند به‌طرز قابل اعتماد، ارقام آن را حدس بزند.

جستارهای وابسته

منابع

    This article is issued from ویکی‌پدیا. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.