القاعدة 110
الأوتومات الخلوية من القاعدة 110 (والتي تُسمى غالبًا ببساطة القاعدة 110 ) [ أ ] هي أوتومات خلوية أولية ذات سلوك مثير للاهتمام على الحد الفاصل بين الاستقرار والفوضى. في هذا الصدد، تُشبه لعبة الحياة لكونواي : فمثل لعبة الحياة، تُعرف القاعدة 110 بنمط خلفية متكرر معين بأنها كاملة تورينج . [ 2 ] وهذا يعني، من حيث المبدأ، أنه يمكن محاكاة أي عملية حسابية أو برنامج حاسوبي باستخدام هذه الأوتومات.
تعريف
في الأوتوماتا الخلوية الأولية، يتطور نمط أحادي البعد من الأصفار والآحاد وفقًا لمجموعة بسيطة من القواعد. يعتمد ما إذا كانت نقطة في النمط ستكون صفرًا أو واحدًا في الجيل الجديد على قيمتها الحالية، بالإضافة إلى قيمتي جارتيها.
يحتوي جهاز التشغيل الآلي من القاعدة 110 على مجموعة القواعد التالية:
| النمط الحالي | 111 | 110 | 101 | 100 | 011 | 010 | 001 | ٠٠٠ |
|---|---|---|---|---|---|---|---|---|
| حالة جديدة للخلية المركزية | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
يُشتق اسم "القاعدة 110" من حقيقة أنه يمكن تلخيص هذه القاعدة في التسلسل الثنائي 01101110؛ وعند تفسيرها كرقم ثنائي ، فإنها تتوافق مع القيمة العشرية 110. هذا هو نظام تسمية كود Wolfram .
تاريخ
في عام ٢٠٠٤، نشر ماثيو كوك برهانًا على أن القاعدة ١١٠، مع نمط خلفية متكرر محدد، هي قاعدة تورينج كاملة ، أي قادرة على الحساب الشامل ، وهو ما افترضه ستيفن وولفرام في عام ١٩٨٥. [ ٢ ] قدّم كوك برهانه في مؤتمر معهد سانتا فيه CA98 قبل نشر كتاب وولفرام " نوع جديد من العلوم" . وقد نتج عن ذلك نزاع قانوني استنادًا إلى اتفاقية عدم إفصاح مع شركة وولفرام للأبحاث . [ ٣ ] منعت شركة وولفرام للأبحاث نشر برهان كوك لعدة سنوات. [ ٤ ]
عقارات مثيرة للاهتمام
من بين 88 نموذجًا فريدًا ممكنًا للأتمتة الخلوية الأولية ، تُعدّ القاعدة 110 الوحيدة التي تم إثبات اكتمالها من قِبل تورينج بشكل مباشر، على الرغم من أن براهين العديد من القواعد المشابهة تُستنتج كنتائج طبيعية (مثل القاعدة 124، وهي انعكاس أفقي للقاعدة 110). وقد وُصفت القاعدة 110 بأنها واحدة من أبسط أنظمة تورينج الكاملة المعروفة. [ 2 ] [ 5 ] [ 6 ]
تُظهر القاعدة 110، مثل لعبة الحياة ، ما يسميه وولفرام " سلوك الفئة 4 "، وهو ليس مستقرًا تمامًا ولا فوضويًا تمامًا. تظهر الهياكل الموضعية وتتفاعل بطرق معقدة. [ 7 ]
أثبت ماثيو كوك قدرة القاعدة 110 على دعم الحوسبة الشاملة من خلال محاكاة أنظمة العلامات الدورية ، ثم نظام العلامات الثنائية ، ثم آلات تورينج . تتطلب المرحلة الأخيرة وقتًا إضافيًا أُسّيًا لأن شريط آلة تورينج مُشفّر بنظام أرقام أحادي . قدّم نيري وودز (2006) تصميمًا مختلفًا يستبدل أنظمة العلامات الثنائية بآلات تورينج في اتجاه عقارب الساعة، ويتطلب وقتًا إضافيًا متعدد الحدود . [ 6 ]
برهان الشمولية
قدّم ماثيو كوك برهانه على عالمية القاعدة 110 في مؤتمرٍ بمعهد سانتا فيه، عُقد قبل نشر كتابه "نوع جديد من العلوم" . ادّعت شركة وولفرام للأبحاث أن هذا العرض يُخالف اتفاقية عدم الإفصاح التي وقّعها كوك مع جهة عمله، وحصلت على أمرٍ قضائيٍّ باستبعاد ورقة كوك من وقائع المؤتمر المنشورة. ومع ذلك، أصبح وجود برهان كوك معروفًا. لم ينبع الاهتمام ببرهانه من نتيجته بقدر ما نبع من أساليبه، وتحديدًا من التفاصيل التقنية لبنائه. [ 8 ] يختلف طابع برهان كوك اختلافًا كبيرًا عن مناقشة القاعدة 110 في كتاب "نوع جديد من العلوم" . وقد كتب كوك منذ ذلك الحين ورقةً تُفصّل برهانه بالكامل. [ 2 ]
أثبت كوك أن القاعدة 110 عالمية (أو كاملة تورينج) من خلال إظهار إمكانية استخدامها لمحاكاة نموذج حسابي آخر، وهو نظام العلامات الدورية ، المعروف بعالميته. في البداية، عزل كوك عددًا من المركبات الفضائية ، وهي أنماط محلية ذاتية التكرار، يمكن بناؤها على نمط متكرر بلا نهاية في كون القاعدة 110. ثم ابتكر طريقة لتفاعل مجموعات هذه الهياكل بطريقة يمكن استغلالها في الحساب.
المركبات الفضائية في القاعدة 110
تتطلب وظيفة الآلة الشاملة في القاعدة 110 تضمين عدد محدود من الأنماط الموضعية ضمن نمط خلفية متكرر بلا نهاية. يبلغ عرض نمط الخلفية أربعة عشر خلية، ويتكرر كل سبع دورات بالضبط. النمط هو 00010011011111 .
ثلاثة أنماط موضعية ذات أهمية خاصة في الآلة العالمية للقاعدة 110. تظهر هذه الأنماط في الصورة أدناه، محاطة بنمط الخلفية المتكرر. ينتقل النمط الموجود في أقصى اليسار إلى خليتين إلى اليمين ويتكرر كل ثلاثة أجيال. ويتألف من التسلسل 0001110111 المحاط بنمط الخلفية المذكور أعلاه، بالإضافة إلى تطورين مختلفين لهذا التسلسل.
في الأشكال، يمر الوقت من الأعلى إلى الأسفل: يمثل الخط العلوي الحالة الأولية، ويمثل كل خط لاحق الحالة في الوقت التالي.
يتحرك التركيب المركزي ثماني خلايا إلى اليسار ويتكرر كل ثلاثين جيلاً. ويتألف من التسلسل 1001111 المحاط بنمط الخلفية المذكور أعلاه، بالإضافة إلى تسعة وعشرين تطوراً مختلفاً لهذا التسلسل.
يبقى الهيكل الموجود في أقصى اليمين ثابتًا ويتكرر كل سبعة أجيال. ويتألف من التسلسل 111 المحاط بنمط الخلفية المذكور أعلاه، بالإضافة إلى خمسة تطورات مختلفة لهذا التسلسل.
فيما يلي صورة توضح أول بنيتين تمر عبر بعضهما البعض دون التفاعل إلا عن طريق الانتقال (يسار)، وتتفاعلان لتشكيل البنية الثالثة (يمين).
هناك العديد من المركبات الفضائية الأخرى في القاعدة 110، لكنها لا تظهر بشكل بارز في برهان الشمولية.
بناء نظام العلامات الدورية
تتكون آلة نظام العلامات الدورية من ثلاثة مكونات رئيسية:
- سلسلة بيانات ثابتة؛
- سلسلة متكررة بلا حدود من قواعد الإنتاج المحدودة التي تبدأ من اليمين وتتحرك نحو اليسار؛
- سلسلة متكررة بلا حدود من نبضات الساعة التي تبدأ من اليسار وتتحرك نحو اليمين.
تُعدّ المسافة الأولية بين هذه المكونات بالغة الأهمية. ولكي يتمكن الأوتومات الخلوي من تطبيق نظام الوسوم الدوري، يجب اختيار الشروط الأولية للأوتومات بعناية فائقة بحيث تتفاعل البنى الموضعية المختلفة الموجودة فيه بطريقة عالية التنظيم.
تُمثَّل سلسلة البيانات في نظام الوسوم الدورية بسلسلة من البنى الثابتة المتكررة من النوع الموضح أعلاه. وتُستخدم مسافات أفقية متفاوتة بين هذه البنى للتمييز بين الرموز 1 والرموز 0. تُمثل هذه الرموز الكلمة التي يعمل عليها نظام الوسوم الدورية، ويتم حذف أول رمز من هذا النوع عند تطبيق كل قاعدة إنتاج. عندما يكون هذا الرمز الأول 1، تُضاف رموز جديدة إلى نهاية السلسلة؛ وعندما يكون 0، لا تُضاف أي رموز جديدة. آلية تحقيق ذلك موضحة أدناه.
تدخل من اليمين سلسلة من البنى المتحركة إلى اليسار من النوع الموضح أعلاه، مفصولة بمسافات أفقية متفاوتة. يتم دمج أعداد كبيرة من هذه البنى بمسافات مختلفة لتمثيل الأصفار والآحاد في قواعد إنتاج نظام الوسوم الدوري. ولأن قواعد إنتاج نظام الوسوم معروفة عند إنشاء البرنامج، وتتكرر بلا نهاية، يمكن تمثيل أنماط الأصفار والآحاد في الحالة الابتدائية بسلسلة متكررة بلا نهاية. يفصل كل قاعدة إنتاج عن القاعدة التي تليها بنية أخرى تُعرف بفاصل القواعد (أو فاصل الكتل )، والتي تتحرك نحو اليسار بنفس معدل ترميز قواعد الإنتاج.
عندما يصادف فاصل القواعد المتحرك لليسار رمزًا ثابتًا في سلسلة بيانات نظام الوسوم الدورية، فإنه يتسبب في تدمير أول رمز يصادفه. ومع ذلك، يختلف سلوكه اللاحق اعتمادًا على ما إذا كان الرمز المشفر بواسطة السلسلة 0 أو 1. إذا كان 0، يتحول فاصل القواعد إلى بنية جديدة تمنع قاعدة الإنتاج الواردة. تُدمر هذه البنية الجديدة عند مصادفتها فاصل القواعد التالي.
أما إذا كان الرمز في السلسلة هو 1، فإن فاصل القواعد يتحول إلى بنية جديدة تسمح بمرور قاعدة الإنتاج الواردة. ورغم أن هذه البنية الجديدة تُهدم عند مصادفتها فاصل القواعد التالي، إلا أنها تسمح أولًا بمرور سلسلة من البنى باتجاه اليسار. ثم تُضاف هذه البنى إلى نهاية سلسلة بيانات نظام الوسوم الدورية. ويتم هذا التحويل النهائي بواسطة سلسلة من نبضات الساعة المتكررة بلا نهاية، والتي تتحرك باتجاه اليمين، وفقًا للنمط الموضح أعلاه. تُحوّل نبضات الساعة رموز 1 الواردة من قاعدة الإنتاج إلى رموز 1 ثابتة في سلسلة البيانات، ورموز 0 الواردة من قاعدة الإنتاج إلى رموز 0 ثابتة في سلسلة البيانات.
نظام العلامات الدورية يعمل
الشكل أعلاه هو الرسم التخطيطي لإعادة بناء نظام العلامات الدورية في القاعدة 110.
انظر أيضاً
ملحوظات
- ↑ العدد ١١٠ هو العدد ١١٠ مكتوبًا بالنظام العشري التقليدي، وبالتالي يُنطق كما تُنطق الأعداد الاسمية عادةً. على سبيل المثال، ينطق ستيفن وولفرام الاسم "قاعدة واحد-عشرة". [ ١ ]
مراجع
- ↑ ستيفن وولفرام (2003). نوع جديد من العلوم - ستيفن وولفرام . تلفزيون جامعة كاليفورنيا (UCTV). يبدأ الحدث في تمام الساعة 9:51 . تاريخ الاسترجاع: 19 يونيو 2023 .
- 1 2 3 4 كوك (2004) .
- ↑ قضية Wolfram Research Inc ضد Cook (2:00-cv-09357) (يشار إليها أحيانًا باسم "Wolfram Research Inc. ضد Matthew Cook. 8/31 CV00-9357 CBM"
- ↑ جايلز (2002) .
- ↑ وولفرام (2002) ، الصفحات 169، 675-691
- 1 2 نيري وودز (2006) .
- ↑ وولفرام (2002) ، ص 229
- ↑ مارتينيز، جينارو ج.؛ سيك توه مورا، خوان؛ تشابا، سيرجيو؛ ليمايتر، كريستيان (أبريل 2019). "ملاحظات موجزة وتاريخ الحوسبة في المكسيك خلال 50 عامًا" . المجلة الدولية للأنظمة المتوازية والناشئة والموزعة . 35 (2): 185-192 . arXiv : 1905.07527 . doi : 10.1080/17445760.2019.1608990 . S2CID 150262966. تاريخ الاسترجاع: 15 أبريل 2020 .
المراجع
- كوك، ماثيو (2004). "الشمولية في الأوتوماتا الخلوية الأولية" (ملف PDF) . الأنظمة المعقدة . 15 : 1-40 . doi : 10.25088/ComplexSystems.15.1.1 .
- جايلز، جيم (2002). "أي نوع من العلوم هذا؟" . مجلة نيتشر . 417 (6886): 216-218 . Bibcode : 2002Natur.417..216G . doi : 10.1038 / 417216a . PMID 12015565. S2CID 10636328 .
- نيري، تورلو؛ وودز، داميان (2006). "اكتمال P لقاعدة الأوتوماتا الخلوية 110". في: بوغليسي، ميشيل؛ برينيل، بارت؛ ساسون، فلاديميرو؛ فيجنر، إنجو (محررون). الأوتوماتا واللغات والبرمجة: الندوة الدولية الثالثة والثلاثون، ICALP 2006، البندقية، إيطاليا، 10-14 يوليو 2006، وقائع المؤتمر، الجزء الأول . سلسلة محاضرات في علوم الحاسوب. المجلد 4051. سبرينغر. الصفحات 132-143 . doi : 10.1007/11786986_13 . ISBN 978-3-540-35904-3.
- وولفرام، ستيفن (2002). نوع جديد من العلوم . وولفرام ميديا. ISBN 1-57955-008-8.
للمزيد من القراءة
- كوك، ماثيو (2008). "نظرة عملية على حساب القاعدة 110". في: نيري، ت.؛ وودز، د.؛ سيدا، أ.ك.؛ مورفي، ن. (محررون). تعقيد البرامج البسيطة . وقائع إلكترونية في علوم الحاسوب النظرية. المجلد 1. الصفحات 31-55 . arXiv : 0906.3248v1 . doi : 10.4204/EPTCS.1.4 . S2CID 10266058 .
- مارتينيز، جينارو ج.؛ أداماتزكي، أ.؛ تشين، فانغيو؛ تشوا، ليون (2012). "حول تصادمات السوليتون بين المواقع في الأوتوماتا الخلوية الأولية المعقدة: القواعد 54 و110 وما بعدها". الأنظمة المعقدة . 21 (2): 117-142 . arXiv : 1301.6258 . doi : 10.25088 /ComplexSystems.21.2.117 . S2CID 10165042 .
- مارتينيز، جينارو ج.؛ أداماتزكي، أ.؛ ستيفنز، كريستوفر ر.؛ هوفليش، أليخاندرو ف. (2011). "مصادمات فائقة باستخدام الأوتوماتا الخلوية" . المجلة الدولية للفيزياء الحديثة ج . 22 (4): 419-439 . arXiv : 1105.4332 . Bibcode : 2011IJMPC..22..419M . doi : 10.1142/S0129183111016348 . S2CID 7508070 .
- مارتينيز، جينارو J.؛ ماكينتوش، هارولد ف . مورا، خوان CST. فيرغارا، سيرجيو في سي (2003-2008). "إعادة إنتاج أنظمة العلامات الدورية التي طورها ماثيو كوك مع القاعدة 110 باستخدام المراحل fi_1" (PDF) . مجلة الأتمتة الخلوية . 6 ( 2 – 3): 121 – 161.
- مارتينيز، جينارو جيه؛ ماكنتوش، هارولد في ؛ مورا، خوان سي إس تي؛ فيرغارا، سيرجيو في سي (2008). "تحديد لغة منتظمة بواسطة هياكل قائمة على الانزلاق تسمى المراحل fi_1 في القاعدة 110". مجلة الأوتوماتا الخلوية . 3 (3): 231-270 . arXiv : 0706.3348v1 . Bibcode : 2007arXiv0706.3348J .
- مارتينيز، جينارو J.؛ ماكينتوش، هارولد ف . مورا، خوان CST. فيرجارا، سيرجيو في سي (2007). "القاعدة 110 من الأشياء وغيرها من التصادمات القائمة على الإنشاءات" (PDF) . مجلة الأتمتة الخلوية . 2 (3): 219 – 242.
- مارتينيز، جينارو جيه؛ ماكنتوش، هارولد في ؛ مورا، خوان سي إس تي (2006). "الطائرات الشراعية في القاعدة 110" (ملف PDF) . المجلة الدولية للحوسبة غير التقليدية . 2 : 1-49 .
- مارتينيز، جينارو جيه؛ ماكنتوش، هارولد في ؛ مورا، خوان سي إس تي (2003). "إنتاج الطائرات الشراعية عن طريق التصادمات في القاعدة 110" (ملف PDF) . التطورات في الحياة الاصطناعية . سلسلة محاضرات في علوم الحاسوب. المجلد 2801. الصفحات 175-182 . doi : 10.1007/978-3-540-39432-7_19 . ISBN 978-3-540-20057-4.
- مارتينيز، جينارو جيه؛ ماكنتوش، هارولد في (2001). "أطلس: تصادمات الطائرات الشراعية كمراحل من الأثير في القاعدة 110" .
- ماكنتوش، هارولد ف. (1999). "القاعدة 110 فيما يتعلق بوجود الطائرات الشراعية" (PDF) .
- ماكنتوش، هارولد ف. (2002). "القاعدة 110 عالمية!" (ملف PDF) .
روابط خارجية
- قواعد الأوتوماتا الخلوية
- شفرة وولفرام