مشکل فشرده سازی داده ها در ساده ترین شکل خود می تواند به اعداد و نمادهای آنها مربوط شود. اعداد را می توان با اعداد نشان داد ("یازده" برای عدد 11)، عبارات ریاضی ("دو در بیستم" برای 1048576)، عبارات رشته ای ("پنج نه" برای 99999)، نام های مناسب ("تعداد وحش" برای 666، "سال مرگ تورینگ" برای 1954)، یا ترکیب دلخواه آنها. هر نامگذاری مناسب است که با آن همکار بتواند به وضوح تعیین کند که در مورد چه عددی صحبت می کنیم. بدیهی است که به همکار خود بگویید "فاکتوریل هشت" کارآمدتر از نمادهای معادل "چهل هزار و سیصد و بیست". یک سوال منطقی در اینجا مطرح می شود: کوتاه ترین نماد برای یک عدد مشخص چیست؟
فیلسوف برتراند راسل در سال 1908 منتشر شد ، که از طرف مقابل به موضوع علامت گذاری اعداد می پردازد: کوچکترین عددی که به هشتاد حرف نیاز ندارد کدام است؟
چنین عددی باید وجود داشته باشد: از هشتاد حرف و فاصله روسی فقط می توانید 3480 علامت بسازید، به این معنی که با استفاده از هشتاد حرف نمی توانید بیش از 3480 عدد را تعیین کنید. این بدان معنی است که نمی توان یک عدد معین را بیش از 3480 به این ترتیب تعیین کرد.
این بدان معنی است که این عدد با تعیین مطابقت دارد "کوچکترین عددی که هشتاد حرف برای آن کافی نیست"، که فقط 78 حرف دارد! از یک طرف، این عدد باید وجود داشته باشد. از طرف دیگر، اگر این عدد وجود داشته باشد، نام آن با آن مطابقت ندارد. پارادوکس!
ساده ترین راه برای رد این پارادوکس مراجعه به غیر رسمی بودن نمادهای کلامی است. مثلاً، اگر فقط مجموعه‌ای از عبارات تعریف شده در نماد مجاز باشد، پس "کوچکترین عددی که هشتاد حرف برای آن کافی نیست" یک نماد معتبر نخواهد بود، در حالی که نمادهای عملا مفید مانند "فاکتوریل هشت" قابل قبول باقی می ماند.
آیا روش های رسمی برای توصیف دنباله (الگوریتم) اعمال روی اعداد وجود دارد؟ وجود دارد، و به وفور - آنها را زبان های برنامه نویسی می نامند. به جای نمادهای شفاهی، از برنامه هایی (مثلاً در پایتون) استفاده خواهیم کرد که اعداد مورد نیاز را نمایش می دهند. به عنوان مثال، برای پنج نه برنامه مناسب است print("9"*5). ما همچنان به کوتاه ترین برنامه برای یک عدد معین علاقه مند خواهیم بود. طول چنین برنامه ای نامیده می شود شماره؛ این حد تئوری است که یک عدد معین را می توان به آن فشرده کرد.
به جای پارادوکس بری، اکنون می توانیم یک مورد مشابه را در نظر بگیریم: کوچکترین عددی که یک برنامه کیلوبایتی برای خروجی کافی نیست چیست؟
ما به همان روش قبلی استدلال خواهیم کرد: 2561024 متون کیلوبایتی وجود دارد، به این معنی که بیش از 2561024 عدد نمی تواند توسط برنامه های کیلوبایتی خروجی شود. این به این معنی است که یک عدد معین که بزرگتر از 2561024 نباشد را نمی توان به این ترتیب به دست آورد.
اما بیایید برنامه ای در پایتون بنویسیم که تمام متون کیلوبایتی ممکن را تولید کند، آنها را برای اجرا اجرا کند، و اگر یک عدد را خروجی کند، سپس این عدد را به فرهنگ لغت نامه های قابل دسترسی اضافه می کند. پس از بررسی همه 2561024 احتمال، مهم نیست که چقدر طول بکشد، برنامه به دنبال کوچکترین عدد گم شده در فرهنگ لغت می گردد و آن عدد را چاپ می کند. بدیهی به نظر می رسد که چنین برنامه ای در یک کیلوبایت کد قرار می گیرد - و همان عددی را که نمی تواند توسط یک برنامه کیلوبایتی خروجی بگیرد را خروجی می دهد!
حالا گیرش چیه؟ دیگر نمی توان آن را به غیر رسمی بودن علامت گذاری نسبت داد!
اگر از این واقعیت که برنامه ما به مقدار نجومی حافظه برای کار کردن نیاز دارد - یک فرهنگ لغت (یا آرایه بیت) از 2561024 عنصر - گیج شده اید، می توانید بدون آن همان کار را انجام دهید: برای هر یک از 2561024 اعداد، به نوبه خود. ، تمام 2561024 برنامه ممکن را مرور کنید تا زمانی که برنامه مناسبی وجود نداشته باشد. مهم نیست که چنین جستجویی مدت زمان زیادی طول بکشد: پس از بررسی کمتر از (2561024) 2 جفت از شماره و برنامه، به پایان می رسد و آن عدد بسیار گرامی را پیدا می کند.
یا تموم نمیشه؟ در واقع، در میان تمام برنامه هایی که امتحان خواهند شد، وجود خواهد داشت while True: pass (و آنالوگ های عملکردی آن) - و موضوع از آزمایش چنین برنامه ای فراتر نمی رود!
بر خلاف پارادوکس بری، که در غیررسمی بودن علامت گذاری، در مورد دوم، ما یک فرمول بندی به خوبی مبدل داریم. . واقعیت این است که تعیین خروجی آن از یک برنامه در زمان محدود غیرممکن است. به طور خاص، پیچیدگی Kolmogorov : هیچ الگوریتمی وجود ندارد که برای یک عدد معین، طول کوتاه ترین برنامه ای را که این عدد را چاپ می کند، پیدا کند. این بدان معناست که هیچ راه حلی برای مشکل بری وجود ندارد - یافتن طول کوتاه ترین علامت کلامی برای یک عدد معین.
منبع: www.habr.com