30000 دولار لحل مشاكل القاعدة 30 للبطاريات الآلية - مسابقة من ستيفن ولفرام

الترجمة الأصلية في مدونتي


موقع المسابقة

دعنا نوضح للقراء ما تعنيه "القاعدة 30" - إنها آلية أولية خلوية (انظر ويكي ) ، تم تعيين حالتها (قاعدة إنشاء مستوى جديد من الخلايا على أساس القديم) في نظام الأرقام الثنائية على أنها 0-0-0-1-1-1 -1-0 ، والتي يمكن تفسيرها على أنها 30 بتدوين عشري.

إذن من أين بدأ كل شيء؟ - "القاعدة 30"

كيف يمكن أن يكون شيء بسيط لا يصدق ينتج شيئًا معقدًا بشكل لا يصدق ؟ لقد مر ما يقرب من 40 عامًا منذ أن تعرفت للمرة الأولى على المادة 30 ، لكنها ما زالت تدهشني وتسعدني. لفترة طويلة ، أصبح اكتشافي الشخصي المفضل في تاريخ العلوم ، على مر السنين غيرت رؤيتي للعالم بأكملها وقادني إلى مجموعة متنوعة من أنواع جديدة من فهم العلوم والتكنولوجيا والفلسفة وأكثر من ذلك بكثير .

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

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

المادة 30 بسيطة للغاية:

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

قانون

RulePlot[CellularAutomaton[30]]

[شاهد الفيديو ، الذي يخبر في دقيقتين جوهر الأوتوماتة الخلوية والقاعدة 30 - ملاحظة المترجم]

ماذا يحدث إذا بدأت بخلية سوداء واحدة؟ [ يتم أخذ صف من الخلايا البيضاء ، بلا حدود على كلا الجانبين وخلية سوداء واحدة ، ثم تنطبق القواعد الموضحة أعلاه على هذا الصف ، ويتم الحصول على صف جديد ، وما إلى ذلك - ملاحظة المترجم ] افترض (كما فعلت أنا في البداية) أن القاعدة بسيطة للغاية ، ويجب أن يكون القالب الذي يتم الحصول عليه على أساس عمله بسيطًا جدًا. ومع ذلك ، إذا أجريت تجربة ، فسترى ما يحدث بعد الخطوات الخمسين الأولى من الخوارزمية:


وبطبيعة الحال ، يمكننا أن نفترض أنه نتيجة للخوارزمية ، سيتم الحصول على كائن رياضي أبسط بكثير. ومع ذلك ، إليك ما يحدث بعد الخطوات الـ 300 الأولى:



هذا يدل على أن هناك نمط معين - على الجانب الأيسر من الهرم . لكن في الوقت نفسه ، تبدو العديد من جوانب هذا القالب وكأنه شيء تم تكوينه بشكل عشوائي .

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

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

تدريجيا ، المزيد من الأدلة كان تراكم هذه المبادئ.

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

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

لقد حاولت بالفعل القيام بشيء مماثل في عام 2007 ، حيث وضعت جائزة للإجابة على السؤال الأساسي حول جهاز Turing معين. وفي هذه الحالة ، كانت النتيجة إيجابية ولم تستغرق وقتًا طويلاً للانتظار. بعد بضعة أشهر فقط ، تم الفوز بهذه الجائزة - بعد أن أثبتت إلى الأبد ما هي أبسط ماكينات تورينج العالمية الممكنة ، كما أثبتت بشكل مقنع للغاية المبدأ العام للتكافؤ الحسابي ، الذي طورته شخصيًا في وقت سابق.

تحدد مسابقة القاعدة 30 مرة أخرى هدف حل مهمة أساسية ، وهي: ما مدى تعقيد سلوك القاعدة 30 ؟ كل مهمة تطرح سؤالاً في هذا المجال بطريقتها الخاصة وعلى وجه التحديد. مثل القاعدة 30 نفسها ، فهي كلها مضللة في الإعداد الأصلي. ومع ذلك ، فإن حل أي منها سيكون إنجازًا كبيرًا ، والذي سيساعد في النهاية على إلقاء الضوء على المبادئ الأساسية لخصائص تكوين الكون الحاسوبي ، والتي تتجاوز بكثير تفاصيل القاعدة 30.

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

المادة 30 - المهام المطلوب حلها

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




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

المهمة 1: هل يبقى العمود المركزي دائمًا غير دوري؟

النظر في بداية العمود المركزي من المادة 30:




