إذاً ها هنا بعض الخفايا أو النقاط المخادعة التي سيجب علينا أن نتمعنها
بخصوص فكرة العشوائية و عدم قابلية الانضغاط هذه.
إذاً، لدينا هنا الفكرة الأولى والتي هي ليست مسألة جدية كثيراً.
وهي أنّنا نحتاج أن نختار طريقة قياسية ما لتمثيل هذا الانضغاط.
إذاً دعونا نقول أنّ المهمّة التي
أعطيناها لنفسنا هي ضغط سلسلة معينة، سلسلة رموز،
وسوف نقوم بكتابة برنامج حاسوبي ليقوم بهذا
ونريد أن نكتب أقصر برنامج حاسوبي ممكن.
إذاً، أحب البرمجة بلغة البرمجة Python
إذاً، ربما أجرب أن أكتب برنامج بلغة البرمجة Python
وشخصٌ آخر ربما يكتب برنامج بلغة C
وشخصٌ آخر ربما يكتبه بلغة C++
وشخصٌ آخر ربما يكتبها بلغة Lisp
ومن يعرف ماذا سيفعله أشخاصٌ آخرون.
لكن سنكون جميعنا نعمل بلغات مختلفة،
والخوارزمية سيكون لديها تمثيلات مختلفة بلغات البرمجة المختلفة هذه.
إذاً إننا نحتاج أن نتفق على مقياس أو مرجع نوعاً ما، أداة
أو لغة نستطيع أن نستخدمها عندما نقارن هذه الخوارزميات.
وإذاً الشيء القياسي المقام هنا
بهذا التطور الرسمي نوعاً ما لهذه الأفكار،
هو إستخام شيئاً ما يدعى آلة تورينغ (turing)الكلية.
إذاً آلة تورينغ الكلية هي
جهاز يستطيع أن يقوم بأي شيء
يستطيع أن ينفذ أي حساب نوعاً ما،
عند أي زمن منفصل، حساب الضاء المتقطع ،
أو حساب حالة منفصلة، أعذروني.
وهو قادر على محاكاة أي حاسوب آخر
أو جهاز يستطيع أن يقوم بذلك الحساب.
إذاً نوعاً ما جهاز يشمل على جميع الحسابات
وهو جهاز مرجعي قياسي،
نموذج للحساب الذي هو فعّال كأي شيء آخر.
إذاً في التطور الرسمي لهذه الأفكار والتي ليست جزء من هذه الدورة،
أحدها تعمل في الهيكل حيث تقارن الأشياء
في شروط آلات تورينغ المختلفة.
إذاً هذه أحد الخفايا التي يجب أن نعالجها.
و حسناً، لقد عالجنا هذا.
سوف نستخدم آلات تورينغ الكلية.
الشيء الخفي الثاني هو أكثر حذقاً،
وأكثر جدّية.
وهو أنّه كيف نعرف إذا وجدنا
الخوارزمية الأقصر التي تستطيع أن تنتج
تستطيع أن تنتج تسلسل.
ربما تسلسل قابل للإنضغاط جداً
لكني لم أكن قادراً على إكتشافه بعد.
أو أنني لست ذكياً كفاية،
أو لم أعطي نفسي وقتاً كافياً.
مثل ذلك قد تكون المسألة لـ pi،
التي بدت عشوائية بدون شك.
وبالمناسبة، بمنظور ما، ببعض النواحي المنظور إليه
pi عشوائي حقاً.
وكل الأرقام (تحت العشرة)، إن قمت بنشر ثنائي ..
ستبدو مثل قرعة العملة.
كل التسلسلات المحتملة من الأصفار والواحدات تحدث عادةً بالتساوي مع النشر الثنائي لـ pi.
إذاً هذا غريب.
إذاً بحس معين ، pi عشوائي.
لكن بحس هذه الخوارزمية،
أو إن كنت تستخدم آلات تورينغ الكلية،
هذا النوع من الخوارزمية يبدو منطقياً.
pi ليس عشوائي، لأن هناك خوارزمية قصيرة تنتجه.
حسناً، إذاً، ربما كل تسلسل محتمل
لديه فعلاً خوارزمية قصيرة من المستحيل تقريباً اكتشافها
والتي تستطيع إنتاجه،
حيث أننا لم نكن أذكياء كفاية لنكتشفها بعد.
إذاً لقد تبيّن أننا نستطيع أن نزيل هذه الإمكانية.
إذاً دعوني أقدّم هذه المناقشة كالتالي.
إذاً كنا نتساءل إن كان بإمكاننا إكتشاف خوارزميات ضغط،
طرق لضغط التسلسلات التي يبدو من الغير واضح كيف يمكنك أن تكون قادراً على ضغطهم.
إذاً فكرة واحدة هي
حسناً، ربما يمكننا أن نأتي بخوارزمية تحدد الخوارزمية الأقصر.
خوارزمية للضغط والتي هي أمثل بكل وقت.
إذاً هذه ستكون خوارزمية تكتب خوارزمية.
أو إنّها كبرنامج يكتب برنامج.
بالإضافة، هذا البرنامج سيكتب آلياً أفضل برنامج
بمعنى إنّه كان أقصر برنامج.
والذي سيضغط تسلسلنا الرمزي قدر الإمكان.
إذاً، هذا سيكون شيئئاً مذهلاً، لكن
أحدٌ ما يستطيع أن يظهر أنّ برنامجاً كهذا لا يوجد.
لا يمكنك كتابة برنامج يكتب أقصر برنامج بشكل آلي .
إذاً، تلك الفكرة، لذلك لا نستطيع
لا نستطيع أن نحدد بشكل آلي نوعاً ما
إن كان هناك خوارزمية أقصر
لكن ربما، يوجد خوارزمية هناك،
حتى لو لم نجدها.
ولقد تبيّن أنّنا نستطيع أن نزيل هذه الإمكانية أيضاً.
وهنا كيف يمكن لأحدٍ ما أن يبرهن ذلك.
إذاً أولاً دعونا نفكر بالمجموعة، كل الخوارزميات المحتملة.
كل المخططات المحتملة لضغط تسلسل من الأصفار والواحدات.
إذاً هذه ستكون مجموعة لا نهائية.
يوجد عدد لا نهائي من الخوارزميات المحتملة
ويمكننا أن ندع برنامجنا يصبح طويلاً بشكل لا نهائي.
إذاً يوجد لدينا هنا هذه المجموعة اللانهائية، هذه المجموعة من كل هذه الخوارزميات .
وربما نفكر أيضاً بتجميع كل التسلسلات المحتملة التي نريد ضغطها.
هذه أيضاً مجموعة لانهائية.
إنّنا نفكر بتسلسلات لا نهائية هنا،
كل تسلسلات الأصفار والواحدات اللانهائية المحتملة.
هذا كثير.
ومن الواضح أنّ هذا لا نهائي أيضاً.
إذاً لدينا هاتين المجموعتين اللانهائيتين:
كل الخوارزميات،
وكل التسلسلات.
وإن كانت هاتين المجموعتين بنفس الحجم،
إذن ربما تكون كل خوارزمية،
إعذروني، كل تسلسل
لديه خوارزمية تتماشى معه.
إذاً ربما لا يمكننا إيجاد أي خوارزمية تتماشى مع أي تسلسل،
لكن، نعرف أنّ تلك الخوارزمية ربما تكون هناك.
ومع ذلك، ليست المسألة أنّه يوجد نفس العدد من الخوارزميات
كما يوجد من التسلسلات.
في الواقع، هناك تسلسلات كثيرة بشكل لا نهائي أكثر من الخوارزميات.
إذن، يوجد
يوجد بالتأكيد بعض التسلسلات والذي لا يوجد خوارزمية ممكن أن تضغطهم.
وسندعو هذه التسلسلات عشوائية.
إذاً العشوائية توجد في هذا النقاش.
علاوةً على ذلك، يوجد الكثير
من االتسلسلات أكثر مما يوجد خوارزميات،
هذا إن اخترت تسلسل،
لا أريد أن أقول عشوائي.
إذا اختر تسلسل اعتباطي،
فقط أغمس يدي في حقيبة التسلسلات اللانهائية هذه،
أنا متأكد تقريباً بمعنى أنّ باحتمال واحد
أنّ التسلسل سيكون عشوائي.
وسيكون غير قابل للانضغاط.
إذاً الفكرة التقنية
ربما، بعضكم مألوف مع هذا،
أنّ مجموعة كل الخوارزميات هي قابلة للعد بشكل لا نهائي .
ومجموعة كل تسلسلات الواحدات والأصفار اللانهائية
غير قابلة للعد.
إذاً إنّهم مجموعات لا نهائية صعبة جداً.
إذاً مجدداً، إذا اخترت تسلسل رموز في حالة عشوائية،
تسلسل رموز اعتباطي،
أستطيع أن أكون متأكد من احتمال واحد
أنّ،
ذلك التسلسل هو عشوائي.
حسناً، الآن دعونا نعود للمعادلة اللوجيستية، أخيراً
نعود للأنظمة الديناميكية.
إذاً إذا اخترت شرط إبتدائي،
شرط إبتدائي عشوائي،
شرط إبتدائي اعتباطي،
للمعادلة اللوجيستية،
هذا سوف ينتج تسلسل من الأصفار والواحدات.
وأعرف، لقد رأينا سابقاً، أو كما جادلت سابقاً،
أنّ المعادلة اللوجيستية تستطيع أن تنتج كل تسلسل ممكن من الواحدات والأصفار،
وكل المتتاليات،
وإنهم يحدثون باحتمال متساوٍ.
إذاً إذا اخترت،
شرط إبتدائي
شرط إبتدائي اعتباطي للمعادلة اللوجيستية، مع R = 4،
أستطيع أن أكون شبه متأكد أنّ النتيجة ستكون عشوائية.
إذاً، من هذا المنظور،
هذه طريقة للتفكير بالعشوائية،
العملية التي تنتج الرموز هي حتمية بالتأكيد.
إنّها قاعدة حتمية غير متغيرة
لكن النتيجة عشوائية.
حيث أنّ احتمال واحد أنا متأكد كلياً
أنّه لا يوجد خوارزمية تستطيع
تستطيع أن تضغظ التسلسل الذي تنتجه المعادلة اللوجيستية.
إذاً المعادلة اللوجيستية تنتج العشوائية.
أو هل حقاّ تفعل؟
انتظر دقيقة.
المعادلة اللوجيستية نفسها هي خوارزمية تنتج هذا التسلسل.
إذاً كيف يمكنني أن أقول أنّ المعادلة اللوجيستية تنتج نتيجة عشوائية
لأنّه يوجد
نتيجة عشوائية
لأنّه لا يوجد خوارزمية لـ،
لضغط ذلك التسلسل.
أليست المعادلة اللوجيستية، تكرر المعادلة اللوجيستية نفسها،
تماماً كما الخوارزمية؟
إذاً، هذا اعتراض جيد
لكن، يجب أن نفكر بحذر بالمعادلة اللوجيستية في الشواش،
وبالاعتماد الحساس الخاص على الشروط الإبتدائية.
إذاً إفترض أنّ أعطيتني
تسلسل عشوائي.
لا يوجد نمط واضح له،
وتقول، حسناً،
مهمّتي هي أن أكتشف إن كانت هناك طريقة
لإستخدام المعادلة اللوجيستية لإنتاج هذا التسلسل من الواحدات والأصفار.
وفي البداية سأقول،
بالتأكيد، طبعاً يجب أن يكون.
المعادلة اللوجيستية تنتج كل تسلسلات الواحدات والأصفار الممكنة .
إذاً هذا التسلسل التي أعطيتني إياه للتو،
لا مشكلة، أستطيع أن أكتشفه.
أو حتى إن لم أستطع أن أكتشفه،
ربما إنّه، يوجد الكثير من الأشياء المختلفة لتجربتها،
شرط إبتدائي لتجربته.
أعرف أنّ الإجابة موجودة،
ومن ثمّ سوف يكون هناك خوارزمية قصيرة.
إذاً لقد ضغطت للتو التسلسل الذي ظننته لا ينضغط.
لكن انتظر دقيقة.
المفتاح هو أنّه، لكي تنتج تسلسل الرموز المعين ذلك،
أحتاج أن أحدد الشرط الإبتدائي بدقة.
إذاً بدقة تامة، أحتاج أن أحدد الشرط الإبتدائي.
إذاً يجب أن ، في خوارزميتي،
حيث التقنية فيها بسيطة جداً نوعاً ما.
أكرر المعادلة اللوجيستية مع R = 4.0
هذا برنامج بسيط جداً.
العديد منكم لقد قام بكتابة نسخته الخاصة من هذه البرامج.
برنامج الجدولة يمكنه القيام بها ، أيضاً.
لكن عندئذٍ، لكي تجعل نتيجةً معينة
النتيجة التي أعطيتني إياها،
إذاً أستطيع أن أقول لقد ضغطتها،
أحتاج أيضاً الشرط الإبتدائي.
وتقريباً كل الشروط الإبتدائية
سوف تكون أعداد غير منطقية.
أعداد تستمر للأبد.
ولذلك، لكي تعمل هذه الخوارزمية،
لتنتج تسلسل الرموز هذا،
أحتاج أن أحدد الشرط الإبتدائي،
أحتاج أن أحدد الشرط الإبتدائي بدقة.
ولقد تبيّن، بنقاش مشابه
أنّ كل الأعداد تقريباً بين 0 و 1
عشوائيين بحد ذاتهم.
إنّه تسلسل عشوائي لـ،
المنازل العشرية بعد الفاصلة عشرية.
ولذلك أحتاج أن أعرف ذلك العدد بدقة،
ذلك الشرط الإبتدائي بدقة،
لعدد لا نهائي من النقاط العشرية،
والغالبية العظمى لكل المجموعات ماعدا المجموعة بقياس صفر
مع احتمال واحد
الشروط الإبتدائية لا تنضفط.
إذاً، لقد وجدت نوعاً ما تقنية مختصرة لإنتاجه
لكن أحتاج، أن أتذكر تسلسل لا نهائي لا ينضغط من الأعداد العشرية
لكي أشغل هذه الخوارزمية
وأنتج التسلسل الثنائي المطلوب بدقة.
إذاً نعم، المعادلة اللوجيستية تنتج حقاً نتيجة عشوائية.
إذاً للتلحيص:
المعادلة اللوجيستية، نظام ديناميكي حتمي
تنتج نتيجة عشوائية.
تسلسل الأصفار والواحدات، الرموز من
الديناميكيا الرمزية للمعادلة اللوجيستية
لا ينضغط.
إنّه عشوا-- وهذا ما يعنيه أن تكون عشوائي.
إنّه لا ينضغط.
وربما تعتقد
أنّ المعادلة اللوجيستية نفسها
وصف مضغوط للتسلسل المُنتج للتو.
ومع ذلك، لكي تنتج ذلك التسلسل،
نحتاج أن نحدد الشرط الإبتدائي بدقة لا نهائية.
إذاً ذلك يتطلب تذكر عدد طويل بشكل لا نهائي.
إذاً، إنّه برنامج قصير،
لكنك تحتاج أن تعطيه عدد طويل بشكل لا نهائي
ذلك الشكل اللانهائي، هو وصف دقيق للشرط الإبتدائي،
إذاً المعادلة اللوجيستية ليست نسخة مضغوطة فعلاً من التسلسل الذي تنتجه.
إذاً آمل أنّ هذا كله لم يكن مربكاً.
لكن لكي أكون صادقاً، آمل أنّه على الأقل مربكٌ قليلاً.
لكن، بطريقة جيدة،
حيث أعتقد ما تفعله هذه الأمثلة هو،
أنها تغني وتعقّد مفهومنا للعشوائية.
إذاً، نظام ديناميكي مشوش،
مثل معادلات لورنز، أو مثل المعالة اللوجيستية مع R = 4،
إنّه حتمي، لكنه غير متوقع بسبب تأثير الفراشة.
وإنّه حتمي، لكنّه في الواقع ينتج عشوائية
بهذا الحس الخوارزمي من العشوائية.
إذاً العشوائية لا يجب أن تكون نيجة صدفة.
العشوائية ممكن أن تكون نتيحة الحتمية.
وذلك، أعتقد أنه أحد الدروس الرئيسية لدراسة الشواش والأنظمة الديناميكية.
وسأتحدث المزيد قليلاً عن أنّه في التلخيص لهذه الوحدة،
وهذه موضوعات سنستمر بإعادة النظر إليها طوال الدورة.