ক্লদ শ্যাননের ইনফরমেশন থিওরি যোগাযোগ বিপ্লব ঘটালেও এর একটি গভীর দার্শনিক সীমাবদ্ধতা ছিল: এটি তথ্য পরিমাপ করত কোনো সম্ভাব্যতা বিন্যাসের প্রেক্ষিতে সামগ্রিক এনসেম্বলের ওপর। শ্যানন বলতে পারতেন একটি উৎস গড়ে কত তথ্য দেয়, কিন্তু একটি নির্দিষ্ট একক স্ট্রিংয়ের—যেমন $pi$-এর প্রথম এক কোটি ডিজিট বনাম একটি কয়েন টসের আউটপুটের—ভেতর অন্তর্নিহিত তথ্যের পরিমাণ কত, তা শ্যানন তত্ত্বে ব্যাখ্যা করা যেত না। ১৯৬০-এর দশকে রাশিয়ান গণিতবিদ আন্দ্রেই কলমোগোরভ, রে সলোমনভ এবং গ্রেগরি চাইতিন স্বাধীনভাবে উদ্ভাবন করেন অ্যালগরিদমিক ইনফরমেশন থিওরি (AIT)। তাঁরা কোনো বস্তুর জটিলতাকে সংজ্ঞায়িত করেন একটি ইউনিভার্সাল টুরিং মেশিনে সেই বস্তুটি তৈরি করতে প্রয়োজনীয় ক্ষুদ্রতম প্রোগ্রামের দৈর্ঘ্য দ্বারা।
১. কলমোগোরভ জটিলতার গাণিতিক সংজ্ঞা
একটি ইউনিভার্সাল টুরিং মেশিন $U$-এর সাপেক্ষে একটি নির্দিষ্ট বাইনারি স্ট্রিং $s$-এর কলমোগোরভ জটিলতা $K_U(s)$ হলো ক্ষুদ্রতম প্রোগ্রাম $p$-এর দৈর্ঘ্য যা রান করলে মেশিনটি থেমে গিয়ে $s$ প্রিন্ট করে:
[
K_U(s) = min { |p| : U(p) = s }
]
যেহেতু একটি প্রোগ্রাম সরাসরি `print “s”` কমান্ডের মাধ্যমে স্ট্রিংকে প্রিন্ট করতে পারে, তাই যেকোনো স্ট্রিংয়ের জটিলতা তার দৈর্ঘ্যের চেয়ে খুব বেশি হতে পারে না: $K(s) le |s| + c$।
২. ইনভ্যারিয়েন্স উপপাদ্য: মেশিন নিরপেক্ষতা
প্রোগ্রামিং ভাষার ভিন্নতায় কি এই জটিলতা বদলে যেতে পারে? কলমোগোরভ ও সলোমনভের ইনভ্যারিয়েন্স উপপাদ্য প্রমাণ করে যে দুটি ভিন্ন ইউনিভার্সাল মেশিন $U_1$ ও $U_2$-এর জন্য:
[
|K_{U_1}(s) – K_{U_2}(s)| le c_{12}
]
যেখানে $c_{12}$ হলো একটি মেশিন থেকে অন্য মেশিনের সিমুলেটর বা ইন্টারপ্রেটারের স্থির দৈর্ঘ্য। বৃহৎ স্ট্রিংয়ের জন্য এই ধ্রুবকটি নগণ্য হয়ে পড়ে, যা প্রমাণ করে কলমোগোরভ জটিলতা প্রকৃতির একটি নিরপেক্ষ ও সার্বজনীন গাণিতিক বৈশিষ্ট্য।
৩. অ্যালগরিদমিক ইনকম্প্রেসিবিলিটি ও বিশুদ্ধ র্যান্ডমনেস
গণিতের ইতিহাসে কলমোগোরভ জটিলতাই প্রথম র্যান্ডমনেস বা দৈবতার একটি ত্রুটিহীন সংজ্ঞা প্রদান করে। কোনো স্ট্রিং যদি কোনো প্যাটার্ন ধারণ না করে এবং তাকে সংকুচিত করা অসম্ভব হয়, তবেই তা বিশুদ্ধ র্যান্ডম।
$n$ দৈর্ঘ্যের একটি স্ট্রিং $s$-কে অ্যালগরিদমিকভাবে ইনকম্প্রেসিবল বলা হয় যদি:
[
K(s) ge n – c
]
সহজ গণনায় দেখা যায়, $n$ দৈর্ঘ্যের মোট $2^n$ টি স্ট্রিংয়ের মধ্যে $99.9%$-এরও বেশি স্ট্রিং বিশুদ্ধ র্যান্ডম এবং ইনকম্প্রেসিবল! মহাবিশ্বে বিশৃঙ্খলা ও অনিয়মিত রূপই পরম সত্য, আর নিয়মতান্ত্রিক বা কমপ্রেসিবল স্ট্রিংগুলো হলো অতি বিরল ব্যতিক্রম।
৪. বেরি প্যারাডক্স ও কলমোগোরভ জটিলতার অগননযোগ্যতা
কোনো কম্পিউটার কি যেকোনো স্ট্রিংয়ের কলমোগোরভ জটিলতা গণনা করতে পারে? কলমোগোরভ প্রমাণ করেন যে $K(s)$ হলো কঠোরভাবে অগণনযোগ্য (Uncomputable)। যদি এমন কোনো অ্যালগরিদম থাকত, তবে তা ক্লাসিক্যাল বেরি প্যারাডক্স-এর জন্ম দিত (“এমন একটি ক্ষুদ্রতম সংখ্যা যা বিশ শব্দের কম বাক্যে প্রকাশ করা যায় না”)। এটি টুরিংয়ের হল্টিং প্রবলেমের সমতুল্য এবং প্রমাণ করে যে তথ্যের চরম সত্য গণিতের সীমানায় বন্দি।
