تعقيد كولموغوروف

في نظرية المعلومات الخوارزمية ( وهي فرع من علوم الحاسوب والرياضيات )، تُعرَّف تعقيدات كولموغوروف لكائن ما، كنص مثلاً، بأنها طول أقصر برنامج حاسوبي ( بلغة برمجة محددة مسبقاً ) يُنتج هذا الكائن كناتج. وهي مقياس للموارد الحاسوبية اللازمة لتحديد هذا الكائن، وتُعرف أيضاً بالتعقيد الخوارزمي ، أو تعقيدات سولومونوف-كولموغوروف-شايتين ، أو تعقيدات حجم البرنامج ، أو التعقيدات الوصفية ، أو الإنتروبيا الخوارزمية . سُميت هذه التعقيدات نسبةً إلى أندريه كولموغوروف ، الذي نشر أول بحث في هذا الموضوع عام ١٩٦٣ ^{[ ١ ] [ ملاحظة ١ ]} ، وهي تعميم لنظرية المعلومات الكلاسيكية.

يمكن استخدام مفهوم تعقيد كولموغوروف لصياغة وإثبات نتائج الاستحالة المشابهة لحجة كانتور القطرية ، ونظرية عدم الاكتمال لغودل ، ومسألة التوقف لتورينغ . على وجه الخصوص، لا يمكن لأي برنامج P يحسب حدًا أدنى لتعقيد كولموغوروف لكل نص أن يُرجع قيمة أكبر جوهريًا من طول البرنامج P نفسه (انظر القسم § نظرية عدم الاكتمال لشايتين )؛ وبالتالي، لا يمكن لأي برنامج بمفرده حساب تعقيد كولموغوروف بدقة لعدد لا نهائي من النصوص. 

نظرية المعلومات الخوارزمية هي مجال من علوم الحاسوب يدرس تعقيد كولموغوروف ومقاييس التعقيد الأخرى على السلاسل (أو هياكل البيانات الأخرى ).

يستند مفهوم ونظرية تعقيد كولموغوروف إلى نظرية أساسية اكتشفها راي سولومونوف لأول مرة ، ونشرها عام 1960، واصفًا إياها في "تقرير تمهيدي عن نظرية عامة للاستدلال الاستقرائي" ^{[ 5 ]} كجزء من ابتكاره للاحتمالية الخوارزمية . وقدّم وصفًا أكثر تفصيلًا في منشوراته عام 1964، "نظرية رسمية للاستدلال الاستقرائي"، الجزء الأول والثاني في مجلة المعلومات والتحكم . ^{[ 6 ] [ 7 ]}

نشر أندريه كولموغوروف هذه النظرية لاحقًا بشكل مستقل في مجلة Problems Inform. Transmission عام 1965. ^{[ 8 ]} كما قدم غريغوري تشايتين هذه النظرية في مجلة ACM  - حيث قُدِّمت ورقة تشايتين في أكتوبر 1966 ونُقِّحت في ديسمبر 1968، واستشهدت بورقتي سولومونوف وكولموغوروف. ^{[ 9 ]}

تنص النظرية على أنه من بين الخوارزميات التي تفك تشفير السلاسل النصية من أوصافها (رموزها)، توجد خوارزمية مثلى. تسمح هذه الخوارزمية، لجميع السلاسل النصية، برموز قصيرة بقدر ما تسمح به أي خوارزمية أخرى، وصولاً إلى ثابت إضافي يعتمد على الخوارزميات، وليس على السلاسل النصية نفسها. استخدم سولومونوف هذه الخوارزمية وأطوال الرموز التي تسمح بها لتعريف "احتمالية عامة" لسلسلة نصية، يمكن الاستناد إليها في الاستدلال الاستقرائي للأرقام اللاحقة في السلسلة. استخدم كولموغوروف هذه النظرية لتعريف عدة دوال للسلاسل النصية، بما في ذلك التعقيد والعشوائية والمعلومات.

