هل أجهزة الكمبيوتر جاهزة لحل هذه المشكلة الحسابية الصعبة السمعة؟

تصور collatz في معالجة js

السيدة تك | SuperRembo عبر codingtrain



تبحث عالمة الكمبيوتر Marijn Heule دائمًا عن تحدٍ رياضي جيد. يتمتع هيول ، الأستاذ المشارك في جامعة كارنيجي ميلون ، بسمعة رائعة في حل مشاكل الرياضيات المستعصية باستخدام الأدوات الحسابية. كانت نتيجته لعام 2016 مع مشكلة ثلاثية فيثاغورس المنطقية دليلاً هائلاً على العناوين الرئيسية: مائتي تيرابايت برهان الرياضيات هو الأكبر على الإطلاق . وهو الآن ينشر نهجًا آليًا لمهاجمة تخمين Collatz البسيط الخادع.

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





الرقم 5 ، على سبيل المثال ، يولد ستة مصطلحات فقط:

5 ، 16 ، 8 ، 4 ، 2 ، 1

كبار السن عارضة أزياء التحدي

يتأرجح الرقم 27 خلال 111 حدًا ، ويتأرجح لأعلى ولأسفل - عند ارتفاع يصل إلى 9232 - قبل أن يهبط في النهاية عند 1.



الرقم 40 يولد تسلسلًا موجزًا ​​آخر:

40 ، 20 ، 10 ، 5 ، 16 ، 8 ، 4 ، 2 ، 1

حتى الآن ، تم التحقق من التخمين بواسطة الكمبيوتر لجميع قيم البداية التي تصل إلى ما يقرب من 300 مليار مليار ويصل كل رقم في النهاية إلى 1.

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



ما نريد معرفته هو ما إذا كان البشر أو أجهزة الكمبيوتر أفضل في حل مثل هذه المشكلات.

مارين هيول

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

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

ترجمة الرياضيات إلى حساب

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

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

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

يكمن جمال هذه الطريقة الآلية في أنه يمكنك تشغيل الكمبيوتر والانتظار.

جيفري لاجارياس

خبرة Heule هي مع أداة حسابية تسمى SAT solver - أو محلل مرضي ، برنامج كمبيوتر يحدد ما إذا كان هناك حل لصيغة أو مشكلة في ظل مجموعة من القيود. على الرغم من الأهمية الحاسمة ، في حالة التحدي الرياضي ، يحتاج محلل SAT أولاً إلى ترجمة المشكلة ، أو تمثيلها ، من حيث أن الكمبيوتر يفهمها. وكما قال يولكو ، طالب دكتوراه مع هيول: التمثيل مهم كثيرًا.

طلقة طويلة ، لكنها تستحق المحاولة

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

'بالمعنى الحرفي للغاية ، كنت أحارب Terminator - على الأقل أحد مبادئ نظرية الإنهاء.'

سكوت آرونسون

استحوذ نظام آرونسون على مشكلة Collatz بـ 11 قاعدة. إذا تمكن الباحثون من الحصول على دليل إنهاء لهذا النظام المماثل ، وتطبيق هذه القواعد الإحدى عشرة بأي ترتيب ، فسيثبت ذلك أن تخمين Collatz صحيح.

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

قواعد إعادة كتابة collatz

تمثيل لنظام إعادة الكتابة المكون من 11 قاعدة لتخمين Collatz.

الطائرات بدون طيار التي تشبه الطيور
مارين هيول

اعتقد آرونسون أنه سيكون من الأسهل بكثير حل النظام مطروحًا منه إحدى القواعد الإحدى عشرة - ترك نظام يشبه Collatz ، اختبارًا حقيقيًا للهدف الأكبر. أصدر تحديًا بين الإنسان والحاسوب: أول من حل جميع الأنظمة الفرعية بعشر قواعد هو الفائز. حاول آرونسون باليد. حاول Heule بواسطة SAT solver: لقد قام بترميز النظام باعتباره مشكلة مرضية - مع طبقة أخرى ذكية من التمثيل ، حيث قام بترجمة النظام إلى لغة الكمبيوتر من المتغيرات التي يمكن أن تكون إما 0s و 1s - ثم ترك محلل SAT الخاص به يعمل على النوى والبحث عن دليل على الإنهاء.

تصور collatz