ليس من الصعب العثور على أن القيم في هذا العمود لا تتكرر - إنها ليست دورية. ولكن التحدي هو ، هل يصبح العمود المركزي دوريًا على الإطلاق؟ من خلال إطلاق القاعدة 30 ، نرى أن التسلسل لا يصبح دوريًا حتى في المراحل الأولى من البليون . ما يجب القيام به من أجل إنشاء وإثبات هذا بشكل مؤكد.

هنا هو الرابط حيث توجد أول مليون وأول مليار قيمة لهذا التسلسل ( مستودع بيانات Wolfram ).

المهمة 2: هل كل لون من خلايا (أسود أو أبيض) في المتوسط ​​من المرجح بنفس القدر في العمود الأوسط؟

هذا هو ما نحصل عليه عندما نحسب عدد الخلايا السوداء والبيضاء بالتتابع في خطوات أكثر في العمود المركزي لخوارزمية القاعدة 30:




النتائج قريبة بالتأكيد من تساوي الخلايا السوداء والبيضاء. هنا المشكلة (سؤال المشكلة) هي مسألة ما إذا كانت هذه العلاقة تتقارب مع 1 مع زيادة عدد الخطوات في الدورة .

المهمة 3: هل يتطلب حساب الخلية n للعمود المركزي عمليات O ( n ) على الأقل؟

للعثور على الخلية n في العمود الأوسط ، يمكنك دائمًا تشغيل القاعدة 30 لخطوات n ، بحساب قيم جميع الخلايا داخل الماس المحددة في الشكل أدناه:




ولكن إذا قمت بذلك مباشرة ، فستفعل ذلك n ² تحديثات خلية منفصلة ، وبالتالي ، فإن قوة الحوسبة المطلوبة تزيد مثل O ( n ² ). مسألة هذه المشكلة هي ما إذا كان هناك أكثر (أو أكثر) طريقة أسرع لحساب قيمة الخلية nth دون جميع العمليات الحسابية الوسيطة - أو ، على وجه الخصوص ، في أقل من O ( n ) العمليات .

الأرقام التي تشكل بي

القاعدة 30 هي نتاج لعالم الحوسبة: نظام قائم على دراسة البرامج البسيطة الممكنة ذات الهيكل الفكري الجديد ، والذي يوفره نموذج الحوسبة. ومع ذلك ، فإن المهام التي حددتها في مسابقة المادة 30 لها نظائرها في الرياضيات ، والتي كانت موجودة منذ قرون .

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




فقط لجعل التناظرية أقرب قليلاً ، إليك الأرقام القليلة الأولى من Pi في نظام الأرقام مع القاعدة 2:




وإليك البتات القليلة الأولى في العمود الأوسط من المادة 30:




للمتعة ، يمكنك تحويلها إلى رقم عشري:




بطبيعة الحال ، فإن الخوارزميات المعروفة لحساب أرقام Pi أكثر تعقيدًا من القاعدة البسيطة نسبيًا لتوليد الخلايا في العمود المركزي من المادة 30. لذا ، ماذا نعرف عن الأرقام في Pi؟

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

إذن ما نوع القياس الذي يمكن استخلاصه عند صياغة المشكلة 2؟ هل نعلم أنه في سلسلة من أرقام Pi ، تحدث أرقام مختلفة بنفس التردد؟ حتى الآن ، تم حساب أكثر من 100 تريليون رقم ثنائي - وترددات الأرقام المقاسة قريبة جدًا (في أول 40 تريليون رقم ثنائي من Pi ، تبلغ نسبة الوحدات إلى الأصفار 0.99999998064 تقريبًا). ولكن عند حساب الحد ، هل ستكون الترددات هي نفسها بالضبط؟ لطالما طرح العلماء هذا السؤال لعدة قرون ، لكن الرياضيات لم تتمكن حتى الآن من الإجابة عليه.

بالنسبة للأرقام المنطقية ، تكون تسلسلات الأرقام المكونة لها دورية ، ومن السهل تحديد الترددات النسبية لحدوث هذه الأرقام في رقم. ومع ذلك ، بالنسبة لتسلسل أرقام جميع الأرقام الأخرى "التي تم إنشاؤها بواسطة الطبيعة (التي تم إنشاؤها بشكل طبيعي)" ، في معظم الحالات ، لا يُعرف عمليا أي شيء عن ماهية ترددات الأرقام المدرجة في الرقم. سيكون من المنطقي أن نفترض أن أرقام Pi (وكذلك العمود المركزي من القاعدة 30) في الواقع " طبيعية " بمعنى أنه لا يقتصر فقط على كل رقم فردي ، بل وأي كتلة من أرقام ذات طول معين تقابل نفس التردد المحدد. وكما لوحظ في الأعمال المتعلقة بهذا الموضوع من ثلاثينيات القرن العشرين ، من الممكن تمامًا "إنشاء بنية رقمية (نموذج)" بالأرقام العادية. ثابت Champernone الذي تم الحصول عليه عن طريق الجمع بين أرقام الأعداد الصحيحة المتتالية هو مثال على التعليل أعلاه (يمكن الحصول على نفس الشيء على أساس أي عدد طبيعي من خلال الجمع بين قيم وظائف الأعداد الصحيحة المتتالية):




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