عندما اطلع كولموغوروف على أعمال سولومونوف، أقرّ بأسبقية سولومونوف. ^{[ 10 ]} لسنوات عديدة، كانت أعمال سولومونوف أكثر شهرة في الاتحاد السوفيتي منها في الغرب. ومع ذلك، كان الإجماع العام في الأوساط العلمية هو ربط هذا النوع من التعقيد بكولموغوروف، الذي اهتم بعشوائية التسلسل، بينما ارتبطت الاحتمالية الخوارزمية بسولومونوف، الذي ركز على التنبؤ باستخدام اختراعه لتوزيع الاحتمال المسبق الشامل. يُطلق على المجال الأوسع الذي يشمل التعقيد الوصفي والاحتمالية غالبًا اسم تعقيد كولموغوروف. يعتبر عالم الحاسوب مينغ لي هذا مثالًا على تأثير ماثيو : "...لكل من يملك، سيُعطى المزيد..." ^{[ 11 ]}

توجد عدة صيغ أخرى لتعقيد كولموغوروف أو المعلومات الخوارزمية. الصيغة الأكثر استخداماً تعتمد على البرامج ذاتية التحديد ، ويعود الفضل في ذلك بشكل أساسي إلى ليونيد ليفين (1974).

قدم مارك بورجين نهجًا بديهيًا لتعقيد كولموغوروف استنادًا إلى بديهيات بلوم (بلوم 1967) في الورقة التي قدمها أندريه كولموغوروف للنشر. ^{[ 12 ]}

نكتب${\displaystyle K(x,y)}$يكون${\displaystyle K((x,y))}$، أين${\displaystyle (x,y)}$يعني ذلك طريقة ثابتة لترميز مجموعة من السلاسل النصية x و y.

دالة kolmogorov_complexity ( s : str ): من أجل i = 1 إلى ما لا نهاية : لكل سلسلة p بطول i بالضبط ، إذا كانت is_valid_program ( p ) و evaluate ( p ) == s ، فأرجع i

دالة kolmogorov_complexity ( s : str )

دالة توليد_سلسلة_معقدة (): سلسلة نصية من أجل i = 1 إلى ما لا نهاية : لكل سلسلة نصية s بطول i بالضبط إذا كانت kolmogorov_complexity ( s ) > = 8000000000 إرجاع s

قاعدة السلسلة لتعقيد كولموغوروف

تنص قاعدة السلسلة ^{[ 15 ]} لتعقيد كولموغوروف على أنه يوجد ثابت c بحيث يكون لكل X و Y :

${\displaystyle K(X,Y)=K(X)+K(Y|X)+c\cdot max(1,log(K(X,Y)))}$.

ينص هذا على أن أقصر برنامج يُعيد إنتاج X و Y لا يزيد عن حد لوغاريتمي عن برنامج لإعادة إنتاج X وبرنامج لإعادة إنتاج Y بمعلومية X. وباستخدام هذا البيان، يمكن تعريف نظير للمعلومات المتبادلة لتعقيد كولموغوروف .

من السهل حساب الحدود العليا لـ K ( s )  - ببساطة قم بضغط السلسلة s باستخدام طريقة ما، وقم بتنفيذ برنامج فك الضغط المقابل في اللغة المختارة، وقم بربط برنامج فك الضغط بالسلسلة المضغوطة، وقم بقياس طول السلسلة الناتجة  - على وجه التحديد، حجم الأرشيف ذاتي الاستخراج في اللغة المعطاة.

تُعتبر السلسلة s قابلة للضغط بمقدار c إذا كان وصفها لا يتجاوز طوله | s | - c بت. وهذا يُعادل القول بأن K ( s ) ≤ | s | - c . وإلا، فإن s غير قابلة للضغط بمقدار c . تُسمى السلسلة غير القابلة للضغط بمقدار 1 ببساطة غير قابلة للضغط  - وفقًا لمبدأ التوزيع ، الذي ينطبق لأن كل سلسلة مضغوطة تُقابل سلسلة واحدة غير مضغوطة فقط، لذا يجب أن توجد سلاسل غير قابلة للضغط ، حيث يوجد 2n ^سلسلة بت بطول n ، ولكن يوجد فقط 2n ^- 1 سلسلة أقصر منها، أي سلاسل بطول أقل من n (أي بطول 0، 1، ...، n  -  1). ^{[ ملاحظة 7 ]}

