تعقيد كولموغروف
المحتويات
- ضغط
- لكل p سلسلة من طول بالضبط i
- الوظيفة إنشاء سلسلة مكونات
- نبذة
- قاعدة سلسلة لتعقيد كولموغوروف تنص على أن
- التاريخ والسياق
- علاج أكثر رسمية
- الإصدارات الشرطية
- عشوائية كولموغوروف
- نظرية : هناك ثابت c مثل هذا
- الحد الأدنى لطول الرسالة
- عدم قابلية الحوسبة لتعقيد كولموغوروف
- لا يزال هناك على الأقل
- 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7
- تعريف
- العودة i
- العلاقة بالانتروبيا
- إرجاع "ab" × 16
- عودة s
- نظرية عدم اكتمال شيتين
- النتائج الأساسية
- العلاج غير الرسمي
- الوظيفة GenerateString2
- هذا تناقض، QED

في البداية، تعقيد كولموغروف في نظرية المعلومات الخوارزمية (وهو حقل فرعي من علوم الكمبيوتر والرياضيات)، تعقيد كولموغروف كائن، مثل قطعة من النص، هو طول أقصر برنامج كمبيوتر (بلغة برمجة محددة سلفا) التي تنتج الكائن والإخراج. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
ضغط
1 + 2 + 2 2 +… + 2 n - c = 2 n - c +1 - 1.
وفي هذا الصدد، للسبب نفسه، فإن أغلب السلاسل معقدة بمعنى أنه لا يمكن ضغطها إلى حدّ كبير - K (s) الخاصة بهم ليست أصغر بكثير من – s – ، طول s بالبتات. لجعل هذا دقيقًا، حدد قيمة n . هناك 2 ن سلاسل بت بطول n . التوزيع الاحتمالي المنتظم على مساحة سلاسل البت هذه يعين وزنًا متساويًا تمامًا 2 - n لكل سلسلة بطول n .
إضافةً إلى ذلك، فمن السهل لحساب الحدود العليا لK (s) – ببساطة ضغط سلسلة s مع بعض الأسلوب، وتنفيذ إلغاء ضغط المقابلة في اللغة المختارة، وسلسلة من إلغاء الضغط إلى سلسلة مضغوط، وقياس طول السلسلة الناتجة – بشكل ملموس، وحجم أرشيف استخراج ذاتي في اللغة معينة.
وعلى صعيد آخر، لإثبات النظرية، لاحظ أن عدد أوصاف الطول التي لا تتجاوز n - c تُعطى بواسطة السلسلة الهندسية:
علاوةً على ذلك، النظرية : مع التوزيع الاحتمالي المنتظم على مساحة سلاسل البت ذات الطول n ، يكون احتمال أن تكون السلسلة غير قابلة للضغط بواسطة c على الأقل 1 - 2 - c +1 + 2 - n .
إضافةً إلى ذلك، تكون السلسلة s قابلة للضغط برقم c إذا كان لها وصف لا يتجاوز طوله | الصورة | - ج بت. هذا يعادل القول بأن K (s) ≤ | الصورة | - ج . خلاف ذلك، يكون s غير قابل للضغط بواسطة c . يُقال إن السلسلة غير القابلة للضغط بمقدار 1 هي ببساطة غير قابلة للضغط - بحسب مبدأ pigeonhole ، الذي ينطبق لأن كل سلسلة مضغوطة ترسم إلى سلسلة واحدة غير مضغوطة فقط، يجب أن توجد سلاسل غير قابلة للضغط ، نظرًا لوجود سلاسل 2 n بت بطول n ، ولكن سلاسل أقصر 2 n - 1 فقط، أي سلاسل بطول أقل من n (أي بطول 0، 1... n - 1). As there are strings of length L, the number of strings of lengths is = , which is a finite geometric series with sum
لكل p سلسلة من طول بالضبط i
إذا (p) برنامج قيدي وتقييم (p) == الصورة
الوظيفة إنشاء سلسلة مكونات
- بالنسبة إلى i = 1 إلى ما لا نهاية:
- لكل سلسلة من الطول بالضبط i
- إذا تعقيد كولموغروف (s) ≥ 8000000000
نبذة
وعلى صعيد آخر، هو مقياس للموارد الحسابية اللازمة لتحديد الكائن، ويعرف كذلك بالتعقيد الخوازمي أو تعقيد سليمانوف -كولموغوروف -تشايتين، أو تعقيد حجم البرنامج، أو التعقيد الوصفي، أو التكعيب الخوارزمي. سميت على اسم أندريه كولموغوروف، الذي نشر لأول مرة حول هذا الموضوع في سنة 1963.
من جهة ثانية، ويمكن استخدام مفهوم تعقيد كولموغوروف في الدولة وإثبات نتائج الاستحالة أقرب إلى حجة كانتور القطرية، نظرية غوديل غير المكتملة، ومشكلة تورينج المتوقفة. على وجه الخصوص، لا يمكن لأي برنامج P حساب الحد الأدنى لتعقيد كولموغروف كل نص إرجاع قيمة أكبر أساسا من طول P الخاصة (انظر المقطع § Chaitin's نظرية عدم اكتمال); وبالتالي لا يمكن لأي برنامج واحد حساب تعقيد كولموغوروف الدقيق للعديد من النصوص بلا حدود.
قاعدة سلسلة لتعقيد كولموغوروف تنص على أن
كذلك، تنص على أن أقصر برنامج يعيد إنتاج X و Y ليس أكثر من مصطلح لوغاريتمي أكبر من برنامج إعادة إنتاج X وبرنامج لإعادة إنتاج Y معطى X. باستخدام هذا البيان، يمكن للمرء تحديد تناظرية للمعلومات المتبادلة لتعقيد Kolmogorov .
K (X ، Y) ≤ K (X) + K (Y – X) + O (تسجيل (K (X ، Y))).
التاريخ والسياق
علاوةً على ذلك، نشر أندريه كولموغوروف في وقت لاحق بشكل مستقل هذه النظرية في المشاكل إبلاغ. انتقال العدوى في سنة 1965. كما يقدم غريغوري شايتين هذه النظرية في J. ACM – قدمت ورقة شايتين أكتوبر 1966 ونقحت في ديسمبر 1968، وتستشهد بكل من أوراق سولومونوف وكولموغوروف.
وفي هذا السياق، عندما Kolmogorov أصبح على بينة من Solomonoff العمل، اعترف Solomonoff ذات الأولوية. لعدة سنوات، Solomonoff عمل المعروف في الاتحاد السوفياتي في العالم الغربي. التوافق العام في الآراء في المجتمع العلمي، ومع ذلك، تم ربط هذا النوع من التعقيد مع Kolmogorov ، يهتم العشوائية من سلسلة، في حين حسابي احتمال أصبحت مرتبطة مع Solomonoff ، الذي ركز على التنبؤ باستخدام اختراعه العالمية قبل توزيع الاحتمالات. المجال الأوسع نطاقا تشمل descriptional التعقيد احتمال وغالبا ما تسمى Kolmogorov التعقيد. في عالم الكمبيوتر مينغ لي ترى هذا مثال على تأثير ماثيو: «...إلى كل من لديه أكثر سوف تعطى...»
وفي هذا السياق، نظرية المعلومات الخوارزمية هي مجال علوم الكمبيوتر التي تدرس تعقيد كولموغروف وغيرها من التدابير المعقدة على سلاسل (أو هياكل البيانات الأخرى).
كذلك، هناك عدة أنواع أخرى من تعقيد كولموغروف أو المعلومات الخوارزمية. ويستند الأكثر استخداما على برامج تحديد الذات، ويرجع ذلك أساسا إلى ليونيد ليفين (1974).
علاوةً على ذلك، وقدم مارك بورغين نهجا بديهيا لتعقيد كولموغوروف استنادا إلى بديهيات بلوم (Blum 1967) في الورقة التي قدمها أندريه كولموغوروف للنشر.
من جهة ثانية، تقول النظرية أنه من بين الخوارزميات التي فك رموز السلاسل من أوصافها (الرموز)، هناك واحد مثالي. هذه الخوارزمية، لكافة السلاسل، تسمح برموز قصيرة كما يسمح بها أي خوارزمية أخرى حتى ثابت المضافة التي تعتمد على الخوارزميات، ولكن ليس على السلاسل نفسها. استعمل سولمونوف هذه الخوارزمية وأطوال التعليمات البرمجية التي تسمح بها لتعريف «الاحتمال العالمي» لسلسلة يمكن أن يستند عليها الاستدلال الاستقرائي للأرقام اللاحقة من السلسلة. استعمل كولموغوروف هذه النظرية لتعريف الكثير من وظائف السلاسل، بما في ذلك التعقيد والعشوائية والمعلومات.
في هذا الإطار، ويستند مفهوم ونظرية تعقيد كولموغوروف على نظرية حاسمة اكتشفت لأول مرة من قبل راي سولومونوف، الذي نشرها في سنة 1960، واصفا إياه في «تقرير أولي عن نظرية عامة للاستدلال الاستقرائي» كجزء من اختراعه للاحتمالية الخوارزية. وقدم وصفاً أكثر اكتمالاً في منشوراته الصادرة عام 1964 بعنوان «نظرية رسمية للاستدلال الاستقرائي» والجزء الأول والجزء الثاني في المعلومات والتحكم.
علاج أكثر رسمية
من جانب آخر، وهكذا، إذا P هو برنامج في L2 وهو وصف الحد الأدنى من s ثم InterpretLanguage(P) إرجاع سلسلة s. طول هذا الوصف s هو مجموع
إضافةً إلى ذلك، نظرية: إذا K1 وK2 هي وظائف التعقيد بالنسبة لاللغات وصف تورينج كاملة L1 و L2، ثم هناك c ثابت - الذي يعتمد فقط على اللغات L1 و L2 المختارة - مثل أن
- طول برنامج InterpretLanguage، والتي يمكننا أن نتخذها لتكون c ثابت.
- طول P الذي هو بحكم التعريف K2 (s).
- وهذا يثبت الحد العلوي المطلوب.
- ∀s. −c ≤ K1(s) − K2(s) ≤ c.
- دليل: عن طريق التماثل، يكفي أن يثبت أن هناك بعض c ثابت مثل أن لجميع السلاسل s
- K1(s) ≤ K2(s) + c.
- الآن، لنفترض أن هناك برنامج في اللغة L1 الذي يعمل كمترجم لL2:
- وظيفة InterpretLanguage(سلسلة p)
- حيث p هو برنامج في L2 . يتميز المترجم بالخاصية التالية:
- تشغيل InterpretLanguage على إدخال p إرجاع نتيجة تشغيل p.
الإصدارات الشرطية
ومن جهة أخرى، تعقيد Kolmogorov المشروط لسلسلتين يُعرَّف ، بشكل تقريبي ، بأنه تعقيد Kolmogorov لـ x معطى y كمدخل مساعد للإجراء.
- انظر كذلك
- ضغط بيانات
- مشهد توضيحي
- ملاحظات
عشوائية كولموغوروف
إضافةً إلى ذلك، يمكن توسيع هذا التعريف لتعريف مفهوم العشوائية للتسلسلات اللانهائية من الأبجدية المحدودة. يمكن تعريف هذه التسلسلات العشوائية خوارزميًا بثلاث طرق مكافئة. طريقة واحدة تستعمل التناظرية الفعالة لنظرية القياس؛ آخر يستعمل مارتينجاليس فعالة. الطريقة الثالثة تحدد التسلسل اللانهائي ليكون عشوائيًا إذا كان تعقيد كولموغروف الخالي من البادئات ينمو بسرعة كافية - يجب أن يكون هناك ثابت c بحيث يكون تعقيد الجزء الأولي من الطول n دائمًا على الأقل n - c . هذا التعريف ، على عكس تعريف العشوائية لسلسلة محدودة ، لا يتأثر بالآلة العامة المستعملة لتحديد تعقيد Kolmogorov الخالي من البادئات.
علاوةً على ذلك، تُعرِّف عشوائية Kolmogorov السلسلة (عادةً من البتات) على أنها عشوائية إذا وفقط إذا كان أي برنامج كمبيوتر يمكنه إنتاج هذه السلسلة بطول السلسلة نفسها على الأقل. لجعل هذا دقيقًا ، يجب تحديد جهاز كمبيوتر عالمي (أو آلة Turing العامة)، بحيث يعني «البرنامج» برنامجًا لهذه الآلة الشاملة. السلسلة العشوائية بهذا المعنى تكون «غير قابلة للضغط» من حيث أنه من المستحيل «ضغط» السلسلة في برنامج أقصر من السلسلة نفسها. يتم استخدام وسيطة العد لإظهار أنه بالنسبة لأي كمبيوتر عام ، هناك سلسلة عشوائية خوارزمية واحدة على الأقل لكل طول. ومع ذلك ، يعتمد ما إذا كانت أي سلسلة معينة عشوائية على الكمبيوتر العالمي المحدد الذي تم اختياره. هذا لأن الكمبيوتر العالمي يمكن أن يحتوي على سلسلة معينة مشفرة في حد ذاته ، ويمكن للبرنامج الذي يعمل على هذا الكمبيوتر العالمي أن يشير ببساطة إلى هذه السلسلة المشفرة باستخدام سلسلة قصيرة من البتات (أي أقصر بكثير من السلسلة نفسها).
نظرية : هناك ثابت c مثل هذا
∀s. K(s) ≤ |s| + c.
الحد الأدنى لطول الرسالة
في هذا الإطار، تم تطوير مبدأ الحد الأدنى لطول الرسالة للاستدلال الإحصائي والاستقرائي والتعلم الآلي بواسطة CS Wallace و DM Boulton في سنة 1968. MML هي نظرية بايزي (أي أنها تتضمن معتقدات سابقة) ونظرية معلومات. لها الخصائص المرغوبة للثوابت الإحصائية (أي أن الاستدلال يتحول مع إعادة تحديد المعلمات، مثل من الإحداثيات القطبية إلى الإحداثيات الديكارتية)، والاتساق الإحصائي (مثلًا ، حتى بالنسبة للمشاكل الصعبة للغاية ، سوف تتقارب MML مع أي نموذج أساسي) والكفاءة (أي أن نموذج MML سوف يتقارب مع أي نموذج أساسي حقيقي بأسرع ما يمكن). أظهر CS Wallace و DL Dowe (1999) علاقة رسمية بين MML ونظرية المعلومات الخوارزمية (أو تعقيد Kolmogorov).
عدم قابلية الحوسبة لتعقيد كولموغوروف
بالنسبة إلى i = 1 إلى ما لا نهاية:
وظيفة تعقيد كولموغروف (سلسلة)
محاولة ساذجة في برنامج لحساب K.
ومن جهة أخرى، للوهلة الأولى قد يبدو تافها لكتابة البرنامج الذي يمكن حساب K (s) لأي s ، مثل ما يلي:
لا يزال هناك على الأقل
كذلك، سلاسل بت بطول n لا يمكن ضغطها بواسطة c . لتحديد الاحتمال، قسّم على 2 n .
2 ن - 2 ن - ج +1 + 1
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7
وفي هذا الصدد، تحتوي السلسلة الأولى على وصف قصير باللغة الإنجليزية، وهو «كتابة ab 16 مرة»، والذي يتكون من 17 حرفًا، الثاني ليس لديه وصف بسيط واضح (باستخدام نفس مجموعة الأحرف) بخلاف كتابة السلسلة نفسها، أي «كتابة 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7» الذي يحتوي على 38 حرفا وبالتالي يمكن القول إن عملية كتابة السلسلة الأولى تحتوي على «تعقيد أقل» من كتابة السلسلة الثانية.
في هذا الإطار، يمكن تعريف تعقيد كولموغروف لأي كائن رياضي، ولكن من أجل البساطة يقتصر نطاق هذه المقالة على سلاسل. يجب علينا أولاً تحديد لغة وصف للسلاسل. يمكن أن تستند لغة الوصف هذه إلى أي لغة برمجة حاسوبية، مثل Lisp أو Pascal أو Java. إذا كان P هو برنامج الذي يخرج سلسلة x، ف هو وصف x. طول الوصف هو فقط طول P كسلسلة أحرف، مضروباً في عدد البتات في حرف (مثلًا، 7 لـ ASCII).
وعلى صعيد آخر، بشكل رسمي أكثر، تعقيد سلسلة هو طول وصف أقصر ممكن من السلسلة في بعض لغة وصف عالمي ثابت (حساسية التعقيد نسبة إلى اختيار لغة الوصف هو مناقشتها أدناه). يمكن إظهار أن تعقيد كولموغروف أي سلسلة لا يمكن أن يكون أكثر من عدد قليل من بايت أكبر من طول السلسلة نفسها. سلاسل مثل المثال abab أعلاه، الذي كولموغوروف التعقيد صغيرة بالنسبة لحجم السلسلة، لا تعتبر معقدة.
وعلى صعيد آخر، أي سلسلة s له وصف واحد على الأقل. مثلًا، السلسلة الثانية أعلاه هو الإخراج بواسطة البرنامج:
وفي هذا السياق، يمكننا، بدلا من ذلك، اختيار ترميز لآلات تورينج، حيث ترميز هو وظيفة الذي يربط مع كل آلة تورينج M . إذا كان M هو آلة تورينج التي، على المدخلات ث، إخراج سلسلة x، ثم سلسلة متسلسلة w هو وصف x. وللتحلي بالتحليل النظري، فإن هذا النهج أكثر ملاءمة لبناء براهين رسمية مفصلة ويفضل عموما في الأدبيات البحثية. في هذه المقالة، يتم مناقشة نهج غير رسمي.
تعريف
ومن ناحية أخرى، ضع في اعتبارك السلاسل التالية المكونة من 32 حرفًا ورقمًا صغيرًا:
abababababababababababababababab ،
العودة i
من جهة ثانية، الذي يأخذ كإدخال سلسلة s وإرجاع K(s). جميع البرامج هي من طول محدود لذلك، من أجل إثبات البساطة، يفترض أن يكون 7000000000 بت. الآن، والنظر في البرنامج التالي من طول 1288 بت:
وفي السياق ذاته، برهان: وإلا فإن كل من سلاسل محدودة ممكن لا نهائي يمكن أن يتم إنشاؤها بواسطة برامج كثيرة محدودة مع تعقيد أقل من ن بت.
دليل رسمي على عدم قابلية الحوسبة لـ K.
من جهة ثانية، يستعمل الدليل غير المباشر التالي لغة بسيطة تشبه باسكال للدلالة على البرامج؛ من أجل إثبات البساطة تفترض وصفها (أي مترجم) أن يكون طول 1400000 بت. افترض للتناقض هناك برنامج
وفي هذا السياق، النظرية : هناك وجود سلاسل من تعقيد كولموغوروف كبيرة بشكل تعسفي. شكليا: لكل n ∈ N، هناك سلسلة s مع K (s) ≥ n.
من جهة ثانية، ولكن هذا لن يعمل لأن بعض البرامج p اختبارها لن تنتهي، مثلًا إذا كانت تحتوي على حلقات لا نهائية. لا توجد طريقة لتجنب كل هذه البرامج عن طريق اختبارها بطريقة ما قبل تنفيذها بسبب عدم قابلية مشكلة التوقف.
وفي هذا السياق، النظرية : K ليست دالة قابلة للحوسبة. بمعنى آخر، لا يوجد أي برنامج الذي يأخذ أي سلسلة s كإدخال وتنتج K (ق) الصحيح كخرج.
وظيفة تعقيد كولموغروف (سلسلة)
ومن جهة أخرى، هذا البرنامج يتير من خلال جميع البرامج الممكنة (من خلال التكرار من خلال جميع السلاسل الممكنة والنظر فقط تلك التي هي برامج صالحة)، بدءا من أقصر. يتم تنفيذ كل برنامج للعثور على النتيجة التي تنتجها هذا البرنامج، ومقارنتها مع مدخلات. إذا كانت النتيجة مطابقة يتم إرجاع طول البرنامج.
ومن جهة أخرى، ما هو أكثر من ذلك، لا يمكن لأي برنامج على الإطلاق حساب الدالة K، على الإطلاق حتى متطورة. وقد ثبت ذلك في ما يلي.
العلاقة بالانتروبيا
من جهة ثانية، بالنسبة للأنظمة الديناميكية ، يرتبط معدل الانتروبيا والتعقيد الحسابي للمسارات بنظرية Brudno ، وهي أن المساواة يحمل للجميع على وجه التقريب .
من جهة ثانية، ويمكن أن تظهر التي لإخراج مصادر المعلومات ماركوف ، ويرتبط كولموجوروف التعقيد إلى الكون من مصدر المعلومات. بتعبير أدق ، فإن تعقيد Kolmogorov لإخراج مصدر معلومات Markov ، الذي تم تطبيعه بطول الناتج ، يتقارب بشكل شبه مؤكد (حيث يذهب طول المخرجات إلى اللانهاية) إلى إنتروبيا المصدر.
إرجاع "ab" × 16
نظرية الثبات
وفي السياق ذاته، يعتمد طول أقصر وصف على اختيار لغة الوصف؛ ولكن تأثير تغيير اللغات محدد (نتيجة تسمى نظرية الثوابت).
في هذا الإطار، إذا كان وصف d(s) من سلسلة s من الحد الأدنى من الطول (أي، باستخدام أقل بتات)، يطلق عليه وصف الحد الأدنى من s، وطول d(s) (أي عدد البتات في وصف الحد الأدنى) هو تعقيد كولموغروف من s، K (s) مكتوبة). رمزيا
عودة 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 هي تورينج ما يعادل.
نظرية عدم اكتمال شيتين
الدالة NthProofProvesComplexityFormula (int n)
يمكن إثباتها داخل S.
من جانب آخر، إذا كانت NthProofProvesComplexityFormula (i) و ComplexityLowerBoundNthProof (i) ≥ n
GenerateProvablyComplexString (ن 0)
علاوةً على ذلك، حسب النظرية أعلاه ، فإن أغلب السلاسل معقدة بمعنى أنه لا يمكن وصفها بأي طريقة «مضغوطة» بشكل ملحوظ. ومع ذلك، فقد تبين أن حقيقة أن سلسلة معينة معقدة لا يمكن إثباتها رسميًا، إذا كان تعقيد السلسلة أعلى من عتبة معينة. الشكل الدقيق هو على النحو التالي. أولاً، إصلاح نظام بديهي خاص S للأعداد الطبيعية. يجب أن يكون النظام البديهي قويًا بدرجة كافية بحيث يمكن ربط صيغة F A في S. لبعض التأكيدات A حول تعقيد السلاسل. يجب أن يكون لهذا الاقتران الخاصية التالية:
وظيفة NthProof (int n)
K(s) ≥ L (كما هو رسمي in S)
حدد n 0 = f −1 (U) +1.
من جانب آخر، ثم لا يمكن الحصول على دليل على النموذج " K (s) ≥ L " مع L ≥ n 0 في S ، كما يمكن رؤيته من خلال وسيطة غير مباشرة: إذا كان ComplexityLowerBoundNthProof(i) إرجاع قيمة ≥ n 0 ، فإن الحلقة داخل GenerateProvablyComplexString سينتهي في النهاية، وهذا الإجراء سيعيد سلسلة نصية مثل
وعلى صعيد آخر، الدليل : تم تصميم الدليل على هذه النتيجة على أساس بناء مرجعي ذاتي مستعمل في مفارقة بيري .
وفي هذا السياق، إذا كانت F A يمكن إثباتها من بديهيات S ، فيجب أن يكون التأكيد المقابل A صحيحًا. يمكن تحقيق هذا «الشكل الرسمي» بناءً على ترقيم Gödel .
ومن جهة أخرى، بالنظر إلى n ، يحاول هذا الإجراء كل دليل حتى يعثر على سلسلة ودليل في النظام الرسمي S للصيغة K (s) ≥ L لبعض L ≥ ن ؛ إذا لم يوجد مثل هذا الدليل، فإنه يدور إلى الأبد.
علاوةً على ذلك، حيث سيتم تحديد الثابت n 0 لاحقًا. يمكن التعبير عن الطول الإجمالي للبرنامج كـ U + log 2 (n 0)، حيث U عبارة عن ثابت معين ويمثل السجل 2 (n 0) طول قيمة العدد الصحيح n 0 ، بحسب الافتراض المعقول بأنه مشفر بأرقام ثنائية . الآن ضع في اعتبارك الوظيفة f : [2، ∞) → [1، ∞)، المحددة بواسطة f (x) = x − log 2 (x). إنها تتزايد بشكل صارم في مجالها، وبالتالي لها معكوس f −1 : [1، ∞) → [2، ∞).
من جانب آخر، النظرية : يوجد ثابت L (الذي يعتمد فقط على S وعلى اختيار لغة الوصف) بحيث لا توجد سلسلة نصية يكون البيان من أجلها
في هذا الإطار، يمكننا إيجاد تعداد فعال لجميع البراهين الرسمية في S من خلال بعض الإجراءات
علاوةً على ذلك، الذي يأخذ كمدخلات n ويخرج بعض الإثبات. هذه الوظيفة تعدد كل البراهين. بعض هذه أدلة على الصيغ التي لا نهتم بها هنا، حيث يتم إنتاج كل دليل محتمل في لغة S لبعض n . بعض هذه صيغ التعقيد على شكل ك (ق) ≥ n حيث s و n ثوابت في لغة S. هناك إجراء
وفي السياق ذاته، التي تحدد ما إذا كان الدليل رقم n يثبت بالفعل صيغة التعقيد K (s) ≥ إل . السلاسل s ، والعدد الصحيح L بدورهما، قابلان للحساب عن طريق الإجراء:
- الوظيفة StringNthProof (int n)
- تعقيد الوظيفة LowBoundNth Proof (int n)
- دالة GenerateProvablyComplexString (int n)
- بالنسبة إلى i = 1 إلى ما لا نهاية:
وفي هذا السياق، أخيرًا، ضع في اعتبارك البرنامج الذي يتكون من كل تعريفات الإجراءات هذه، والدعوة الرئيسية:
إرجاع StringNthProof (i)
النتائج الأساسية
وعلى صعيد آخر، ليس من الصعب أن نرى أن وصف الحد الأدنى من سلسلة لا يمكن أن يكون أكبر بكثير من السلسلة نفسها — برنامج GenerateString2 أعلاه أن المخرجات s هو مبلغ ثابت أكبر من s.
في المناقشة التالية، اسمحوا K (s) يكون تعقيد سلسلةs .
العلاج غير الرسمي
وفي هذا الصدد، طول P هو ثابت لا يعتمد على D. لذلك، هناك على الأكثر الحمل ثابت بغض النظر عن الكائن الموصوفة. لذلك، اللغة المثلى هي عالمية حتى هذا ثابت المضافة.
وفي هذا الصدد، هناك بعض اللغات الوصف التي هي الأمثل، في المعنى التالي: نظرا لأي وصف لكائن في لغة وصف، ووصف وقال يمكن استخدامها في لغة وصف الأمثل مع النفقات العامة ثابتة. يعتمد الثابت فقط على اللغات المتضمنة، وليس على وصف الكائن، ولا على الكائن الذي يتم وصفه.
من جانب آخر، من الناحية التقنية أكثر، فإن الجزء الأول من الوصف هو برنامج كمبيوتر، والجزء الثاني هو المدخل إلى هذا البرنامج الحاسوبي الذي ينتج الكائن كخرج.
- هنا مثال على لغة وصف الأمثل. سيكون للوصف جزأين:
- يصف الجزء الأول لغة وصف أخرى.
- الجزء الثاني هو وصف للكائن بهذه اللغة.
ومن جهة أخرى، تتبع نظرية الثبات مايلي: نظرا لأي وصف اللغة L، لغة وصف الأمثل على الأقل كفاءة L، مع بعض النفقات العامة المستمرة.
من جانب آخر، دليل: يمكن تحويل أي وصف D في L إلى وصف في اللغة المثلى عن طريق وصف أولاً L كـ P برنامج كمبيوتر (جزء 1)، ثم ثم استخدام الوصف الأصلي D كمدخلات إلى هذا البرنامج (الجزء 2). طول هذا الوصف الجديد D′ هو (على وجه التقريب):
الوظيفة GenerateString2
- إرجاع "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"
- بينما السلسلة الأولى هي الإخراج بواسطة (أقصر بكثير) الزائفة رمز:
- الوظيفة GenerateString1
هذا تناقض، QED
يتم استخدام أفكار مماثلة لإثبات خصائص ثابت Chaitin .
وعلى صعيد آخر، نتيجة لذلك، يجب أن يستمر البرنامج أعلاه، مع القيمة المختارة لـ n 0 ، في حلقة إلى الأبد.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