أخيرًا ، فكر في تناظر المشكلة 3 لـ Pi؟ على عكس القاعدة 30 ، حيث أن الطريقة الواضحة لحساب العناصر في التسلسل هي خطوة واحدة في كل مرة ، فإن الطرق التقليدية لحساب أرقام Pi تشمل الحصول على أفضل التقريب ل Pi كرقم دقيق. مع السلسلة القياسية ("الغريبة") التي اخترعها رامانوجان في عام 1910 والتي تم تحسينها من قبل الأخوين تشودنوفسكي في عام 1989 ، فإن الأعضاء القلائل الأوائل في هذه السلسلة يقدمون التقديرات التالية:




إذن كم عدد العمليات اللازمة للعثور على الرقم التاسع ؟ عدد المصطلحات المطلوبة في الصف هو O ( n ). ولكن يجب حساب كل شرط بدقة رقمية ، والتي تتطلب على الأقل O ( n ) عمليات حسابية منفصلة ، مما يعني ضمنا أن أعباء العمل الحسابية العامة ستكون أكبر من O ( n ).

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

النتائج والقياسات والحدس

المهمة 1: هل يبقى العمود المركزي دائمًا غير دوري؟

من بين الجوائز الثلاث في مسابقة القاعدة 30 ، هذه هي الجائزة التي تحقق فيها بالفعل معظم التقدم المحرز في حل هذه المشكلة. نظرًا لأنه لا يزال من غير المعروف ما إذا كان العمود المركزي للقاعدة 30 سيصبح دوريًا ، فقد أظهرت إريكا جين في عام 1986 أنه لا يمكن أن يكون هناك عمودين دوريان. وفي الحقيقة هذا صحيح ، ويمكن للمرء أن يجادل مؤيدًا لحقيقة أن عمودًا واحدًا مع خلايا فردية في عمود آخر لا يمكن أن يكون دوريًا .

يستخدم إثبات زوج الأعمدة سمة من سمات القاعدة 30. خذ بعين الاعتبار بنية القاعدة:




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




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

لذا ، ما الذي يمكن استخدامه لحلها؟ إذا اتضح أن العمود المركزي دوري في النهاية ، يمكنك فقط حسابه. نحن نعلم أنه ليس دوريًا بالنسبة للمليارات من الخطوات الأولى ، لكن يمكننا على الأقل افتراض وجود عملية انتقالية تتضمن تريليونات من الخطوات ، وبعد ذلك تصبح دورية.

هل تعتقد أن هذا أمر معقول؟ يحدث العبور - ومن الناحية النظرية (كما في المشكلة الكلاسيكية المتمثلة في إيقاف تشغيل آلة Turing ) ، يمكن أن تكون ذات طول تعسفي. هنا نلقي نظرة على بعض الأمثلة - وجدت أثناء البحث - قواعد مع 4 ألوان ممكنة (الكود الشائع 150898). لنفترض أننا شغله 200 خطوة ، وكما ترى ، سيكون العمود المركزي عشوائيًا تمامًا:




بعد 500 خطوة ، يبدو القالب بأكمله عشوائيًا تمامًا:




هنا يمكنك أن ترى أنه عند الاقتراب من العمود المركزي ، يحدث شيء مفاجئ: بعد 251 خطوة ، يبدو أن العمود المركزي قد تولد من جديد إلى قيمة ثابتة (أو على الأقل ثابت إلى أكثر من مليون خطوة التالية):




هل يمكن أن يحدث نفس الانتقال في المادة 30؟ النظر في الأنماط من المادة 30 ، وحدد تلك التي تكون فيها الأقطار على اليسار دورية:




على ما يبدو ، هناك حدود تفصل الترتيب إلى يسار الاضطراب إلى اليمين. وعلى الأقل بالنسبة لأول 100000 خطوة أو نحو ذلك ، يبدو أن الحدود تتغير في المتوسط ​​بنحو 0.252 خطوة إلى اليسار في كل خطوة - مع بعض الانحرافات العشوائية :




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

