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

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

توضح هذه الصورة جزء من مجموعة ماندلبروت كسورية قد يتطلب تخزين لون 24 بت لكل بكسل في هذه الصورة ببساطة 1.61 مليون بايت، ولكن يمكن لبرنامج كمبيوتر صغير إعادة إنتاج هذه 1.61 مليون بايت باستخدام تعريف مجموعة Mandelbrot وإحداثيات زوايا الصورة. وبالتالي، فإن تعقيد Kolmogorov للملف الخام الذي يشفر هذه الصورة النقطية أقل بكثير من 1.61 مليون بايت في أي نموذج عملي للحساب.

نبذة

هو مقياس للموارد الحسابية اللازمة لتحديد الكائن، ويعرف أيضاً بالتعقيد الخوازمي أو تعقيد سليمانوف -كولموغوروف -تشايتين، أو تعقيد حجم البرنامج، أو التعقيد الوصفي، أو التكعيب الخوارزمي. سميت على اسم أندريه كولموغوروف، الذي نشر لأول مرة حول هذا الموضوع في عام 1963.

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

تعريف

ضع في اعتبارك السلاسل التالية المكونة من 32 حرفًا ورقمًا صغيرًا:

abababababababababababababababab ،

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

تحتوي السلسلة الأولى على وصف قصير باللغة الإنجليزية، وهو «كتابة ab 16 مرة»، والذي يتكون من 17 حرفًا، الثاني ليس لديه وصف بسيط واضح (باستخدام نفس مجموعة الأحرف) بخلاف كتابة السلسلة نفسها، أي «كتابة 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7» الذي يحتوي على 38 حرفا وبالتالي يمكن القول إن عملية كتابة السلسلة الأولى تحتوي على «تعقيد أقل» من كتابة السلسلة الثانية.

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

يمكن تعريف تعقيد كولموغروف لأي كائن رياضي، ولكن من أجل البساطة يقتصر نطاق هذه المقالة على سلاسل. يجب علينا أولاً تحديد لغة وصف للسلاسل. يمكن أن تستند لغة الوصف هذه إلى أي لغة برمجة حاسوبية، مثل Lisp أو Pascal أو Java. إذا كان P هو برنامج الذي يخرج سلسلة x، ف هو وصف x. طول الوصف هو فقط طول P كسلسلة أحرف، مضروباً في عدد البتات في حرف (على سبيل المثال، 7 لـ ASCII).

يمكننا، بدلا من ذلك، اختيار ترميز لآلات تورينج، حيث ترميز هو وظيفة الذي يربط مع كل آلة تورينج M <M>. إذا كان M هو آلة تورينج التي، على المدخلات ث، إخراج سلسلة x، ثم سلسلة متسلسلة <M>w هو وصف x. وللتحلي بالتحليل النظري، فإن هذا النهج أكثر ملاءمة لبناء براهين رسمية مفصلة ويفضل عموما في الأدبيات البحثية. في هذه المقالة، يتم مناقشة نهج غير رسمي.

أي سلسلة s له وصف واحد على الأقل. على سبيل المثال، السلسلة الثانية أعلاه هو الإخراج بواسطة البرنامج:

الوظيفة GenerateString2 ()
إرجاع "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

بينما السلسلة الأولى هي الإخراج بواسطة (أقصر بكثير) الزائفة رمز:

الوظيفة GenerateString1 ()
إرجاع "ab" × 16

إذا كان وصف d(s) من سلسلة s من الحد الأدنى من الطول (أي، باستخدام أقل بتات)، يطلق عليه وصف الحد الأدنى من s، وطول d(s) (أي عدد البتات في وصف الحد الأدنى) هو تعقيد كولموغروف من s، K (s) مكتوبة). رمزيا

K(s) = |d(s)|.

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

نظرية الثبات

العلاج غير الرسمي

هناك بعض اللغات الوصف التي هي الأمثل، في المعنى التالي: نظرا لأي وصف لكائن في لغة وصف، ووصف وقال يمكن استخدامها في لغة وصف الأمثل مع النفقات العامة ثابتة. يعتمد الثابت فقط على اللغات المتضمنة، وليس على وصف الكائن، ولا على الكائن الذي يتم وصفه.