وللسبب نفسه، فإن معظم السلاسل معقدة بمعنى أنها لا يمكن ضغطها بشكل كبير  - فقيمة K ( s ) الخاصة بها ليست أصغر بكثير من | s |، وهو طول السلسلة s بالبتات. ولتوضيح ذلك بدقة، لنفترض قيمة n . يوجد 2 ^{^n} سلسلة بتية طول كل منها n . يُخصص التوزيع الاحتمالي المنتظم على فضاء هذه السلاسل وزنًا متساويًا تمامًا مقداره 2^ n ^{- n} لكل سلسلة طولها n .

النظرية : مع التوزيع الاحتمالي المنتظم على فضاء سلاسل البتات ذات الطول n ، فإن احتمال أن تكون السلسلة غير قابلة للضغط بواسطة c هو على الأقل 1 − 2 ^{− c +1} + 2 ^{− n} .

لإثبات النظرية، لاحظ أن عدد الأوصاف التي لا يتجاوز طولها n − c يُعطى بواسطة المتسلسلة الهندسية:

لا يزال هناك على الأقل

سلاسل بتية بطول n غير قابلة للضغط بواسطة c . لتحديد الاحتمالية، اقسم على ²ⁿ .

بحسب النظرية المذكورة أعلاه ( قسم  الضغط )، فإن معظم السلاسل معقدة بمعنى أنه لا يمكن وصفها بأي طريقة "مضغوطة" بشكل ملحوظ. ومع ذلك، يتضح أنه لا يمكن إثبات تعقيد سلسلة معينة بشكل رسمي إذا تجاوز تعقيدها عتبة معينة. والصيغة الدقيقة لذلك هي كما يلي: أولًا، نحدد نظامًا بديهيًا معينًا S للأعداد الطبيعية . يجب أن يكون هذا النظام البديهي قويًا بما يكفي بحيث يمكن ربط صيغة F ∈ _A في S ببعض التأكيدات A حول تعقيد السلاسل . يجب أن تتمتع هذه الصيغة بالخاصية التالية:

إذا كان من الممكن إثبات F _A من بديهيات S ، فإن العبارة المقابلة A يجب أن تكون صحيحة. ويمكن تحقيق هذه "الصياغة الرسمية" بالاعتماد على ترقيم غودل .

نظرية : يوجد ثابت L (يعتمد فقط على S وعلى اختيار لغة الوصف) بحيث لا توجد سلسلة s يكون فيها البيان

${\displaystyle K(s)\geq L}$   (كما هو موضح في S )

يمكن إثبات ذلك ^ضمن S. [ ^{16 ] [ 17 ]}

فكرة البرهان : يُبنى برهان هذه النتيجة على نموذج البناء المرجعي الذاتي المستخدم في مفارقة بيري . نبدأ ببرنامج يُحصي البراهين ضمن المجموعة S ، ونُحدد إجراءً P يأخذ كمدخل عددًا صحيحًا L ويطبع السلاسل النصية x التي تقع ضمن براهين العبارة K ( x ) ≥ L في المجموعة S. بجعل L أكبر من طول هذا الإجراء P ، نجد أن الطول المطلوب لبرنامج يطبع x كما هو منصوص عليه في K ( x ) ≥ L ، أي L على الأقل ، يكون أقل من L لأن السلسلة النصية x طُبعت بواسطة الإجراء P. وهذا تناقض. لذا، لا يمكن لنظام البرهان S إثبات K ( x ) ≥ L لأي قيمة كبيرة لـ L ، وخاصةً عندما تكون L أكبر من طول الإجراء P (وهو طول محدود).

دليل :

يمكننا إيجاد تعداد فعال لجميع البراهين الرسمية في S من خلال إجراء ما

