hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
اسطوانة صوتية فائقة جودة الصوت
ومنذ دراسة Meyer-Moran في عام 2007،  تم نشر ما يقرب من 80 دراسة على صوت عالي الدقة، حيث تضمنت نصفها تقريبًا اختبارات عمياء. أجرى الدكتور جوشوا ريس، من جامعة كوين ماري بلندن، وعضو مجلس محافظي جمعية هندسة الصوت (AES)، تحليلًا تلويًا لعشرين من الاختبارات المنشورة التي تضمنت تفاصيل وبيانات تجريبية كافية. وفي بحث نُشر في عدد يوليو 2016 من مجلة AES ،  يقول الدكتور ريس إنه على الرغم من أن الاختبارات الفردية كانت لها نتائج مختلطة، وأن التأثير كان «صغيرًا ويصعب اكتشافه»، فإن النتيجة الإجمالية كانت يمكن للمستمعين المدربين التمييز بين التسجيلات عالية الدقة ومكافئات الأقراص المضغوطة الخاصة بهم في ظل ظروف عمياء: «بشكل عام، وكانت هناك قدرة صغيرة ولكنها ذات دلالة إحصائية للتمييز بين جودة الصوت القياسية (44.1 أو 48 كيلو هرتز، 16 بت) والصوت عالي الدقة (يتجاوز المعيار جودة). عندما تم تدريب المشاركين، كانت القدرة على التمييز أكثر أهمية».
تم العثور على نتائج متناقضة عند مقارنة تنسيقات 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 دولار أمريكي. كان يزن أكثر من 26 كيلوغرام (57 رطل) وتشغيل الاسطوانة الصوتية الفائقة ثنائية القناة وأقراص الكتاب الأحمر المضغوطة فقط. قام مصنعو الإلكترونيات، بما في ذلك 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.
بروتوكول بصمة اليد
بروتوكول الاصبع في علم شبكات الكمبيوتر، يعد بروتوكول من بروتوكولات شبكية بسيطة لتبادل المعلومات الموجهة للمستخدم ومعرفة حالته.
بروتوكول بصمة اليد بروتوكول الاسم / الاصبع
يعتمد بروتوكول الاسم / الاصبع على مستند طلب التعليقات RFC 742 (ديسمبر 1977) كوسيط لبرامج name و finger التي تقدم تقارير عن حالة جهاز كمبيوتر أو شخص معين في مواقع الشبكة. تمت كتابة برنامج الاصبع في عام 1971 بواسطة ليه ايرنست الذي أنشأ البرنامج لتلبية رغبة المستخدمين الذين هم بحاجة معلومات عن مستخدمين آخرين على الشبكة. كانت المعلومات المتعلقة بمن قام بتسجيل الدخول مفيدة للتحقق من توفر شخص ما للقاء. غالبا كان هذا هو أقدم نوع من أشكال معلومات التواجد لمستخدمي الشبكة عن بعد.
قبل تواجد برنامج الاصبع، كانت الطريقة الوحيدة للحصول على هذه المعلومات هي عبر برنامج who الذي بمقدورة عرض المعرفات وأرقام الخطوط الطرفية (الرقم الداخلي لخط الاتصال بالخادم، والذي تم من خلاله توصيل الجهاز الطرفي من قبل المستخدم) للمستخدمين الذين سجلوا دخولهم. قام العالم ليه ايرنست بتسمية برنامجه بعد فكرة أن الناس سوف يحركون أصابعهم أسفل قائمة who للعثور على ما كانوا يبحثون عنه.
بروتوكول بصمة اليد بروتوكول الاسم / الاصبع
كان مصطلح «الإصبع»، في سبعينيات القرن الماضي، له دلالة على «واش»: هذا ما يجعل من «الإصبع» تذكيرًا جيدًا ومساعد للذاكرة
للدلالات الدلالية لأمر finger UNIX (عميل في سياق البروتوكول).
بروتوكول بصمة اليد بروتوكول اصبع معلومات المستخدم
يعمل برنامج اصبع الـ عفريت على منفذ TCP 79. سينشئ العميل (في حالة المستضيفين عن طريق التحكم عن بعد) اتصالاً بالمنفذ رقم 79. يتم بدء برنامج RUIP (برنامج معلومات المستخدم عن بعد) على الطرف الآخر من الاتصال لمعالجة الطلب. يرسل مركز الاستضافة المحلي استعلام RUIP يتكون من سطر واحد بناءً على مواصفات استعلام الاصبع، وينتظر استجابة RUIP. يتلقى RUIP الاستعلام ويعالج، ويعيد إجابة، ثم يبدأ بإغلاق الاتصال. يتلقى المضيف المحلي إشارة الإجابة والإغلاق، ثم يواصل لإغلاق الاتصال من طرفه.
يعتمد بروتوكول اصبع معلومات المستخدم على RFC 1288 (بروتوكول إصبع معلومات المستخدم ، ديسمبر 1991). عادة ما يكون طرف الخادم من البروتوكول يتم تنفيذه باستخدام برنامج fingerd أو in.fingerd (لاصبع الـ عفريت)، في حين أن من طرف العميل يتم تنفيذ هذا الجانب من قبل برامج name و finger التي من المفترض أن تعود بتقرير عن الحالة بشكل موجه للبشر ويسهل استخدامه على أي نظام في وقتها الحالي أو حتى الشخص المستخدم لها. لا يستوجب صيغة محددة، ويتكون البروتوكول غالباً بتحديد سطر أوامر واحد.
بروتوكول بصمة اليد بروتوكول اصبع معلومات المستخدم
يمكن للبرنامج توفير معلومات مثل ما إذا كان المستخدم مسجلاً الدخول حاليًا أو عنوان بريده الإلكتروني أو اسمه الكامل وما إلى ذلك. إضافة إلى معلومات المستخدم القياسية، يعرض الاصبع محتويات ملفات .project و .plan في الدليل الرئيسي للمستخدم. غالبًا ما يحتوي هذا الملف (الذي يحتفظ به المستخدم) إما على معلومات مفيدة حول أنشطة المستخدم الحالية، مثل التدوين المصغر، أو بدلاً من ذلك كل أنواع الدعابة.
بروتوكول بصمة اليد مخاوف أمنية
كان سابقاً تقديم مثل هذه المعلومات التفصيلية مثل عناوين البريد الإلكتروني والأسماء الكاملة يعتبر امر مقبولاً وملائماً في بدايات عصر الشكبة العنكبوتية، ولكن فيما بعد كان موضع شك لأسباب تتعلق بالخصوصية والأمان.
استخدم المتسللون المعلومات الصادرة من الإصبع كطريقة لشن هجوم سيبراني يعرف بـ الهندسة الاجتماعية على نظام كمبيوتر الأمن الخاص بالشركة.[بحاجة لمصدر] باستخدام أحد الإصابع الخاصة للعملاء فقط للحصول على قائمة بأسماء موظفي الشركة وعناوين البريد الإلكتروني وأرقام الهواتف وما إلى ذلك. يمكن للمتسلل الاتصال أو إرسال بريد إلكتروني إلى شخص ما في الشركة ويطلب ان يزوده بالمعلومات أثناء التظاهر بأنه موظف آخر.
كما كان لاصبع الـ عفريت العديد [بحاجة لمصدر] من التصدعات والثغرات الأمنية القابلة للاستغلال واختراق الأنظمة. على سبيل المثال، في عام 1988 استغلت دودة موريس نقطة ضعف تسمى بـ الفيضان في برنامج fingerd (بجانب نقاط ضعف أخرى) لنشرها.[بحاجة لمصدر]
لهذه الأسباب وبحلول أواخر تسعينيات القرن الماضي لم تعد الغالبية العظمى من المواقع على الإنترنت تقدم هذه الخدمة.[بحاجة لمصدر]
بروتوكول بصمة اليد دعم التطبيق
يتم تنفيذه على نظام يونكس ونظام شبيه يونكس والإصدارات الحالية من مايكروسوفت ويندوز (باستخدام الأمر 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 ، بياتشينزا.
سانتا مارينيلا
سانتا مارينيلا، هي (محافظة) في مدينة روما الحضرية في منطقة لاتسيو الإيطالية، وتقع على بعد حوالي 60 كيلومتر (37 ميل) شمال غرب روما. وهي تشمل منتجع Santa Severa الشاطئي (Pyrgi القديمة) وقلعة من القرون الوسطى.
سانتا مارينيلا تاريخ
في العصور القديمة كانت سانتا مارينيلا موقعًا لمنتجع الاستحمام الروماني.
سانتا مارينيلا ثقافه
وامتلكوا الممثلة إنجريد بيرجمان والمخرج روبرتو روسيليني فيلا هناك. وفرقة الغجر البانك Gogol Bordello لديها أيضا أغنية بعنوان «سانتا مارينيلا» عن الوقت الذي أمضاه يوجين هاتز في سانتا مارينيلا بينما كان يحاول الحصول على الهجرة إلى أمريكا.
تشتهر المحافظة بـ «عجلات الهجرة» - وهي وجبة خفيفة تشبه البسكويت اكلها المهاجرون اليهود الروس الذين استقروا هناك مؤقتًا في أواخر الثمانينيات في طريقهم إلى الولايات المتحدة أو إسرائيل.
الاتصالات في توغو
الاتصالات السلكية واللاسلكية في توغو تشملالإذاعة والتلفزيون والهواتف الثابتة والمتنقلة والإنترنت.
الاتصالات في توغو الإذاعة والتلفزيون
محطات الراديو : هي شبكة راديو مملوكة للدولة مع محطات متعددة ؛ وعشرات المحطات الإذاعية الخاصة وقليلاً من محطات الإذاعة المجتمعية ؛ وتتاح عمليات البث لعدة محطات إذاعية دولية (2007).
محطات التلفزيون : تمتلك الدولة محطتي تلفاز مع مواقع بث عديدة؛ وايضا خمس محطات تلفزيونية خاصة تبث محليًا ؛ كما تتوفر خدمة تلفزيون الكابل (2007).
انتشرت وسائل الإعلام الخاصة في توغو، وتعمل مع عشرات الإذاعات التجارية والمجتمعية وقليلاً من محطات التلفزيون الخاصة والإذاعة هي الوسيلة الأكثر شعبية لا سيما في المناطق الريفية وتعتبر محطة تلفزيون توغولاس المملوك للحكومة المحطة الرئيسية
وتتوفر جميع الخدمات الإذاعية من BBC World Service و Gabon Africa رقم 1 و Radio France Internationale (RFI) .
الاتصالات في توغو هاتف
نظام الهاتف: هو نظام عادل يعتمد على شبكة من موجات راديو دقيقة متتابعة تكملها خطوط الأسلاك المفتوحة والنظام الخلوي حيث تجمع الكثافة الهاتفية للخطوط الثابتة والمتنقلة حوالي 50 هاتفًا لكل 100 شخص يستخدام الهاتف الخلوي المتنقل الرائج(2010).
المحطات الأرضية الساتلية : 1 Intelsat ( المحيط الأطلسي ) و 1 Symphonie (القمر الصناعي) (2010).
كابلات الاتصالات : تشمل نظام كابلات غرب إفريقيا وهو عبارة عن كبل بحري يربط بين البلدان الواقعة على طول الساحل الغربي لأفريقيا والبرتغال والمملكة المتحدة ؛  و كبل GLO-1 الذي يربط بين البلدان الواقعة على طول الساحل الغربي لأفريقيا ومنها إلى البرتغال وإسبانيا والمملكة المتحدة .
الاتصالات في توغو إنترنت
النطاق العريض الثابت : 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 <M>. إذا كان M هو آلة تورينج التي، على المدخلات ث، إخراج سلسلة x، ثم سلسلة متسلسلة <M>w هو وصف x. وللتحلي بالتحليل النظري، فإن هذا النهج أكثر ملاءمة لبناء براهين رسمية مفصلة ويفضل عموما في الأدبيات البحثية. في هذه المقالة، يتم مناقشة نهج غير رسمي.
أي سلسلة s له وصف واحد على الأقل. على سبيل المثال، السلسلة الثانية أعلاه هو الإخراج بواسطة البرنامج:
بينما السلسلة الأولى هي الإخراج بواسطة (أقصر بكثير) الزائفة رمز:
إذا كان وصف 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:
حيث p هو برنامج في L2 . يتميز المترجم بالخاصية التالية:
تشغيل InterpretLanguage على إدخال p إرجاع نتيجة تشغيل p.
وهكذا، إذا 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.
للوهلة الأولى قد يبدو تافها لكتابة البرنامج الذي يمكن حساب K (s) لأي s ، مثل ما يلي:
هذا البرنامج يتير من خلال جميع البرامج الممكنة (من خلال التكرار من خلال جميع السلاسل الممكنة والنظر فقط تلك التي هي برامج صالحة)، بدءا من أقصر. يتم تنفيذ كل برنامج للعثور على النتيجة التي تنتجها هذا البرنامج، ومقارنتها مع مدخلات. إذا كانت النتيجة مطابقة يتم إرجاع طول البرنامج.
ولكن هذا لن يعمل لأن بعض البرامج p اختبارها لن تنتهي، على سبيل المثال إذا كانت تحتوي على حلقات لا نهائية. لا توجد طريقة لتجنب كل هذه البرامج عن طريق اختبارها بطريقة ما قبل تنفيذها بسبب عدم قابلية مشكلة التوقف.
ما هو أكثر من ذلك، لا يمكن لأي برنامج على الإطلاق حساب الدالة K، على الإطلاق حتى متطورة. وقد ثبت ذلك في ما يلي.
تعقيد كولموغروف النتائج الأساسية
النظرية : هناك وجود سلاسل من تعقيد كولموغوروف كبيرة بشكل تعسفي. شكليا: لكل n ∈ N، هناك سلسلة s مع K (s) ≥ n.
برهان: وإلا فإن كل من سلاسل محدودة ممكن لا نهائي يمكن أن يتم إنشاؤها بواسطة برامج كثيرة محدودة مع تعقيد أقل من ن بت.
النظرية : K ليست دالة قابلة للحوسبة. بمعنى آخر، لا يوجد أي برنامج الذي يأخذ أي سلسلة s كإدخال وتنتج K (ق) الصحيح كخرج.
يستخدم الدليل غير المباشر التالي لغة بسيطة تشبه باسكال للدلالة على البرامج؛ من أجل إثبات البساطة تفترض وصفها (أي مترجم) أن يكون طول 1400000 بت. افترض للتناقض هناك برنامج
الذي يأخذ كإدخال سلسلة s وإرجاع K(s). جميع البرامج هي من طول محدود لذلك، من أجل إثبات البساطة، يفترض أن يكون 7000000000 بت. الآن، والنظر في البرنامج التالي من طول 1288 بت:
تعقيد كولموغروف النتائج الأساسية
باستخدام تعقيد كولموغروف (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 +… + 2 n - c = 2 n - c +1 - 1.
سلاسل بت بطول n لا يمكن ضغطها بواسطة c . لتحديد الاحتمال، قسّم على 2 n .
تعقيد كولموغروف نظرية عدم اكتمال شيتين
حسب النظرية أعلاه (§ Compression)، فإن معظم السلاسل معقدة بمعنى أنه لا يمكن وصفها بأي طريقة «مضغوطة» بشكل ملحوظ. ومع ذلك، فقد تبين أن حقيقة أن سلسلة معينة معقدة لا يمكن إثباتها رسميًا، إذا كان تعقيد السلسلة أعلى من عتبة معينة. الشكل الدقيق هو على النحو التالي. أولاً، إصلاح نظام بديهي خاص S للأعداد الطبيعية. يجب أن يكون النظام البديهي قويًا بدرجة كافية بحيث يمكن ربط صيغة F A في S. لبعض التأكيدات A حول تعقيد السلاسل. يجب أن يكون لهذا الاقتران الخاصية التالية:
إذا كانت F A يمكن إثباتها من بديهيات S ، فيجب أن يكون التأكيد المقابل A صحيحًا. يمكن تحقيق هذا «الشكل الرسمي» بناءً على ترقيم Gödel .
النظرية : يوجد ثابت L (الذي يعتمد فقط على S وعلى اختيار لغة الوصف) بحيث لا توجد سلسلة نصية يكون البيان من أجلها
الدليل : تم تصميم الدليل على هذه النتيجة على أساس بناء مرجعي ذاتي مستخدم في مفارقة بيري .
تعقيد كولموغروف نظرية عدم اكتمال شيتين
يمكننا إيجاد تعداد فعال لجميع البراهين الرسمية في S من خلال بعض الإجراءات
الذي يأخذ كمدخلات n ويخرج بعض الإثبات. هذه الوظيفة تعدد كل البراهين. بعض هذه أدلة على الصيغ التي لا نهتم بها هنا، حيث يتم إنتاج كل دليل محتمل في لغة S لبعض n . بعض هذه صيغ التعقيد على شكل ك (ق) ≥ n حيث s و n ثوابت في لغة S. هناك إجراء
التي تحدد ما إذا كان الدليل رقم n يثبت بالفعل صيغة التعقيد K (s) ≥ إل . السلاسل s ، والعدد الصحيح L بدورهما، قابلان للحساب عن طريق الإجراء:
بالنظر إلى 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، ∞).
ثم لا يمكن الحصول على دليل على النموذج " K (s) ≥ L " مع L ≥ n 0 في S ، كما يمكن رؤيته من خلال وسيطة غير مباشرة: إذا كان ComplexityLowerBoundNthProof(i) إرجاع قيمة ≥ n 0 ، فإن الحلقة داخل GenerateProvablyComplexString سينتهي في النهاية، وهذا الإجراء سيعيد سلسلة نصية مثل
نتيجة لذلك، يجب أن يستمر البرنامج أعلاه، مع القيمة المختارة لـ n 0 ، في حلقة إلى الأبد.
يتم استخدام أفكار مماثلة لإثبات خصائص ثابت Chaitin .