هنا مثال على لغة وصف الأمثل. سيكون للوصف جزأين:

• يصف الجزء الأول لغة وصف أخرى.
• الجزء الثاني هو وصف للكائن بهذه اللغة.

من الناحية التقنية أكثر، فإن الجزء الأول من الوصف هو برنامج كمبيوتر، والجزء الثاني هو المدخل إلى هذا البرنامج الحاسوبي الذي ينتج الكائن كخرج.

تتبع نظرية الثبات مايلي: نظرا لأي وصف اللغة L، لغة وصف الأمثل على الأقل كفاءة L، مع بعض النفقات العامة المستمرة.

دليل: يمكن تحويل أي وصف D في L إلى وصف في اللغة المثلى عن طريق وصف أولاً L كـ P برنامج كمبيوتر (جزء 1)، ثم ثم استخدام الوصف الأصلي D كمدخلات إلى هذا البرنامج (الجزء 2). طول هذا الوصف الجديد D′ هو (تقريبا):

|D′| = |P| + |D|

طول P هو ثابت لا يعتمد على D. لذلك، هناك على الأكثر الحمل ثابت بغض النظر عن الكائن الموصوفة. لذلك، اللغة المثلى هي عالمية حتى هذا ثابت المضافة.

علاج أكثر رسمية

نظرية: إذا K1 وK2 هي وظائف التعقيد بالنسبة لاللغات وصف تورينج كاملة L1 و L2، ثم هناك c ثابت - الذي يعتمد فقط على اللغات L1 و L2 المختارة - مثل أن

∀s. −c ≤ K₁(s) − K₂(s) ≤ c.

دليل: عن طريق التماثل، يكفي أن يثبت أن هناك بعض c ثابت مثل أن لجميع السلاسل s

K₁(s) ≤ K₂(s) + c.

الآن، لنفترض أن هناك برنامج في اللغة L1 الذي يعمل كمترجم لL2:

وظيفة InterpretLanguage(سلسلة p)

حيث p هو برنامج في L₂ . يتميز المترجم بالخاصية التالية:

تشغيل InterpretLanguage على إدخال p إرجاع نتيجة تشغيل p.

وهكذا، إذا P هو برنامج في L2 وهو وصف الحد الأدنى من s ثم InterpretLanguage(P) إرجاع سلسلة s. طول هذا الوصف s هو مجموع

1. طول برنامج InterpretLanguage، والتي يمكننا أن نتخذها لتكون c ثابت.
2. طول P الذي هو بحكم التعريف K2 (s).

وهذا يثبت الحد العلوي المطلوب.

التاريخ والسياق

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

ويستند مفهوم ونظرية تعقيد كولموغوروف على نظرية حاسمة اكتشفت لأول مرة من قبل راي سولومونوف، الذي نشرها في عام 1960، واصفا إياه في «تقرير أولي عن نظرية عامة للاستدلال الاستقرائي» كجزء من اختراعه للاحتمالية الخوارزية. وقدم وصفاً أكثر اكتمالاً في منشوراته الصادرة عام 1964 بعنوان «نظرية رسمية للاستدلال الاستقرائي» والجزء الأول والجزء الثاني في المعلومات والتحكم.

نشر أندريه كولموغوروف في وقت لاحق بشكل مستقل هذه النظرية في المشاكل إبلاغ. انتقال العدوى في عام 1965. كما يقدم غريغوري شايتين هذه النظرية في J. ACM – قدمت ورقة شايتين أكتوبر 1966 ونقحت في ديسمبر 1968، وتستشهد بكل من أوراق سولومونوف وكولموغوروف.

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