دالة إثبات الرتبة n ( n : عدد صحيح )

تأخذ هذه الدالة المدخل n وتُخرج برهانًا. تُحصي هذه الدالة جميع البراهين. بعض هذه البراهين هي براهين لصيغ لا تهمنا هنا، حيث يتم إنتاج كل برهان ممكن في لغة S لبعض قيم n . بعض هذه البراهين هي صيغ تعقيد من الشكل K ( s )  ≥ n، حيث s و n ثابتان في لغة S. هناك إجراء 

def nth_proof_proves_complexity_formula ( n : int ): bool

والذي يحدد ما إذا كان البرهان رقم n يثبت بالفعل صيغة التعقيد K ( s )  ≥ L. يمكن حساب السلاسل s ، والعدد الصحيح L بدوره، من خلال الإجراء التالي: 

دالة string_nth_proof ( n : int )

دالة التعقيد_الحد_الأدنى_للبرهان_الرقم_ن ( ن : عدد صحيح ): عدد صحيح

ضع في اعتبارك الإجراء التالي:

دالة توليد سلسلة معقدة قابلة للإثبات ( n : عدد صحيح ): من أجل i = 1 إلى ما لا نهاية : إذا كان البرهان النوني يثبت صيغة التعقيد ( i ) وكان الحد الأدنى للتعقيد للبرهان النوني ( i ) ≥ n، فأرجع سلسلة البرهان النوني ( i ).

بالنظر إلى${\displaystyle n}$، يحاول هذا الإجراء كل برهان حتى يجد سلسلة وبرهانًا في النظام الرسمي S للصيغة${\displaystyle K(s)\geq L}$بالنسبة للبعض${\displaystyle L\geq n}$إذا لم يكن هناك دليل من هذا القبيل، فإنها تدور في حلقة لا نهائية.

وأخيرًا، لننظر إلى البرنامج الذي يتكون من جميع تعريفات الإجراءات هذه، واستدعاء رئيسي:

generate_provably_complex_string ( n ₀ )

حيث الثابت${\displaystyle n_{0}}$سيتم تحديد ذلك لاحقًا. ويمكن التعبير عن المدة الإجمالية للبرنامج على النحو التالي:${\displaystyle U+log_{2}(n_{0})}$، أين${\displaystyle U}$هو ثابت ما و${\displaystyle log_{2}(n_{0})}$يمثل طول القيمة الصحيحة${\displaystyle n_{0}}$بافتراض معقول أنه مُشفّر بالأرقام الثنائية، سنختار${\displaystyle n_{0}}$أن يكون أكبر من طول البرنامج، أي بحيث${\displaystyle n_{0}>U+log_{2}(n_{0})}$وهذا ينطبق بوضوح على${\displaystyle n_{0}}$كبيرة بما يكفي، لأن الجانب الأيسر ينمو خطيًا في${\displaystyle n_{0}}$بينما ينمو الجانب الأيمن لوغاريتميًا في${\displaystyle n_{0}}$حتى قيمة ثابتة${\displaystyle U}$.

ثم لا يوجد دليل على الشكل "${\displaystyle K(s)\geq L}$" مع${\displaystyle L\geq n_{0}}$يمكن الحصول على ذلك في S ، كما يتضح من خلال وسيط غير مباشر : إذا complexity_lower_bound_nth_proof(i)كان بإمكانها إرجاع قيمة${\displaystyle \geq n_{0}}$ثم ستنتهي الحلقة الداخلية generate_provably_complex_stringفي النهاية، وسيعيد هذا الإجراء سلسلة نصية s بحيث

	${\displaystyle K(s)}$
≥	${\displaystyle n_{0}}$	عن طريق بناءgenerate_provably_complex_string
>	${\displaystyle U+log_{2}(n_{0})}$	باختيار${\displaystyle n_{0}}$
≥	${\displaystyle K(s)}$	منذ${\displaystyle s}$وقد وصفه البرنامج بهذا الطول