يتبع النظام هنا تسلسل Collatz لقيمة البداية 27—27 في أعلى يسار السلسلة القطرية ، 1 في أسفل اليمين. هناك 71 خطوة ، بدلاً من 111 ، حيث استخدم الباحثون إصدارًا مختلفًا ولكن مكافئًا من خوارزمية Collatz: إذا كان الرقم زوجيًا ، فقسّمه على 2 ؛ وإلا اضرب في 3 ، أضف 1 ، ثم اقسم الناتج على 2.

مارين هيول

نجح كلاهما في إثبات أن النظام ينتهي بمجموعات مختلفة من 10 قواعد. في بعض الأحيان كانت مهمة تافهة لكل من الإنسان والبرنامج. استغرق نهج هيول الآلي 24 ساعة على الأكثر. تطلب نهج آرونسون جهدًا فكريًا كبيرًا ، استغرق بضع ساعات أو حتى يوم واحد - مجموعة واحدة من 10 قواعد لم يتمكن من إثباتها مطلقًا ، على الرغم من أنه يعتقد اعتقادًا راسخًا أنه يمكن أن يكون لديه ، بمزيد من الجهد. يقول آرونسون ، بالمعنى الحرفي للغاية ، كنت أحارب تيرميناتور - على الأقل أحد مبادئ نظرية الإنهاء.

منذ ذلك الحين ، قامت Yolcu بضبط أداة حل SAT ، ومعايرة الأداة لتناسب طبيعة مشكلة Collatz بشكل أفضل. أحدثت هذه الحيل كل الاختلاف - تسريع إثباتات الإنهاء للأنظمة الفرعية ذات القواعد العشر وتقليل أوقات التشغيل إلى مجرد ثوانٍ.

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

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

حتى الآن ، أجرى Heule تحقيق Collatz باستخدام حوالي 5000 مركز (وحدات المعالجة التي تشغل أجهزة الكمبيوتر ؛ أجهزة الكمبيوتر الاستهلاكية بها أربعة أو ثمانية مراكز). بصفته باحثًا في Amazon ، تلقى دعوة مفتوحة من Amazon Web Services للوصول عمليًا إلى موارد غير محدودة - ما يصل إلى مليون مركز. لكنه متردد في استخدام المزيد بشكل ملحوظ.

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

تحوّل فائق

يكمن جمال هذه الطريقة الآلية في أنه يمكنك تشغيل الكمبيوتر والانتظار ، كما يقول عالم الرياضيات جيفري لاغارياس ، من جامعة ميتشيغان. لقد لعب مع Collatz لنحو خمسين عامًا وأصبح حارسًا للمعرفة ، وقام بتجميع الببليوغرافيات المشروحة وتحرير كتاب حول هذا الموضوع ، التحدي النهائي. بالنسبة إلى Lagarias ، جلب النهج الآلي إلى الذهن أ ورقة 2013 بواسطة عالم الرياضيات في جامعة برينستون جون هورتون كونواي ، الذي فكر في أن مشكلة Collatz قد تكون من بين فئة مراوغة من المشكلات التي تكون صحيحة وغير قابلة للتقرير - ولكن في الوقت نفسه لا يمكن إثباتها بشكل قاطع. كما لاحظ كونواي: ... قد يكون التأكيد على أنها غير قابلة للإثبات لا يمكن إثباته في حد ذاته ، وهكذا.

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

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

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

اكتشاف أرض جديدة مثل الكوكب

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

لتحقيق هذه الغاية ، دعونا نرى من يحل تخمين Collatz أولاً.

يخفي

التقنيات الفعلية

فئة

غير مصنف

تكنولوجيا

التكنولوجيا الحيوية

سياسة التكنولوجيا

تغير المناخ

البشر والتكنولوجيا

وادي السيليكون

الحوسبة

مجلة Mit News

الذكاء الاصطناعي

الفراغ

المدن الذكية

بلوكشين

قصة مميزة

الملف الشخصي للخريجين

اتصال الخريجين

ميزة أخبار معهد ماساتشوستس للتكنولوجيا

1865

وجهة نظري

77 Mass Ave

قابل المؤلف

ملامح في الكرم

شوهد في الحرم الجامعي

خطابات الخريجين

أخبار

انتخابات 2020

فهرس With

تحت القبه

خرطوم الحريق

قصص لانهائية

مشروع تكنولوجيا الوباء

من الرئيس

غلاف القصه

معرض الصور

موصى به