عندما Kolmogorov أصبح على بينة من Solomonoff العمل، اعترف Solomonoff ذات الأولوية. لعدة سنوات، Solomonoff عمل المعروف في الاتحاد السوفياتي في العالم الغربي. التوافق العام في الآراء في المجتمع العلمي، ومع ذلك، تم ربط هذا النوع من التعقيد مع Kolmogorov ، يهتم العشوائية من سلسلة، في حين حسابي احتمال أصبحت مرتبطة مع Solomonoff ، الذي ركز على التنبؤ باستخدام اختراعه العالمية قبل توزيع الاحتمالات. المجال الأوسع نطاقا تشمل descriptional التعقيد احتمال وغالبا ما تسمى Kolmogorov التعقيد. في عالم الكمبيوتر مينغ لي ترى هذا مثال على تأثير ماثيو: «...إلى كل من لديه أكثر سوف تعطى...»

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

وقدم مارك بورغين نهجا بديهيا لتعقيد كولموغوروف استنادا إلى بديهيات بلوم (Blum 1967) في الورقة التي قدمها أندريه كولموغوروف للنشر.

النتائج الأساسية

في المناقشة التالية، اسمحوا K (s) يكون تعقيد سلسلةs .

ليس من الصعب أن نرى أن وصف الحد الأدنى من سلسلة لا يمكن أن يكون أكبر بكثير من السلسلة نفسها — برنامج GenerateString2 أعلاه أن المخرجات s هو مبلغ ثابت أكبر من s.

نظرية : هناك ثابت c مثل هذا

∀s. K(s) ≤ |s| + c.

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

محاولة ساذجة في برنامج لحساب K.

للوهلة الأولى قد يبدو تافها لكتابة البرنامج الذي يمكن حساب K (s) لأي s ، مثل ما يلي:

وظيفة تعقيد كولموغروف (سلسلة)
بالنسبة إلى i = 1 إلى ما لا نهاية:
لكل p سلسلة من طول بالضبط i
إذا (p) برنامج قيدي وتقييم (p) == الصورة
 العودة i

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

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

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

دليل رسمي على عدم قابلية الحوسبة لـ K.

النظرية : هناك وجود سلاسل من تعقيد كولموغوروف كبيرة بشكل تعسفي. شكليا: لكل n ∈ N، هناك سلسلة s مع K (s) ≥ n.

برهان: وإلا فإن كل من سلاسل محدودة ممكن لا نهائي يمكن أن يتم إنشاؤها بواسطة برامج كثيرة محدودة مع تعقيد أقل من ن بت.

النظرية : K ليست دالة قابلة للحوسبة. بمعنى آخر، لا يوجد أي برنامج الذي يأخذ أي سلسلة s كإدخال وتنتج K (ق) الصحيح كخرج.

يستخدم الدليل غير المباشر التالي لغة بسيطة تشبه باسكال للدلالة على البرامج؛ من أجل إثبات البساطة تفترض وصفها (أي مترجم) أن يكون طول 1400000 بت. افترض للتناقض هناك برنامج

وظيفة تعقيد كولموغروف (سلسلة)

الذي يأخذ كإدخال سلسلة s وإرجاع K(s). جميع البرامج هي من طول محدود لذلك، من أجل إثبات البساطة، يفترض أن يكون 7000000000 بت. الآن، والنظر في البرنامج التالي من طول 1288 بت:

الوظيفة إنشاء سلسلة مكونات ()
بالنسبة إلى i = 1 إلى ما لا نهاية:
لكل سلسلة من الطول بالضبط i 
إذا تعقيد كولموغروف (s) ≥ 8000000000
 عودة s

باستخدام تعقيد كولموغروف (KolmogorovComplexity) باعتبارها روتين، البرنامج يحاول كل سلسلة، بدءا من أقصر، حتى يعود سلسلة مع تعقيد Kolmogorov ما لا يقل عن 800000000000 بت، أي سلسلة التي لا يمكن أن تنتج من قبل أي برنامج أقصر من 8000000000 بت. ومع ذلك، فإن الطول الإجمالي للبرنامج أعلاه الذي أنتج s هو فقط 7001401288 بت، وهو تناقض. (إذا كان رمز كولموغوروفاللمرف أقصر، يبقى التناقض. إذا كان أطول، يمكن دائماً تغيير الثابت المستخدمة في إنشاء سلسلة مكونات (GenerateComplexString) بشكل مناسب.)