هذا تناقض، وهو المطلوب إثباته.

ونتيجة لذلك، فإن البرنامج المذكور أعلاه، بالقيمة المختارة لـ${\displaystyle n_{0}}$يجب أن تستمر العملية إلى الأبد.

تُستخدم أفكار مماثلة لإثبات خصائص ثابت تشايتين .

طُوِّر مبدأ الحد الأدنى لطول الرسالة في الاستدلال الإحصائي والاستقرائي والتعلم الآلي على يد سي إس والاس ودي إم بولتون عام ١٩٦٨. يُعدّ التعلم الآلي ذو الحد الأدنى لطول الرسالة (MML) بايزيًا (أي أنه يتضمن المعتقدات المسبقة) ونظريًا معلوماتيًا. ويتمتع بخصائص مرغوبة، منها الثبات الإحصائي (أي أن الاستدلال يتحول مع إعادة تحديد المعلمات، مثل التحويل من الإحداثيات القطبية إلى الإحداثيات الديكارتية)، والاتساق الإحصائي (أي أنه حتى في المسائل بالغة الصعوبة، يتقارب التعلم الآلي ذو الحد الأدنى لطول الرسالة مع أي نموذج أساسي)، والكفاءة (أي أن نموذج التعلم الآلي ذو الحد الأدنى لطول الرسالة يتقارب مع أي نموذج أساسي صحيح بأسرع ما يمكن). وقد أظهر سي إس والاس ودي إل داو (١٩٩٩) وجود صلة رسمية بين التعلم الآلي ذو الحد الأدنى لطول الرسالة ونظرية المعلومات الخوارزمية (أو تعقيد كولموغوروف). ^{[ ١٨ ]}

يُعرّف مبدأ كولموغوروف العشوائي سلسلةً (عادةً من البتات ) بأنها عشوائية إذا كان أقصر برنامج حاسوبي قادر على إنتاج تلك السلسلة يُقارب طول السلسلة نفسها. ولتوضيح ذلك بدقة، فإن السلسلة${\displaystyle x}$من الطول${\displaystyle n}$يُطلق عليه اسم عشوائية كولموغوروف إذا ${\displaystyle K(x)\geq n+O(1)}$أين${\displaystyle K}$هي تعقيد كولموغوروف الخالي من البادئات المعرّف أعلاه. السلسلة العشوائية بهذا المعنى غير قابلة للضغط ، إذ يستحيل ضغطها إلى برنامج أقصر منها. يوجد على الأقل سلسلة عشوائية واحدة من نوع كولموغوروف لكل طول. ^{[ 19 ]}

يمكن توسيع هذا التعريف ليشمل مفهوم العشوائية للمتتاليات اللانهائية من أبجدية محدودة. ويمكن تعريف هذه المتتاليات العشوائية خوارزميًا بثلاث طرق متكافئة. تستخدم إحدى الطرق نظيرًا فعالًا لنظرية القياس ؛ وتستخدم أخرى المارتينجالات الفعالة . أما الطريقة الثالثة، فتُعرّف المتتالية اللانهائية بأنها عشوائية إذا كان تعقيد كولموغوروف الخالي من البادئات لأجزائها الأولية ينمو بسرعة كافية  - أي يجب أن يكون هناك ثابت c بحيث يكون تعقيد جزء أولي طوله n دائمًا على الأقل n − c . ^{[ 20 ]}

بالنسبة للأنظمة الديناميكية، يرتبط معدل الإنتروبيا والتعقيد الخوارزمي للمسارات بنظرية برودنو، التي تنص على المساواة${\displaystyle K(x;T)=h(T)}$ينطبق على جميع الحالات تقريبًا${\displaystyle x}$[ ^{21 ]​}

يمكن إثبات ^{[ 22 ]} أن تعقيد كولموغوروف لمخرجات مصادر معلومات ماركوف يرتبط بإنتروبيا مصدر المعلومات. وبشكل أدق، فإن تعقيد كولموغوروف لمخرجات مصدر معلومات ماركوف، مُقسَّمًا على طول المخرجات، يتقارب تقريبًا بشكل مؤكد (عندما يؤول طول المخرجات إلى اللانهاية) مع إنتروبيا المصدر .