هذا ، بالطبع ، هو بالتحديد الحالة التي توضح وجود أنظمة ذات "عابرين" طويلة بشكل استثنائي. الآن النظر في توزيع الأعداد الأولية وحساب LogIntegral [ n ] - PrimePi [ n ]




نعم ، هناك تقلبات ، ولكن في هذا الرسم التوضيحي يبدو أن هذا الاختلاف سيكون دائمًا في المجال الإيجابي. وهذا ، على سبيل المثال ، هو ما كان يناقشه رامانوجان ، ولكن في النهاية اتضح أن هذا ليس كذلك . في البداية ، كانت حدود المكان الذي فشل فيه كبيرة في ذلك الوقت ( عدد Skives 10 ^{10 10 964} ). وعلى الرغم من أن أحداً لم يجد بعد قيمة واضحة لـ n والتي يكون الفارق سالبًا بها ، فمن المعروف أنه يجب أن يوجد n = 10 ³¹⁷ (وفي النهاية سيكون الفرق سالبًا).

لقد شكلت الرأي القائل بأنه لا يوجد شيء من هذا القبيل يحدث في العمود المركزي من المادة 30 ، ولكن حتى الآن ليس لدينا دليل على أن هذا مستحيل ، لا يمكن المجادلة.

تجدر الإشارة إلى أنه من الممكن أن نفترض أنه على الرغم من أنه من الممكن بشكل أساسي إثبات الدورية من خلال الكشف عن الانتظام في العمود المركزي من المادة 30 ، لا يمكن القيام بأي شيء من هذا القبيل لغير الدورية. من المعروف أن هناك أنماطًا تكون أعمدةها المركزية غير دورية ، على الرغم من أنها منتظمة جدًا. الفئة الرئيسية من هذه الأمثلة هي قوالب متداخلة. هنا ، على سبيل المثال ، مثال بسيط للغاية من القاعدة 161 ، حيث يحتوي العمود الأوسط على خلايا بيضاء عند n = 2 ^k :




وهنا مثال أكثر تعقيدًا قليلاً (من القاعدة 69540422 ذات اللونين لجارين) ، حيث يكون العمود المركزي هو تسلسل Thue - Morse - ThueMorse [ n ]:




يمكننا أن نفترض أن تسلسل Thue - Morse يتم إنشاؤه بواسطة التطبيق المتسلسل للاستبدال:




اتضح أنه تم تعيين المصطلح nth في هذا التسلسل على أنه Mod [ DigitCount [ n ، 2، 1]، 2] - لن يكون هذا الكائن دوريًا أبدًا.

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

تجدر الإشارة إلى أن جميع المهام التنافسية من المادة 30 يتم أخذها في الاعتبار عند صياغة خوارزمية تعمل على عدد لا حصر له من الخلايا. , n , , ( )? , 2 ⁿ — , , . n =5:




n =5 n =11:




, , , , . , 2 ⁿ ( , , ).

, n 30 , , 2 ⁿ . , ( ):




, , n 2 ^{0.63 n} . , , . , , ? .

2: ?

10000 30:




:




:




, , 1 () 0 (), , , , , , , .

. 10 000 :




, 1? …

, :




, , . 1 , :




, ? . , . , , , , .

, , 30, .

, , k . , 2 ^k . , - , , , , 30 k ( ).

, . , , k =22, 2 ^k , , :




, , . , – , , .

— — , , , , , , 30, , , , , .

30 , , « », , , , , , . , «»: 30, , , , , , , , 30.

, . 30, , - , , , 30, , , - .

. 30 , , . , , 30 - ( ), , , , 30. 200 :




, :




, , , 0 1.

1900- . , , FractionalPart [ hn ] n h . , FractionalPart [ h ⁿ ] h ( ), — FractionalPart [(3/2) ⁿ ] — . (, , 16- , , 2- FractionalPart [16 x _{n -1} + r [ n ]], r [ n ] n .)

3: n- O( n ) ?

, 150 :




, ( ), , :




n- ? , , : Mod [ IntegerExponent [ n , 2], 2]. , n , , .

, « »? , n , Log [2, n ] . , , O(log n ) .

- 30? , n- , 30 n ² , , . , -, , , — , , , , , .

« » (, , . .), , , , , (, , 3D- . .), .

, 1980- , , , , , , , .

, 3 30 , , . ( O( n ) ; O( n ^α ) α <2, , , O(log ^β ( n )) — , , .)

3 , , n- , O( n ), 150 .

O ( n )? () , « »? , — — , , .