يستخدم الدليل أعلاه تناقض مشابه لتلك التي من مفارقة بيري: «1The 2smallest 3positive 4integer 5that 6cannot 7be 8 9في 10 أقل 11than 12twenty 13English 14words». ومن الممكن أيضا أن تظهر عدم قابلية K للحوسبة عن طريق الحد من عدم قابلية الحوسبة لمشكلة التوقف H، لأن K وH هي تورينج ما يعادل.

هناك نتيجة طبيعية، ودعا روح الدعابة «نظرية العمالة الكاملة» في مجتمع لغة البرمجة، مشيرا إلى أنه لا يوجد الكمال الحجم الأمثل المترجم.

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

قاعدة سلسلة لتعقيد كولموغوروف تنص على أن

K (X ، Y) ≤ K (X) + K (Y | X) + O (تسجيل (K (X ، Y))).

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

ضغط

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

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

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

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

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

1 + 2 + 2 ² +… + 2 ^{n - c} = 2 ^{n - c +1} - 1.

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

2 ^ن - 2 ^{ن - ج +1} + 1

سلاسل بت بطول n لا يمكن ضغطها بواسطة c . لتحديد الاحتمال، قسّم على 2 ⁿ .

نظرية عدم اكتمال شيتين

تعقيد Kolmogorov K(s) ، واثنان من الوظائف prog1(s) ، prog2(s) . المحور الأفقي ( مقياس لوغاريتمي) تعداد كافة السلاسل الصورة، التي أمر بها طول. المحور الرأسي (مقياس خطي) يقيس تعقيد كولموغوروف في بت . معظم السلاسل غير قابلة للضغط، أي أن تعقيدها كولموغروف يتجاوز طولها بمقدار ثابت. تظهر 9 سلاسل مضغوطة في الصورة، تظهر على شكل منحدرات عمودية تقريبًا. نظرًا لنظرية عدم اكتمال Chaitin (1974)، لا يمكن أن يتجاوز ناتج أي برنامج يحسب حدًا أدنى من تعقيد Kolmogorov حدًا ثابتًا، وهو مستقل عن سلسلة الإدخال s .

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

إذا كانت F _A يمكن إثباتها من بديهيات S ، فيجب أن يكون التأكيد المقابل A صحيحًا. يمكن تحقيق هذا «الشكل الرسمي» بناءً على ترقيم Gödel .

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

K(s) ≥ L       (كما هو رسمي in S)

يمكن إثباتها داخل S.

الدليل : تم تصميم الدليل على هذه النتيجة على أساس بناء مرجعي ذاتي مستخدم في مفارقة بيري .

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

وظيفة NthProof (int n)

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

الدالة NthProofProvesComplexityFormula (int n)

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

الوظيفة StringNthProof (int n)

تعقيد الوظيفة LowBoundNth Proof (int n)

دالة GenerateProvablyComplexString (int n)
بالنسبة إلى i = 1 إلى ما لا نهاية:
إذا كانت NthProofProvesComplexityFormula (i) و ComplexityLowerBoundNthProof (i) ≥ n
إرجاع StringNthProof (i)

بالنظر إلى n ، يحاول هذا الإجراء كل دليل حتى يعثر على سلسلة ودليل في النظام الرسمي S للصيغة K (s) ≥ L لبعض L ≥ ن ؛ إذا لم يوجد مثل هذا الدليل، فإنه يدور إلى الأبد.

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

GenerateProvablyComplexString (ن 0)

حيث سيتم تحديد الثابت n _{0 لاحقًا.} يمكن التعبير عن الطول الإجمالي للبرنامج كـ U + log ₂ (n ₀)، حيث U عبارة عن ثابت معين ويمثل السجل ₂ (n ₀) طول قيمة العدد الصحيح n ₀ ، وفقًا للافتراض المعقول بأنه مشفر بأرقام ثنائية . الآن ضع في اعتبارك الوظيفة f : [2، ∞) → [1، ∞)، المحددة بواسطة f (x) = x − log ₂ (x). إنها تتزايد بشكل صارم في مجالها، وبالتالي لها معكوس f ⁻¹ : [1، ∞) → [2، ∞).