نظرية. (النظرية 14.2.5 ^{[ 23 ]} ) تعقيد كولموغوروف الشرطي لسلسلة ثنائية${\displaystyle x_{1:n}}$يرضي$${\displaystyle {\frac {1}{n}}K(x_{1:n}|n)\leq H_{b}\left({\frac {1}{n}}\sum _{i}x_{i}\right)+{\frac {\log n}{2n}}+O(1/n)}$$أين${\displaystyle H_{b}}$هي دالة الإنتروبيا الثنائية (لا ينبغي الخلط بينها وبين معدل الإنتروبيا).

دالة تعقيد كولموغوروف تعادل حل مشكلة التوقف.

إذا كان لدينا أوراكل متوقف، فيمكن حساب تعقيد كولموغوروف لسلسلة ما ببساطة عن طريق تجربة كل برنامج متوقف، بالترتيب المعجمي، حتى يقوم أحدهم بإخراج السلسلة.

أما الاتجاه الآخر فهو أكثر تعقيدًا بكثير. ^{[ 24 ] [ 25 ]} يُظهر أنه بمعرفة دالة تعقيد كولموغوروف، يمكننا بناء دالة${\displaystyle p}$بحيث${\displaystyle p(n)\geq BB(n)}$لجميع الأحجام الكبيرة${\displaystyle n}$، أين${\displaystyle BB}$هي دالة الإزاحة Busy Beaver (يشار إليها أيضًا باسم${\displaystyle S(n)}$). عن طريق تعديل الدالة عند قيم أقل من${\displaystyle n}$نحصل على حد أعلى لـ${\displaystyle BB}$، مما يحل مشكلة التوقف.

ضع هذا البرنامج في الاعتبار${\textstyle p_{K}}$، والذي يأخذ المدخلات كـ${\textstyle n}$، ويستخدم${\textstyle K}$.

• اعرض جميع السلاسل النصية ذات الطول${\textstyle \leq 2n+1}$.
• لكل سلسلة من هذا القبيل${\textstyle x}$، قم بتعداد جميع البرامج (الخالية من البادئات) ذات الطول${\displaystyle K(x)}$إلى أن يقوم أحدهم بإخراج البيانات${\textstyle x}$سجل وقت تشغيله${\textstyle n_{x}}$.
• أنتج أكبر قدر${\textstyle n_{x}}$.

نثبت بالتناقض أن${\textstyle p_{K}(n)\geq BB(n)}$لجميع الأحجام الكبيرة${\textstyle n}$.

يترك${\textstyle p_{n}}$كن قندسًا نشيطًا من طول${\displaystyle n}$. لنفترض هذا البرنامج (الخالي من البادئات)، والذي لا يأخذ أي مدخلات:

• قم بتشغيل البرنامج${\textstyle p_{n}}$وسجل مدة تشغيله${\textstyle BB(n)}$.
• قم بإنشاء جميع البرامج ذات الطول${\textstyle \leq 2n}$قم بتشغيل كل واحد منها لمدة تصل إلى${\textstyle BB(n)}$الخطوات. لاحظ مخرجات تلك التي توقفت.
• أخرج السلسلة ذات الترتيب المعجمي الأدنى التي لم يتم إخراجها بواسطة أي من تلك السلاسل.

لنفترض أن السلسلة النصية التي يُخرجها البرنامج هي${\textstyle x}$.