, . , , , n , , , n , (, «», O(log n ) .

, . , , , , Wolfram Language . « ». , , Wolfram Language , .

, 30 , 3 , , , , , , n- , O( n ) , .

, , . , , . , , , , , — , O(log n ) , n .

, P NP . , 30 ( P LOGTIME ), , , , . , , , n n , O( n ² ) , , P (« »), , , , , NP. («») , , , , 2 ⁿ .

, 2 ⁿ , , . , NP- , , , NP . 30 NP-? , , ( - , 30 NP).

30 . : 30 , , 30, «» , , , , .

, 256 110 ( , ), 110 , , , . , , , «» 110 .




30, , — , «» , . , , 30 , , , , .

, , , , , 30. , , (, ) , , . , , — , . , .

, , 3. , , , , n- ?

, 30 . , 2 ^{m 2} m × m , , . , , , O( n ² ) ( ). , O( n ) ? .

, 1 , , - O( n ) — , « ». , ( , 2 ), , , .

- , , , ? , , .

. «» , , , . 30 - . ( — — 30 Wolfram Language, « !» ).

: « - , , ». ? , , , - . . , — , . , , , — - «» 30.

, 30. , 30 - . , , , - 30 , , , , — 30, , , , .

. , 3 2 6 :




, 6 . ( 2 ). , , .

s- n . s- 3 ⁿ , «» ( b — , 2 6) Mod [ Quotient [3 ⁿ , b ^s ], b]. ? , 3 ⁿ n , : , , 3 ⁿ , log( n ). , , , . , 30, , - , .

3 n - 30 , , O( n ), , n , . , r [ n ] , r [ n ] «O-» n , , MaxLimit [ r [ n ]/ n , n →∞ ]<∞.

, ( - ), . , r [ n ] n , , , - , , r [ n ] . , - n ( - ), r [ n ] . , , , r [ n ] O( n ).

30

, ( , ).

Wolfram Language t 30 :




c [ t ].

1: ?

p i t , t > i , [ t + p ] c [ t ].

2: ?

c [ t ]/ t t →∞ 1/2.

3: n- O( n ) ?

machine[ m ] , m (, TuringMachine [...]), machine[ m ][ n ] { v , t }, v — , t — (, ). :




« m, , machine[ m ] n c [ n ] , n , ». ( m , «» ).

, , , , . 3 ( ), , 1 2, . 3 ( ), , 1 . : 1 , , 3 .

1 , , , , , 2. , 2 - 3. , , O( n ) — , , 3, , .

, , ?

1 , , , 30 - , . , 1 , . , , - , .

( , ), 2, 3 , — , , , . , 3 , , (, , ), O( n ) .

, - . , n n- . . , - , . , , n n . , . , « » . , n , . , , O( n ) .

: ? « », / ( ).

, , ( )? , , , , «» , -, ( ) , .

, , . , , , . , () .

, , , , : « ». , , , .

, — - . - n , . . — (« » . .). , , , .

— , , . , ( FindEquationalProof ). , () .

, , , — , . — , .

, . Wolfram|Alpha (, ) , . , .

, , - , , , , .

? , «» , . Wolfram Language , . Wolfram Language, .

« »? , , - . . - , , «» , , - ( ), . , , «» — , .

?

, ? . . , . - , . . - , , .

, , «» — , — , « ». , 2,3 2007 .

— , , 30, , . . - ( , , ). , , ( ) , , .

n — 30 n , n . Wolfram Language . , 0,4 100 000 :




, 30 Xor [ p , Or [ q , r ]], . , CellularAutomaton :




. . , , 30, , 30 , , , : .

. , , «» . 30 — . , , , .

— , , . , , 30, .

, , 30, . 45° , 30, , . ; . ?

? ? - ? , , , , , .

? 30, . , , , , , . , - , , , , , , - .

– , «» . ( , - ). , , , , « » :




, , , . ? , « » ?

, (, ), , - 30?

« 30». , «» ? 30 , ? «» ?

, , 30, , , , 30, . 256 ( ) , , :




, . , . , , . , , , « 30», .

« 30». 30 ( 1), , — , .

2, 30, , .

3 . n- O( n ^γ ) γ <2 ( - )? , n- , O(log( n )) ? O(log( n )) ? ? . ?

, 30. 30, (, , 110) , 30.

, NP-, 30 , , NP-? , . , , , « », 30?

?

2007 2,3 , — , , , . , . 30? . 40 , - ( , !). , , (, ) .

, - ( ), , , , , , , . ( ), , , .

, « » ( , ), . , . , (« » . .). . , - « », , , …

, . , , . , , . , .

, 30 40 , - .

Wolfram Language?
« Wolfram » ( ).