CALM/arwiki huggingface dataset:
ومنذ دراسة Meyer-Moran في عام 2007 ، تم نشر ما يقرب من 80 دراسة على صوت عالي الدقة، حيث تضمنت نصفها تقريبًا اختبارات عمياء. أجرى الدكتور جوشوا ريس، من جامعة كوين ماري بلندن ، وعضو مجلس محافظي جمعية هندسة الصوت (AES) ، تحليلًا تلويًا لعشرين من الاختبارات المنشورة التي تضمنت تفاصيل وبيانات تجريبية كافية. وفي بحث نُشر في عدد يوليو 2016 من مجلة AES ، يقول الدكتور ريس إنه على الرغم من أن الاختبارات الفردية كانت لها نتائج مختلطة، وأن التأثير كان "صغيرًا ويصعب اكتشافه" ، فإن النتيجة الإجمالية كانت يمكن للمستمعين المدربين التمييز بين التسجيلات عالية الدقة ومكافئات الأقراص المضغوطة الخاصة بهم في ظل ظروف عمياء: "بشكل عام، وكانت هناك قدرة صغيرة ولكنها ذات دلالة إحصائية للتمييز بين جودة الصوت القياسية (44.1 أو 48 كيلو هرتز، 16 بت) والصوت عالي الدقة (يتجاوز المعيار جودة). عندما تم تدريب المشاركين، كانت القدرة على التمييز أكثر أهمية " .
مقارنة مع DVD-A.
تم العثور على نتائج متناقضة عند مقارنة تنسيقات DSD وتنسيقات PCM عالية الدقة. واختبارات الاستماع مزدوجة التعمية في عام 2004 بين DSD و 24 بت، 176.4 ذكرت تسجيلات kHz PCM أنه لا يمكن سماع أي اختلافات كبيرة بين الأشخاص الخاضعين للاختبار. يواصل دعاة DSD ومصنعي المعدات التأكيد على تحسين جودة الصوت أعلى من PCM 24 بت 176.4 كيلو هرتز. وجدت دراسة أجريت عام 2003 أنه على الرغم من استجابات الترددات الموسعة لكلا الصيغتين، ولم يتمكن الأشخاص من التمييز بين الصوت والمعلومات فوق 21 كيلوهرتز من الصوت بدون مثل هذا المحتوى عالي التردد. في دراسة عام 2014 ، ومع ذلك، Marui et al. وجد أنه في ظل ظروف التعمية المزدوجة، كان المستمعون قادرين على التمييز بين تنسيقات تسجيل PCM (192 كيلو هرتز / 24 بت) و DSD (2.8 ميجا هرتز) أو DSD (5.6 ميجا هرتز) ، مفضلين الميزات النوعية لـ DSD ، لكن لم يتمكنوا من التمييز بين اثنين من تنسيقات DSD .
أجهزة التشغيل.
لقد تم تقديم مشغل Sony SCD-1 بالتزامن مع تنسيق الاسطوانة الصوتية الفائقة في عام 1999 ، بسعر حوالي 5000 دولار أمريكي. كان يزن أكثر من وتشغيل الاسطوانة الصوتية الفائقة ثنائية القناة وأقراص الكتاب الأحمر المضغوطة فقط. قام مصنعو الإلكترونيات، بما في ذلك Onkyo ، Denon ، Marantz ، Pioneer و Yamaha بعرض أو عرض مشغلات الاسطوانة الصوتية الفائقة. وصنعت سوني مشغلات الاسطوانة الصوتية الفائقة داخل السيارة .
وكان أول جيلين من وحدة تحكم ألعاب PlayStation 3 من سوني قادرين على قراءة أقراص الاسطوانة الصوتية الفائقة.و بدءًا من الجيل الثالث (تم تقديمه في أكتوبر 2007) ، تمت إزالة تشغيل SACD. ومع ذلك، ستعمل جميع طرز PlayStation 3 على تنسيق قرص DSD. وكان PlayStation 3 قادرًا على تحويل DSD متعدد القنوات إلى ضياع 1.5 Mbit / s DTS للتشغيل عبر S / PDIF باستخدام برنامج النظام 2.00. أزال التنقيح اللاحق الميزة.
وقدمت العديد من العلامات التجارية (في الغالب عالية الجودة ) مشغلات Blu-ray Disc و Ultra HD Blu-ray التي يمكنها تشغيل أقراص SACD .
ويمكن التشغيل غير الرسمي لصور قرص الاسطوانة الصوتية الفائقة على جهاز كمبيوتر من خلال مشغل الصوت المجاني foobar2000 لنظام التشغيل Windows باستخدام ملحق إضافي مفتوح المصدر يسمى SACDDecoder. ويدعم برنامج موسيقى Mac OS X Audirvana أيضًا تشغيل صور قرص SACD.
بروتوكول الاصبع في علم شبكات الكمبيوتر ، يعد بروتوكول من بروتوكولات شبكية بسيطة لتبادل المعلومات الموجهة للمستخدم ومعرفة حالته.
بروتوكول الاسم / الاصبع.
يعتمد بروتوكول الاسم / الاصبع على مستند طلب التعليقات (ديسمبر 1977) كوسيط لبرامج codice_1 و codice_2 التي تقدم تقارير عن حالة جهاز كمبيوتر أو شخص معين في مواقع الشبكة. تمت كتابة برنامج الاصبع في عام 1971 بواسطة ليه ايرنست الذي أنشأ البرنامج لتلبية رغبة المستخدمين الذين هم بحاجة معلومات عن مستخدمين آخرين على الشبكة. كانت المعلومات المتعلقة بمن قام بتسجيل الدخول مفيدة للتحقق من توفر شخص ما للقاء. غالبا كان هذا هو أقدم نوع من أشكال معلومات التواجد لمستخدمي الشبكة عن بعد.
قبل تواجد برنامج الاصبع، كانت الطريقة الوحيدة للحصول على هذه المعلومات هي عبر برنامج codice_3 الذي بمقدورة عرض المعرفات وأرقام الخطوط الطرفية (الرقم الداخلي لخط الاتصال بالخادم، والذي تم من خلاله توصيل الجهاز الطرفي من قبل المستخدم) للمستخدمين الذين سجلوا دخولهم. قام العالم ليه ايرنست بتسمية برنامجه بعد فكرة أن الناس سوف يحركون أصابعهم أسفل قائمة codice_3 للعثور على ما كانوا يبحثون عنه.
كان مصطلح "الإصبع" ، في سبعينيات القرن الماضي، له دلالة على "واش": هذا ما يجعل من "الإصبع" تذكيرًا جيدًا ومساعد للذاكرة
للدلالات الدلالية لأمر codice_2 UNIX "(عميل" في سياق البروتوكول).
بروتوكول اصبع معلومات المستخدم.
يعمل برنامج اصبع الـ عفريت على منفذ TCP 79. سينشئ العميل (في حالة المستضيفين عن طريق التحكم عن بعد) اتصالاً بالمنفذ رقم 79. يتم بدء برنامج RUIP (برنامج معلومات المستخدم عن بعد) على الطرف الاخر من الاتصال لمعالجة الطلب. يرسل مركز الاستضافة المحلي استعلام RUIP يتكون من سطر واحد بناءً على مواصفات استعلام الاصبع، وينتظر استجابة RUIP. يتلقى RUIP الاستعلام ويعالج، ويعيد إجابة، ثم يبدأ بإغلاق الاتصال. يتلقى المضيف المحلي إشارة الإجابة والإغلاق، ثم يواصل لإغلاق الاتصال من طرفه.
يعتمد بروتوكول اصبع معلومات المستخدم على ( "بروتوكول إصبع معلومات المستخدم" ، ديسمبر 1991). عادة ما يكون طرف الخادم من البروتوكول يتم تنفيذه باستخدام برنامج codice_6 أو codice_7 "(لاصبع الـ عفريت" )، في حين أن من طرف العميل يتم تنفيذ هذا الجانب من قبل برامج codice_1 و codice_2 التي من المفترض أن تعود بتقرير عن الحالة بشكل موجه للبشر ويسهل استخدامه على أي نظام في وقتها الحالي أو حتى الشخص المستخدم لها. لا يستوجب صيغة محددة، ويتكون البروتوكول غالباً بتحديد سطر أوامر واحد.
يمكن للبرنامج توفير معلومات مثل ما إذا كان المستخدم مسجلاً الدخول حاليًا أو عنوان بريده الإلكتروني أو اسمه الكامل وما إلى ذلك. إضافة إلى معلومات المستخدم القياسية، يعرض الاصبع محتويات ملفات codice_10 و codice_11 في الدليل الرئيسي للمستخدم . غالبًا ما يحتوي هذا الملف (الذي يحتفظ به المستخدم) إما على معلومات مفيدة حول أنشطة المستخدم الحالية، مثل التدوين المصغر ، أو بدلاً من ذلك كل أنواع الدعابة .
كان سابقاً تقديم مثل هذه المعلومات التفصيلية مثل عناوين البريد الإلكتروني والأسماء الكاملة يعتبر امر مقبولاً وملائماً في بدايات عصر الشكبة العنكبوتية ، ولكن فيما بعد كان موضع شك لأسباب تتعلق بالخصوصية والأمان.
استخدم المتسللون المعلومات الصادرة من الإصبع كطريقة لشن هجوم سيبراني يعرف بـ الهندسة الاجتماعية على نظام كمبيوتر الأمن الخاص بالشركة. باستخدام أحد الإصابع الخاصة للعملاء فقط للحصول على قائمة بأسماء موظفي الشركة وعناوين البريد الإلكتروني وأرقام الهواتف وما إلى ذلك. يمكن للمتسلل الاتصال أو إرسال بريد إلكتروني إلى شخص ما في الشركة ويطلب ان يزوده بالمعلومات أثناء التظاهر بأنه موظف آخر.
كما كان لاصبع الـ عفريت العديد من التصدعات والثغرات الأمنية القابلة للاستغلال واختراق الأنظمة. على سبيل المثال، في عام 1988 استغلت دودة موريس نقطة ضعف تسمى بـ الفيضان في برنامج codice_6 (بجانب نقاط ضعف أخرى) لنشرها.
لهذه الأسباب وبحلول أواخر تسعينيات القرن الماضي لم تعد الغالبية العظمى من المواقع على الإنترنت تقدم هذه الخدمة.
دعم التطبيق.
يتم تنفيذه على نظام يونكس ونظام شبيه يونكس والإصدارات الحالية من مايكروسوفت ويندوز (باستخدام الأمر finger.exe). برامج أخرى لديها دعم لبرنامج الإصبع:
ترونتانو هي (بلدية) في مقاطعة فيربانو-كوسيو-أوسولا في منطقة بيدمونت الإيطالية، وتقع على بعد 120 كم (75 ميل) شمال شرق تورينو وحوالي 25 كم (16 ميل) شمال غرب فيربانيا.
في 31 ديسمبر 2004، كان عدد سكانها 1,684 وتبلغ مساحتها 58.0 كيلومتر مربع (22.4 sq mi).
يحد ترونتانو البلديات التالية: بيورا - كارديزا، كوسوجنو، دومودوسولا، دروغنو، ماليسكو، ماسيرا، بريموسيلو - تشيوفندا، سانتا ماريا ماجيور.
سان روكو آل بورتو ( لوديجيانو ، بياسينتينو : سان روتش ) هي "كومونا" (محافظة) في مقاطعة لودي في منطقة لومباردي الإيطالية ، وتقع على بعد حوالي 50 كيلومتر ( 31ميل) جنوب شرق ميلانو وحوالي 25 كيلومتر (16 ميل) جنوب شرق لودي . ومن 31 ديسمبر 2004 ، كان عدد سكانها 3383 نسمة ومساحتها 30.7 كيلومتر مربع ( 11.9 ميل مربع). سان روكو آل بورتو على الحدود مع المحافظات التالية: Fombio ، سانتو ستيفانو لوديجيانو ، كالينداسكو ، Guardamiglio ، بياتشينزا.
سانتا مارينيلا، هي (محافظة) في مدينة روما الحضرية في منطقة لاتسيو الإيطالية، وتقع على بعد حوالي شمال غرب روما. وهي تشمل منتجع Santa Severa الشاطئي ( Pyrgi القديمة) وقلعة من القرون الوسطى.
في العصور القديمة كانت سانتا مارينيلا موقعًا لمنتجع الاستحمام الروماني.
ثقافه.
وامتلكوا الممثلة إنجريد بيرجمان والمخرج روبرتو روسيليني فيلا هناك. وفرقة الغجر البانك Gogol Bordello لديها أيضا أغنية بعنوان "سانتا مارينيلا" عن الوقت الذي أمضاه يوجين هاتز في سانتا مارينيلا بينما كان يحاول الحصول على الهجرة إلى أمريكا.
تشتهر المحافظة بـ "عجلات الهجرة" - وهي وجبة خفيفة تشبه البسكويت اكلها المهاجرون اليهود الروس الذين استقروا هناك مؤقتًا في أواخر الثمانينيات في طريقهم إلى الولايات المتحدة أو إسرائيل.
الاتصالات السلكية واللاسلكية في توغو تشملالإذاعة والتلفزيون والهواتف الثابتة والمتنقلة والإنترنت.
محطات الراديو : هي شبكة راديو مملوكة للدولة مع محطات متعددة ؛ وعشرات المحطات الإذاعية الخاصة وقليلاً من محطات الإذاعة المجتمعية ؛ وتتاح عمليات البث لعدة محطات إذاعية دولية (2007).
محطات التلفزيون : تمتلك الدولة محطتي تلفاز مع مواقع بث عديدة؛ وايضا خمس محطات تلفزيونية خاصة تبث محليًا ؛ كما تتوفر خدمة تلفزيون الكابل (2007).
انتشرت وسائل الإعلام الخاصة في توغو، وتعمل مع عشرات الإذاعات التجارية والمجتمعية وقليلاً من محطات التلفزيون الخاصة والإذاعة هي الوسيلة الأكثر شعبية لا سيما في المناطق الريفية وتعتبر محطة تلفزيون توغولاس المملوك للحكومة المحطة الرئيسية
وتتوفر جميع الخدمات الإذاعية من BBC World Service و Gabon Africa رقم 1 و Radio France Internationale (RFI) .
رمز الاتصال : +228
بادئة المكالمة الدولية : 00
الخطوط الرئيسية:
الهواتف الخلوية المتنقلة:
نظام الهاتف: هو نظام عادل يعتمد على شبكة من موجات راديو دقيقة متتابعة تكملها خطوط الأسلاك المفتوحة والنظام الخلوي حيث تجمع الكثافة الهاتفية للخطوط الثابتة والمتنقلة حوالي 50 هاتفًا لكل 100 شخص يستخدام الهاتف الخلوي المتنقل الرائج(2010).
المحطات الأرضية الساتلية : 1 Intelsat ( المحيط الأطلسي ) و 1 Symphonie (القمر الصناعي) (2010).
كابلات الاتصالات : تشمل نظام كابلات غرب إفريقيا وهو عبارة عن كبل بحري يربط بين البلدان الواقعة على طول الساحل الغربي لأفريقيا والبرتغال والمملكة المتحدة ؛ و كبل GLO-1 الذي يربط بين البلدان الواقعة على طول الساحل الغربي لأفريقيا ومنها إلى البرتغال وإسبانيا والمملكة المتحدة .
نطاق المستوى الأعلى : .tg
مستخدمو الإنترنت :
النطاق العريض الثابت : 5,560 اشتراكًا، يحتل المرتبة 158 عالمياً ؛ بنسبة 0.1 ٪ من السكان، في مرتبة 170 عالمياً (2012).
النطاق العريض اللاسلكي : 47,892 مشتركًا، يحتل المرتبة 125 في العالم ؛ 0.7٪ من السكان، 135 في العالم (2012).
مضيفو الإنترنت :
IPv4 : خُصص 13.312 عنوانًا، أي أقل من 0.05٪ من الإجمالي العالمي، و 1.9 عنوانًا لكل 1000 شخص (2012).
الرقابة على الإنترنت والمراقبة.
لا توجد قيود حكومية معروفة على الوصول إلى الإنترنت أو تقارير تفيد بأن الحكومة تراقب البريد الإلكتروني أو غرف الدردشة عبر الإنترنت دون إشراف قضائي بالرغم من أن الدستور ينص على حرية التعبير والصحافة ، إلا أن الحكومة تقيد هذه الحقوق.
يحظر الدستور والقانون التدخل التعسفي في الخصوصية أو الأسرة أو المنزل أو المراسلات وتحترم الحكومة هذه المحظورات بشكل عام وفي القضايا الجنائية قد يأذن قاض أو مفوض الشرطة بتفتيش المساكن الخاصة ويعتقد المواطنين أن الحكومة تراقب الهواتف والمراسلات مع ان هذه المراقبة ليست مؤكدة.
تعقيد كولموغروف في نظرية المعلومات الخوارزمية (وهو حقل فرعي من علوم الكمبيوتر والرياضيات)، تعقيد كولموغروف كائن، مثل قطعة من النص، هو طول أقصر برنامج كمبيوتر (بلغة برمجة محددة سلفا) التي تنتج الكائن والإخراج.
هو مقياس للموارد الحسابية اللازمة لتحديد الكائن، ويعرف أيضاً بالتعقيد الخوازمي أو تعقيد سليمانوف -كولموغوروف -تشايتين، أو تعقيد حجم البرنامج، أو التعقيد الوصفي، أو التكعيب الخوارزمي. سميت على اسم أندريه كولموغوروف، الذي نشر لأول مرة حول هذا الموضوع في عام 1963.
ويمكن استخدام مفهوم تعقيد كولموغوروف في الدولة وإثبات نتائج الاستحالة أقرب إلى حجة كانتور القطرية، نظرية غوديل غير المكتملة، ومشكلة تورينج المتوقفة. على وجه الخصوص، لا يمكن لأي برنامج P حساب الحد الأدنى لتعقيد كولموغروف كل نص إرجاع قيمة أكبر أساسا من طول P الخاصة (انظر المقطع § Chaitin's نظرية عدم اكتمال); وبالتالي لا يمكن لأي برنامج واحد حساب تعقيد كولموغوروف الدقيق للعديد من النصوص بلا حدود.
ضع في اعتبارك السلاسل التالية المكونة من 32 حرفًا ورقمًا صغيرًا :
تحتوي السلسلة الأولى على وصف قصير باللغة الإنجليزية، وهو "كتابة ab 16 مرة" ، والذي يتكون من 17 حرفًا، الثاني ليس لديه وصف بسيط واضح (باستخدام نفس مجموعة الأحرف) بخلاف كتابة السلسلة نفسها، أي " كتابة 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7" الذي يحتوي على 38 حرفا وبالتالي يمكن القول إن عملية كتابة السلسلة الأولى تحتوي على "تعقيد أقل" من كتابة السلسلة الثانية.
بشكل رسمي أكثر، تعقيد سلسلة هو طول وصف أقصر ممكن من السلسلة في بعض لغة وصف عالمي ثابت (حساسية التعقيد نسبة إلى اختيار لغة الوصف هو مناقشتها أدناه). يمكن إظهار أن تعقيد كولموغروف أي سلسلة لا يمكن أن يكون أكثر من عدد قليل من بايت أكبر من طول السلسلة نفسها. سلاسل مثل المثال abab أعلاه، الذي كولموغوروف التعقيد صغيرة بالنسبة لحجم السلسلة، لا تعتبر معقدة.
يمكن تعريف تعقيد كولموغروف لأي كائن رياضي، ولكن من أجل البساطة يقتصر نطاق هذه المقالة على سلاسل. يجب علينا أولاً تحديد لغة وصف للسلاسل. يمكن أن تستند لغة الوصف هذه إلى أي لغة برمجة حاسوبية، مثل Lisp أو Pascal أو Java. إذا كان P هو برنامج الذي يخرج سلسلة x، ف هو وصف x. طول الوصف هو فقط طول P كسلسلة أحرف، مضروباً في عدد البتات في حرف (على سبيل المثال، 7 لـ ASCII).
يمكننا، بدلا من ذلك، اختيار ترميز لآلات تورينج، حيث ترميز هو وظيفة الذي يربط مع كل آلة تورينج M &lt;M&gt;. إذا كان M هو آلة تورينج التي، على المدخلات ث، إخراج سلسلة x، ثم سلسلة متسلسلة &lt;M&gt;w هو وصف x. وللتحلي بالتحليل النظري، فإن هذا النهج أكثر ملاءمة لبناء براهين رسمية مفصلة ويفضل عموما في الأدبيات البحثية. في هذه المقالة، يتم مناقشة نهج غير رسمي.
أي سلسلة s له وصف واحد على الأقل. على سبيل المثال، السلسلة الثانية أعلاه هو الإخراج بواسطة البرنامج:
الوظيفة GenerateString2 ()
إرجاع "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"
بينما السلسلة الأولى هي الإخراج بواسطة (أقصر بكثير) الزائفة رمز:
الوظيفة GenerateString1 ()
إرجاع "ab" × 16
إذا كان وصف d(s) من سلسلة s من الحد الأدنى من الطول (أي، باستخدام أقل بتات)، يطلق عليه وصف الحد الأدنى من s، وطول d(s) (أي عدد البتات في وصف الحد الأدنى) هو تعقيد كولموغروف من s، K (s) مكتوبة). رمزيا
يعتمد طول أقصر وصف على اختيار لغة الوصف؛ ولكن تأثير تغيير اللغات محدد (نتيجة تسمى نظرية الثوابت).
نظرية الثبات.
العلاج غير الرسمي.
هناك بعض اللغات الوصف التي هي الأمثل، في المعنى التالي: نظرا لأي وصف لكائن في لغة وصف، ووصف وقال يمكن استخدامها في لغة وصف الأمثل مع النفقات العامة ثابتة. يعتمد الثابت فقط على اللغات المتضمنة، وليس على وصف الكائن، ولا على الكائن الذي يتم وصفه.
هنا مثال على لغة وصف الأمثل. سيكون للوصف جزأين:
من الناحية التقنية أكثر، فإن الجزء الأول من الوصف هو برنامج كمبيوتر، والجزء الثاني هو المدخل إلى هذا البرنامج الحاسوبي الذي ينتج الكائن كخرج.
تتبع نظرية الثبات مايلي: نظرا لأي وصف اللغة L، لغة وصف الأمثل على الأقل كفاءة L، مع بعض النفقات العامة المستمرة.
دليل: يمكن تحويل أي وصف D في L إلى وصف في اللغة المثلى عن طريق وصف أولاً L كـ P برنامج كمبيوتر (جزء 1)، ثم ثم استخدام الوصف الأصلي D كمدخلات إلى هذا البرنامج (الجزء 2). طول هذا الوصف الجديد D′ هو (تقريبا):
طول P هو ثابت لا يعتمد على D. لذلك، هناك على الأكثر الحمل ثابت بغض النظر عن الكائن الموصوفة. لذلك، اللغة المثلى هي عالمية حتى هذا ثابت المضافة.
علاج أكثر رسمية.
نظرية: إذا K1 وK2 هي وظائف التعقيد بالنسبة لاللغات وصف تورينج كاملة L1 و L2، ثم هناك "c" ثابت - الذي يعتمد فقط على اللغات L1 و L2 المختارة - مثل أن
دليل: عن طريق التماثل، يكفي أن يثبت أن هناك بعض "c" ثابت مثل أن لجميع السلاسل "s"
الآن، لنفترض أن هناك برنامج في اللغة L1 الذي يعمل كمترجم لL2:
وظيفة InterpretLanguage(سلسلة "p")
حيث "p" هو برنامج في "L"2 . يتميز المترجم بالخاصية التالية:
وهكذا، إذا P هو برنامج في L2 وهو وصف الحد الأدنى من s ثم InterpretLanguage(P) إرجاع سلسلة s. طول هذا الوصف 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" مثل هذا
عدم قابلية الحوسبة لتعقيد كولموغوروف.
محاولة ساذجة في برنامج لحساب "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
إذا تعقيد كولموغروف (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 هي تورينج ما يعادل.
هناك نتيجة طبيعية، ودعا روح الدعابة "نظرية العمالة الكاملة" في مجتمع لغة البرمجة، مشيرا إلى أنه لا يوجد الكمال الحجم الأمثل المترجم.
حكم السلسلة لتعقيد كولموغوروف.
قاعدة سلسلة لتعقيد كولموغوروف تنص على أن
تنص على أن أقصر برنامج يعيد إنتاج "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" تُعطى بواسطة السلسلة الهندسية:
لا يزال هناك على الأقل
سلاسل بت بطول "n" لا يمكن "ضغطها بواسطة c" . لتحديد الاحتمال، قسّم على 2 "n" .
نظرية عدم اكتمال شيتين.
حسب النظرية أعلاه ( ) ، فإن معظم السلاسل معقدة بمعنى أنه لا يمكن وصفها بأي طريقة "مضغوطة" بشكل ملحوظ. ومع ذلك، فقد تبين أن حقيقة أن سلسلة معينة معقدة لا يمكن إثباتها رسميًا، إذا كان تعقيد السلسلة أعلى من عتبة معينة. الشكل الدقيق هو على النحو التالي. أولاً، إصلاح نظام بديهي خاص S للأعداد الطبيعية . يجب أن يكون النظام البديهي قويًا بدرجة كافية بحيث يمكن ربط صيغة F A في S. لبعض التأكيدات A حول تعقيد السلاسل. يجب أن يكون لهذا الاقتران الخاصية التالية:
إذا كانت F A يمكن إثباتها من بديهيات S ، فيجب أن يكون التأكيد المقابل A صحيحًا. يمكن تحقيق هذا "الشكل الرسمي" بناءً على ترقيم Gödel .
النظرية : يوجد ثابت "L" (الذي يعتمد فقط على 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" )
إذا كانت NthProofProvesComplexityFormula (i) و ComplexityLowerBoundNthProof (i) ≥ "n"
إرجاع StringNthProof ( "i" )
بالنظر إلى "n" ، يحاول هذا الإجراء كل دليل حتى يعثر على سلسلة ودليل في النظام الرسمي S للصيغة "K" ( "s" ) ≥ "L" لبعض "L" ≥ "ن" ؛ إذا لم يوجد مثل هذا الدليل، فإنه يدور إلى الأبد.
أخيرًا، ضع في اعتبارك البرنامج الذي يتكون من كل تعريفات الإجراءات هذه، والدعوة الرئيسية:
GenerateProvablyComplexString ( "ن" 0 )
حيث سيتم تحديد "الثابت 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، ∞).
حدد "n" 0 = "f" −1 ( "U" ) +1.
ثم لا يمكن الحصول على دليل على النموذج " "K" ( "s" ) ≥ "L" " مع "L" ≥ "n" 0 في S ، كما يمكن رؤيته من خلال وسيطة غير مباشرة : إذا كان codice_3 إرجاع قيمة ≥ "n" 0 ، فإن الحلقة داخل codice_4 سينتهي في النهاية، وهذا الإجراء سيعيد سلسلة "نصية" مثل
هذا تناقض، QED
نتيجة لذلك، يجب أن يستمر البرنامج أعلاه، مع القيمة المختارة لـ "n" 0 ، في حلقة إلى الأبد.
يتم استخدام أفكار مماثلة لإثبات خصائص ثابت Chaitin .
الحد الأدنى لطول الرسالة.