حدد n ₀ = f ⁻¹ (U) +1.

ثم لا يمكن الحصول على دليل على النموذج " K (s) ≥ L " مع L ≥ n ₀ في S ، كما يمكن رؤيته من خلال وسيطة غير مباشرة: إذا كان ComplexityLowerBoundNthProof(i) إرجاع قيمة ≥ n ₀ ، فإن الحلقة داخل GenerateProvablyComplexString سينتهي في النهاية، وهذا الإجراء سيعيد سلسلة نصية مثل

	ك (ق)
≥	ن 0		عن طريق إنشاء GenerateProvablyComplexString
>	U + سجل 2 (ن 0)		بما أن n 0 > f −1 (U) تعني n 0 − السجل 2 (n 0) = f (n 0)> U
≥	ك (ق)		منذ الصورة التي وصفها البرنامج مع أن طول

هذا تناقض، QED

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

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

الحد الأدنى لطول الرسالة

تم تطوير مبدأ الحد الأدنى لطول الرسالة للاستدلال الإحصائي والاستقرائي والتعلم الآلي بواسطة CS Wallace و DM Boulton في عام 1968. MML هي نظرية بايزي (أي أنها تتضمن معتقدات سابقة) ونظرية معلومات. لها الخصائص المرغوبة للثوابت الإحصائية (أي أن الاستدلال يتحول مع إعادة تحديد المعلمات، مثل من الإحداثيات القطبية إلى الإحداثيات الديكارتية)، والاتساق الإحصائي (على سبيل المثال ، حتى بالنسبة للمشاكل الصعبة للغاية ، سوف تتقارب MML مع أي نموذج أساسي) والكفاءة (أي أن نموذج MML سوف يتقارب مع أي نموذج أساسي حقيقي بأسرع ما يمكن). أظهر CS Wallace و DL Dowe (1999) علاقة رسمية بين MML ونظرية المعلومات الخوارزمية (أو تعقيد Kolmogorov).

عشوائية كولموغوروف

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

يمكن توسيع هذا التعريف لتعريف مفهوم العشوائية للتسلسلات اللانهائية من الأبجدية المحدودة. يمكن تعريف هذه التسلسلات العشوائية خوارزميًا بثلاث طرق مكافئة. طريقة واحدة تستخدم التناظرية الفعالة لنظرية القياس؛ آخر يستخدم مارتينجاليس فعالة. الطريقة الثالثة تحدد التسلسل اللانهائي ليكون عشوائيًا إذا كان تعقيد كولموغروف الخالي من البادئات ينمو بسرعة كافية - يجب أن يكون هناك ثابت c بحيث يكون تعقيد الجزء الأولي من الطول n دائمًا على الأقل n - c . هذا التعريف ، على عكس تعريف العشوائية لسلسلة محدودة ، لا يتأثر بالآلة العامة المستخدمة لتحديد تعقيد Kolmogorov الخالي من البادئات.

العلاقة بالانتروبيا

بالنسبة للأنظمة الديناميكية ، يرتبط معدل الانتروبيا والتعقيد الحسابي للمسارات بنظرية Brudno ، وهي أن المساواة $K(x;T)=h(T)$ يحمل للجميع تقريبا $x$.

ويمكن أن تظهر التي لإخراج مصادر المعلومات ماركوف ، ويرتبط كولموجوروف التعقيد إلى الكون من مصدر المعلومات. بتعبير أدق ، فإن تعقيد Kolmogorov لإخراج مصدر معلومات Markov ، الذي تم تطبيعه بطول الناتج ، يتقارب بشكل شبه مؤكد (حيث يذهب طول المخرجات إلى اللانهاية) إلى إنتروبيا المصدر.

الإصدارات الشرطية

تعقيد Kolmogorov المشروط لسلسلتين $K(x|y)$ يُعرَّف ، بشكل تقريبي ، بأنه تعقيد Kolmogorov لـ x معطى y كمدخل مساعد للإجراء.

انظر أيضًا

• ضغط بيانات
• دموسين