مدة البرنامج${\textstyle \leq n+2\log _{2}n+O(1)}$، أين${\displaystyle n}$يأتي من طول القندس المشغول${\textstyle p_{n}}$،${\displaystyle 2\log _{2}n}$يأتي ذلك من استخدام رمز دلتا إلياس (الخالي من البادئات) للرقم${\displaystyle n}$، و${\displaystyle O(1)}$يأتي ذلك من بقية البرنامج. لذلك،$${\displaystyle K(x)\leq n+2\log _{2}n+O(1)\leq 2n}$$لجميع الكبار${\textstyle n}$علاوة على ذلك، بما أن عدد البرامج الممكنة ذات الطول محدود${\textstyle \leq 2n}$لدينا${\textstyle l(x)\leq 2n+1}$بحسب مبدأ التوزيع . بافتراض،${\textstyle p_{K}(n)<BB(n)}$لذا فإن كل سلسلة بطول${\textstyle \leq 2n+1}$يحتوي على برنامج بسيط مع وقت تشغيل${\textstyle <BB(n)}$وبالتالي، فإن السلسلة${\textstyle x}$يحتوي على برنامج بسيط مع وقت تشغيل${\textstyle <BB(n)}$علاوة على ذلك، فإن هذا البرنامج له طول${\textstyle K(x)\leq 2n}$وهذا يتناقض مع كيفية${\textstyle x}$تم بناؤه.

إصلاح آلة تورينج العالمية${\displaystyle U}$، وهو نفس المستخدم لتعريف تعقيد كولموغوروف (بدون بادئات). عرّف الاحتمالية العامة (بدون بادئات) لسلسلة نصية${\displaystyle x}$يكون$${\displaystyle P(x)=\sum _{U(p)=x}2^{-l(p)}}$$بمعنى آخر، هو احتمال أن تتوقف آلة تورينج العالمية، عند إدخال سلسلة ثنائية عشوائية بشكل منتظم، بعد قراءة بادئة معينة من السلسلة، ثم تُخرج${\displaystyle x}$.

ملحوظة.${\displaystyle U(p)=x}$لا يعني ذلك أن دفق الإدخال هو${\displaystyle p000\cdots }$لكن آلة تورينج العالمية ستتوقف عند نقطة ما بعد قراءة الجزء الأولي.${\displaystyle p}$دون قراءة أي مدخلات أخرى، وعندما يتوقف، يكون قد كتب${\displaystyle x}$إلى شريط الإخراج.

نظرية. (النظرية 14.11.1 ^{[ 23 ]} )${\displaystyle \log {\frac {1}{P(x)}}=K(x)+O(1)}$

استُخدم مفهوم تعقيد كولموغوروف في علم الأحياء للتأكيد على أن التناظرات والترتيبات المعيارية الملاحظة في أنواع متعددة تنشأ من ميل التطور إلى تفضيل الحد الأدنى من تعقيد كولموغوروف. ^{[ 26 ]} وبالنظر إلى الجينوم كبرنامج يجب أن يحل مهمة أو ينفذ سلسلة من الوظائف، فإن البرامج الأقصر تُفضّل لكونها أسهل في الاكتشاف بواسطة آليات التطور. ^{[ 27 ]} ومن الأمثلة على هذا النهج التناظر الثماني لدائرة البوصلة الموجودة في جميع أنواع الحشرات، والتي تتوافق مع الدائرة الوظيفية التي تتطلب الحد الأدنى من تعقيد كولموغوروف لتوليدها من وحدات ذاتية التضاعف. ^{[ 28 ]}

تعقيد كولموغوروف الشرطي لسلسلتين${\displaystyle K(x|y)}$يُعرَّف تعقيد كولموغوروف، بشكل تقريبي، بأنه تعقيد كولموغوروف لـ x بمعلومية y كمدخل مساعد للإجراء. ^{[ 29 ] [ 30 ]} لذا، بينما تعقيد كولموغوروف (غير المشروط)${\displaystyle K(x)}$من تسلسل${\displaystyle x}$يمثل طول أقصر برنامج ثنائي يُخرج${\displaystyle x}$على جهاز كمبيوتر عالمي، ويمكن اعتبارها الحد الأدنى من المعلومات اللازمة لإنتاج${\displaystyle x}$، تعقيد كولموغوروف الشرطي${\displaystyle K(x|y)}$يُعرَّف بأنه طول أقصر برنامج ثنائي يقوم بحساب${\displaystyle x}$متى${\displaystyle y}$يتم إدخالها كمدخلات باستخدام حاسوب عالمي. ^{[ 31 ]}

يوجد أيضًا تعقيد مشروط بالطول${\displaystyle K(x|L(x))}$، وهو تعقيد x بمعلومية طول x كمدخل. ^{[ 32 ] [ 33 ]}

يُعدّ تعقيد كولموغوروف المحدود زمنيًا نسخةً مُعدّلة من تعقيد كولموغوروف، حيث يقتصر نطاق البرامج المطلوب البحث فيها عن حل على البرامج التي يمكن تشغيلها ضمن عدد مُحدّد مُسبقًا من الخطوات. ^{[ 34 ]} يُفترض أن إمكانية وجود خوارزمية فعّالة لتحديد تعقيد كولموغوروف التقريبي المحدود زمنيًا ترتبط بمسألة وجود دوال أحادية الاتجاه حقيقية . ^{[ 35 ] [ 36 ]}

• مفارقة التوت
• لعبة الجولف البرمجية
• ضغط البيانات
• نظرية التعقيد الوصفي
• الاستقراء النحوي
• الاستدلال الاستقرائي
• دالة بنية كولموغوروف
• مسافة ليفنشتاين
• فرضيات متعددة
• نظرية سولومونوف للاستدلال الاستقرائي
• إنتروبيا العينة
• رقم رايو

• بلوم، م. (1967). "حول حجم الآلات" . المعلومات والتحكم . 11 (3): 257. doi : 10.1016/S0019-9958(67)90546-3 .
• برودنو، أ. (1983). "الإنتروبيا وتعقيد مسارات النظام الديناميكي". معاملات جمعية موسكو الرياضية . 2 : 127-151 .
• كوفر، توماس م.؛ توماس، جوي أ. (2006). عناصر نظرية المعلومات (  الطبعة الثانية). وايلي-إنترساينس. ISBN 0-471-24195-4.
• لايوس، رونياي؛ غابور، إيفانيوس؛ ريكا، زابو (1999). الخوارزمية . تايبوتكس. رقم ISBN 963-279-014-6.
• لي مينغ. فيتاني، بول (1997). مقدمة لتعقيد كولموجوروف وتطبيقاته . سبرينغر. رقم ISBN 978-0-387-33998-6.
• يو، مانين (1977). دورة في المنطق الرياضي . سبرينغر-فيرلاغ. ISBN 978-0-7204-2844-5.
• سيبسر، مايكل (1997). مقدمة في نظرية الحوسبة . دار نشر PWS. رقم ISBN 0-534-95097-3.
• داوني، رودني ج.؛ هيرشفيلدت، دينيس ر. (2010). "العشوائية والتعقيد الخوارزمي" . نظرية وتطبيقات الحوسبة . doi : 10.1007/978-0-387-68441-3 . ISBN 978-0-387-95567-4ISSN 2190-619X​​ 

• تراث أندريه نيكولايفيتش كولموغوروف
• منشورات تشايتين على الإنترنت
• صفحة سولومونوف على موقع IDSIA
• تعميمات المعلومات الخوارزمية بقلم ج. شميدهوبر
• "مراجعة لي فيتاني 1997" .
• ترومب، جون. "ملعب جون لحساب التفاضل والتكامل لامدا والمنطق التوافقي" .يقدم نموذج حساب التفاضل والتكامل اللامدا الخاص بترومب تعريفًا ملموسًا لـ K()]
• الذكاء الاصطناعي الشامل القائم على تعقيد كولموغوروف (ISBN) 3-540-22139-5بقلم م. هوتر : رقم ISBN 3-540-22139-5
• الحد الأدنى لطول الرسالة (MML) لديفيد داو وصفحات أوكام .
• غرونوالد، ب.؛ بيت، م.أ. (2005). ميونغ، إ.ج. (محرر). التطورات في الحد الأدنى لطول الوصف: النظرية والتطبيقات . مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 0-262-07262-9.