الأوتوماتون الخلوي

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 11 صور
الموسوعة الحرة

بندقية جوسبر الشراعية التي تخلق " طائرات شراعية " في لعبة الحياة الخلوية لكونواي [ 1 ]

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

تتكون الأوتوماتا الخلوية من شبكة منتظمة من الخلايا ، كل منها في إحدى حالات محدودة ، مثل التشغيل والإيقاف (على عكس شبكة الخرائط المترابطة ). يمكن أن تكون الشبكة بأي عدد محدود من الأبعاد. لكل خلية، تُحدد مجموعة من الخلايا تُسمى جوارها نسبةً إلى تلك الخلية. تُختار حالة ابتدائية (عند الزمن t = 0) بتعيين حالة لكل خلية. يُنشأ جيل جديد (بزيادة t بمقدار 1)، وفقًا لقاعدة ثابتة (عادةً ما تكون دالة رياضية) [ 3 ] تُحدد الحالة الجديدة لكل خلية بناءً على حالتها الحالية وحالات الخلايا المجاورة لها. عادةً، تكون قاعدة تحديث حالة الخلايا واحدة لجميع الخلايا ولا تتغير بمرور الوقت، وتُطبق على الشبكة بأكملها في آنٍ واحد، [ 4 ] مع وجود استثناءات معروفة، مثل الأوتوماتا الخلوية العشوائية والأوتوماتا الخلوية غير المتزامنة .  

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

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

ملخص

تمثل الخلايا الحمراء نطاق مور للخلية الزرقاء.
تمثل الخلايا الحمراء نطاق فون نيومان للخلية الزرقاء. ويشمل نطاق "التقاطع" الثاني الخلايا الوردية أيضًا.

إحدى طرق محاكاة الأوتوماتا الخلوية ثنائية الأبعاد هي استخدام ورقة رسم بياني لانهائية مع مجموعة من القواعد التي تتبعها الخلايا. يُطلق على كل مربع اسم "خلية"، ولكل خلية حالتان محتملتان: سوداء أو بيضاء. جوار الخلية هو الخلايا المجاورة لها، وعادةً ما تكون الخلايا المجاورة. النوعان الأكثر شيوعًا من الجوار هما جوار فون نيومان وجوار مور . [ 5 ] يتكون جوار فون نيومان، نسبةً إلى مؤسس نظرية الأوتوماتا الخلوية، من الخلايا الأربع المتجاورة عموديًا . [ 5 ] أما جوار مور فيشمل جوار فون نيومان بالإضافة إلى الخلايا الأربع المتجاورة قطريًا. [ 5 ] بالنسبة لهذه الخلية وجوار مور الخاص بها، يوجد 512 نمطًا ممكنًا (2^ 9 ). لكل نمط من الأنماط الـ 512 الممكنة، يحدد جدول القواعد ما إذا كانت الخلية المركزية ستكون سوداء أم بيضاء في الفترة الزمنية التالية. تُعد لعبة الحياة لكونواي نسخة شائعة من هذا النموذج. نوع آخر شائع من الجوار هو جوار فون نيومان الموسع ، الذي يشمل أقرب خليتين في كل اتجاه متعامد، ليصبح المجموع ثماني خلايا. [ 5 ] المعادلة العامة للعدد الإجمالي الممكن للأوتوماتا هي k = k s ، حيث k هو عدد الحالات الممكنة للخلية، و s هو عدد الخلايا المجاورة (بما في ذلك الخلية المراد حساب حالتها) المستخدمة لتحديد الحالة التالية للخلية. [ 6 ] وبالتالي، في النظام ثنائي الأبعاد ذي جوار مور، سيكون العدد الإجمالي الممكن للأوتوماتا هو 2 2 9 ، أو1.34 × 10 154 .

يُفترض عادةً أن كل خلية في الكون تبدأ في الحالة نفسها، باستثناء عدد محدود من الخلايا في حالات أخرى؛ ويُطلق على تعيين قيم الحالة اسم التكوين . [ 7 ] وبشكل أعم، يُفترض أحيانًا أن الكون يبدأ مغطى بنمط دوري، وأن عددًا محدودًا فقط من الخلايا يخالف هذا النمط. هذا الافتراض الأخير شائع في الأوتوماتا الخلوية أحادية البعد.

شكل حلقي ( الحلقة )

غالبًا ما تُحاكى الأوتوماتا الخلوية على شبكة محدودة بدلًا من شبكة غير محدودة. في بُعدين، سيكون الكون مستطيلًا بدلًا من مستوى لا نهائي. تكمن المشكلة الواضحة في الشبكات المحدودة في كيفية التعامل مع الخلايا الموجودة على الحواف. ستؤثر طريقة التعامل معها على قيم جميع الخلايا في الشبكة. إحدى الطرق الممكنة هي السماح لقيم هذه الخلايا بالبقاء ثابتة. طريقة أخرى هي تعريف الجوار بشكل مختلف لهذه الخلايا. يمكن القول إن لها عددًا أقل من الجيران، ولكن سيتعين حينها أيضًا تحديد قواعد جديدة للخلايا الموجودة على الحواف. عادةً ما تُعالج هذه الخلايا بشروط حدودية دورية ينتج عنها ترتيب حلقي : عندما تخرج خلية من الأعلى، تدخل خلية أخرى من الموضع المقابل في الأسفل، وعندما تخرج خلية من اليسار، تدخل خلية أخرى من اليمين. (يحاكي هذا بشكل أساسي تبليطًا دوريًا لانهائيًا، ويُشار إليه أحيانًا في مجال المعادلات التفاضلية الجزئية باسم شروط الحدود الدورية ). يمكن تصور ذلك على أنه لصق الحافتين اليمنى واليسرى للمستطيل لتشكيل أنبوب، ثم لصق الحافتين العلوية والسفلية للأنبوب لتشكيل حلقة ( شكل كعكة). تُعالج الأكوان ذات الأبعاد الأخرى بطريقة مماثلة. يحل هذا مشاكل الحدود باستخدام الجوار، ولكن من مزاياه الأخرى سهولة برمجته باستخدام دوال حسابية نمطية . على سبيل المثال ، في آلة خلوية أحادية البعد مثل الأمثلة أدناه، يكون جوار الخلية xᵢᵗ هو { xᵢ⁻¹ᵗ⁻¹ , xᵢᵗ⁻¹ , xᵢ⁺¹ᵗ⁻¹ } ، حيث t هي الخطوة الزمنية (رأسيًا)، و i هو المؤشر ( أفقيًا) في جيل واحد .

تاريخ

درس ستانيسواف أولام ، أثناء عمله في مختبر لوس ألاموس الوطني في أربعينيات القرن العشرين، نمو البلورات، مستخدمًا شبكة بسيطة كنموذج له. [ 8 ] في الوقت نفسه، كان جون فون نيومان ، زميل أولام في لوس ألاموس ، يعمل على مشكلة الأنظمة ذاتية التكاثر . [ 9 ] استند تصميم فون نيومان الأولي إلى فكرة قيام روبوت ببناء روبوت آخر. يُعرف هذا التصميم بالنموذج الحركي. [ 10 ] [ 11 ] مع تطويره لهذا التصميم، أدرك فون نيومان الصعوبة البالغة في بناء روبوت ذاتي التكاثر، والتكلفة الباهظة لتزويد الروبوت بكمية هائلة من الأجزاء التي يمكن من خلالها بناء نظيره. كتب نيومان ورقة بحثية بعنوان "النظرية العامة والمنطقية للآلات" لندوة هيكسون عام 1948. [ 9 ] وكان أولام هو من اقترح استخدام نظام منفصل لإنشاء نموذج اختزالي للتكاثر الذاتي. [ 12 ] [ 13 ] وقد أجرى نيلز آل باريسيلي العديد من الاستكشافات المبكرة لهذه النماذج من الحياة الاصطناعية .

جون فون نيومان ، شارة هوية لوس ألاموس

ابتكر أولام وفون نيومان طريقةً لحساب حركة السوائل في أواخر خمسينيات القرن العشرين. تمحورت الفكرة الأساسية لهذه الطريقة حول اعتبار السائل مجموعةً من الوحدات المنفصلة، ​​وحساب حركة كل وحدة بناءً على سلوك جيرانها. [ 14 ] وهكذا وُلد أول نظام للأتمتة الخلوية. وكما هو الحال في شبكة أولام الشبكية، فإن أتمتة فون نيومان الخلوية ثنائية الأبعاد، حيث تم تنفيذ آلية التكرار الذاتي الخاصة به خوارزميًا. وكانت النتيجة ناسخًا وبانيًا عالميًا يعمل ضمن أتمتة خلوية ذات جوار صغير (الخلايا المتلامسة فقط هي المجاورة؛ بالنسبة لأتمتة فون نيومان الخلوية، الخلايا المتعامدة فقط )، وبـ 29 حالة لكل خلية. [ 15 ] وقدّم فون نيومان برهانًا على وجود نمط معين يمكنه إنشاء نسخ لا نهائية من نفسه داخل الكون الخلوي المحدد، وذلك من خلال تصميم تكوين مكون من 200,000 خلية قادر على القيام بذلك. [ 15 ] يُعرف هذا التصميم بنموذج التبليط ، ويُطلق عليه اسم مُنشئ فون نيومان الشامل . [ 16 ]

في أربعينيات القرن العشرين، طوّر نوربرت وينر وأرتورو روزنبلويث نموذجًا للأوساط القابلة للاستثارة، يحمل بعض خصائص الأوتوماتا الخلوية. [ 17 ] وكان دافعهما الأساسي هو الوصف الرياضي لتوصيل النبضات في أنظمة القلب. مع ذلك، لا يُعدّ نموذجهما أوتوماتا خلوية، لأن الوسط الذي تنتشر فيه الإشارات متصل، بينما تكون جبهات الموجات منحنية. [ 17 ] [ 18 ] وفي عام 1978، طوّر جيه إم غرينبيرغ وإس بي هاستينغز نموذجًا حقيقيًا للأوتوماتا الخلوية للأوساط القابلة للاستثارة، ودرساه؛ انظر: أوتوماتا غرينبيرغ-هاستينغز الخلوية . يحتوي العمل الأصلي لوينر وروزنبلويث على العديد من الأفكار القيّمة، ولا يزال يُستشهد به في منشورات الأبحاث الحديثة حول اضطراب نظم القلب والأنظمة القابلة للاستثارة. [ 19 ]

في ستينيات القرن العشرين، دُرست الأوتوماتا الخلوية كنوع خاص من الأنظمة الديناميكية ، ورُبطت لأول مرة بمجال الديناميكا الرمزية في الرياضيات. وفي عام ١٩٦٩، جمع غوستاف أ. هيدلوند العديد من النتائج التي تبنت هذا المنظور [ ٢٠ ] في ورقة بحثية لا تزال تُعتبر مرجعًا أساسيًا في الدراسة الرياضية للأوتوماتا الخلوية. وتتمثل النتيجة الأهم في توصيف مجموعة القواعد العامة للأوتوماتا الخلوية، في نظرية كورتيس-هيدلوند-ليندون، بأنها مجموعة التشاكلات الداخلية المستمرة لفضاءات الإزاحة .

في عام 1969، نشر رائد الحوسبة الألماني كونراد تسوزه كتابه "حساب الفضاء "، مقترحًا أن القوانين الفيزيائية للكون منفصلة بطبيعتها، وأن الكون بأكمله هو نتاج عملية حسابية حتمية على آلة خلوية واحدة؛ أصبحت "نظرية تسوزه" أساس مجال الدراسة المسمى الفيزياء الرقمية . [ 21 ]

في عام 1969، أنجز عالم الحاسوب ألفي راي سميث أطروحة دكتوراه من جامعة ستانفورد حول نظرية الأوتوماتا الخلوية، وهي أول دراسة رياضية للأوتوماتا الخلوية كفئة عامة من الحواسيب. وقد انبثقت العديد من الأبحاث من هذه الأطروحة: فقد بيّن تكافؤ الجوارات ذات الأشكال المختلفة، وكيفية اختزال جوار مور إلى جوار فون نيومان، أو كيفية اختزال أي جوار إلى جوار فون نيومان. [ 22 ] كما أثبت أن الأوتوماتا الخلوية ثنائية الأبعاد تتمتع بخاصية الحوسبة الشاملة، وقدّم الأوتوماتا الخلوية أحادية البعد، وأظهر أنها تتمتع أيضاً بخاصية الحوسبة الشاملة، حتى مع الجوارات البسيطة. [ 23 ] وبيّن كيفية دمج برهان فون نيومان المعقد لعمومية البناء (وبالتالي الآلات ذاتية التكاثر) في نتيجة لعمومية الحوسبة في الأوتوماتا الخلوية أحادية البعد. [ 24 ] كتب فون نيومان، في إطار مقدمة النسخة الألمانية من كتابه عن تحليل المحادثة، مسحًا شاملًا للمجال مع عشرات المراجع لأوراق بحثية كتبها العديد من المؤلفين في بلدان مختلفة على مدى عقد من الزمن تقريبًا، وهي أوراق غالبًا ما يتجاهلها الباحثون المعاصرون في مجال تحليل المحادثة. [ 25 ]

في سبعينيات القرن العشرين، اشتهرت لعبة الحياة، وهي عبارة عن آلة خلوية ثنائية الأبعاد ذات حالتين، على نطاق واسع، لا سيما بين رواد مجال الحوسبة. ابتكرها جون كونواي، ونشرها مارتن غاردنر في مقالٍ له في مجلة ساينتفك أمريكان ، [ 26 ] وقواعدها كالتالي:

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

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

بدأ ستيفن وولفرام العمل بشكل مستقل على الأوتوماتا الخلوية في منتصف عام 1981 بعد أن لاحظ كيف تتشكل الأنماط المعقدة في الطبيعة بما يخالف القانون الثاني للديناميكا الحرارية . [ 29 ] وقد حفزت أبحاثه في البداية رغبته في نمذجة أنظمة مثل الشبكات العصبية الموجودة في الدماغ. [ 29 ] نشر بحثه الأول في مجلة " Reviews of Modern Physics" في يونيو 1983، حيث تناول الأوتوماتا الخلوية الأولية ( القاعدة 30 على وجه الخصوص). [ 2 ] [ 29 ] دفعه التعقيد غير المتوقع لسلوك هذه القواعد البسيطة إلى الشك في أن التعقيد في الطبيعة قد يكون ناتجًا عن آليات مماثلة. [ 29 ] إلا أن أبحاثه قادته إلى إدراك أن الأوتوماتا الخلوية غير فعالة في نمذجة الشبكات العصبية. [ 29 ] بالإضافة إلى ذلك، خلال هذه الفترة صاغ وولفرام مفاهيم العشوائية الجوهرية وعدم قابلية الاختزال الحسابي ، [ 30 ] واقترح أن القاعدة 110 قد تكون عالمية - وهي حقيقة أثبتها لاحقًا مساعد وولفرام البحثي ماثيو كوك في التسعينيات. [ 31 ]

تصنيف

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

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

هذه التعريفات نوعية بطبيعتها، وتسمح ببعض التأويل. ووفقًا لوولفرام، "...في أي نظام تصنيف عام تقريبًا، توجد حتمًا حالات تُنسب إلى فئة معينة بتعريف معين، وإلى فئة أخرى بتعريف آخر. وينطبق الأمر نفسه على الأوتوماتا الخلوية: إذ توجد أحيانًا قواعد... تُظهر بعض سمات فئة ما، وبعض سمات فئة أخرى." [ 34 ]

بُذلت عدة محاولات لتصنيف الأوتوماتا الخلوية في فئات دقيقة رسميًا، مستوحاة من تصنيف وولفرام. على سبيل المثال، اقترح كوليك ويو ثلاث فئات محددة جيدًا (وفئة رابعة للأوتوماتا التي لا تتطابق مع أي من هذه الفئات)، والتي تُسمى أحيانًا فئات كوليك-يو؛ وقد ثبت أن الانتماء إلى هذه الفئات غير قابل للتقرير . [ 35 ] [ 36 ] [ 37 ] يمكن تقسيم فئة وولفرام الثانية إلى مجموعتين فرعيتين من القواعد المستقرة (ذات النقطة الثابتة) والقواعد المتذبذبة (الدورية). [ 38 ]

نشأت فكرة وجود أربع فئات من الأنظمة الديناميكية من الكيميائي الحائز على جائزة نوبل إيليا بريغوجين، الذي حدد هذه الفئات الأربع للأنظمة الديناميكية الحرارية: (1) الأنظمة في حالة توازن ديناميكي حراري، (2) الأنظمة المتجانسة مكانيًا/زمنيًا، (3) الأنظمة الفوضوية، و(4) الأنظمة المعقدة البعيدة عن حالة التوازن ذات البنى المبددة (انظر الشكل 1 في ورقة نيكوليس، تلميذ بريغوجين، عام 1974). [ 39 ]

قابل للعكس

تكون الأوتوماتا الخلوية قابلة للانعكاس إذا كان لكل تكوين حالي لها تكوين سابق واحد فقط ( صورة سابقة ). [ 40 ] إذا اعتبرنا الأوتوماتا الخلوية دالةً تربط التكوينات ببعضها، فإن قابلية الانعكاس تعني أن هذه الدالة تقابلية . [ 40 ] إذا كانت الأوتوماتا الخلوية قابلة للانعكاس، فيمكن وصف سلوكها المعكوس زمنيًا بأنها أوتوماتا خلوية أيضًا؛ وهذه الحقيقة هي نتيجة لنظرية كورتيس-هيدلوند-ليندون ، وهي توصيف طوبولوجي للأوتوماتا الخلوية. [ 41 ] [ 42 ] بالنسبة للأوتوماتا الخلوية التي لا تحتوي كل تكويناتها على صورة سابقة، تُسمى التكوينات التي لا تحتوي على صور سابقة بأنماط جنة عدن . [ 43 ]

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

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

شمولي

تُعدّ الأوتوماتا الخلوية الشاملة فئة خاصة من الأوتوماتا الخلوية. يُمثّل كل خلية في الأوتوماتا الخلوية الشاملة برقم (عادةً ما يكون عددًا صحيحًا مُختارًا من مجموعة محدودة)، وتعتمد قيمة الخلية عند الزمن t فقط على مجموع قيم الخلايا المجاورة لها (بما في ذلك الخلية نفسها أحيانًا) عند الزمن t − 1. [ 49 ] [ 50 ]   

إذا كانت حالة الخلية عند الزمن t تعتمد على حالتها الخاصة وعلى مجموع حالات جيرانها عند الزمن t − 1، فإن الأوتوماتا الخلوية تُسمى بشكل صحيح أوتوماتا خارجية شاملة . [ 50 ] لعبة الحياة لكونواي هي أوتوماتا خارجية شاملة (ولكنها ليست شاملة)، حيث تكون قيم الخلايا 0 و1. تُسمى الأوتوماتا الخلوية الخارجية الشاملة التي لها نفس بنية جوار مور للعبة الحياة أحيانًا بالأوتوماتا الخلوية الشبيهة بالحياة . [ 51 ] [ 52 ]   

بشكل عام، مجموعة القواعد المتناحية هي مجموعة ليست بالضرورة شاملة خارجية، ولكنها مع ذلك تمتلك جميع تناظرات الانعكاس. في حالة الأوتوماتا الخلوية على شبكة مربعة، تكون مجموعة التناظرات هي D8 .

توجد العديد من التعميمات الممكنة لمفهوم الأوتوماتا الخلوية.

آلة خلوية تعتمد على خلايا سداسية بدلاً من المربعات (القاعدة 34/2)

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

كذلك، يمكن أن تكون القواعد احتمالية وليست حتمية. تُسمى هذه الأوتوماتا الخلوية بالأوتوماتا الخلوية الاحتمالية . تُعطي القاعدة الاحتمالية، لكل نمط عند الزمن t ، احتمالات انتقال الخلية المركزية إلى كل حالة ممكنة عند الزمن t  +  1. أحيانًا تُستخدم قاعدة أبسط؛ على سبيل المثال: "القاعدة هي لعبة الحياة، ولكن في كل خطوة زمنية، هناك احتمال بنسبة 0.001% لانتقال كل خلية إلى اللون المقابل."

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

في الأوتوماتا الخلوية، لا تتأثر الحالة الجديدة للخلية بالحالة الجديدة للخلايا الأخرى. يمكن تغيير ذلك بحيث، على سبيل المثال، يمكن تحديد كتلة من الخلايا بحجم 2×2 من خلال حالتها الخاصة والخلايا المجاورة لها.

توجد آلات متصلة . وهي تشبه الآلات الخلوية الشاملة، ولكن بدلاً من أن تكون القواعد والحالات منفصلة ( مثل جدول يستخدم الحالات {0، 1، 2})، تُستخدم دوال متصلة، وتصبح الحالات متصلة (عادةً ما تكون قيمها في النطاق [0، 1] ). حالة الموقع هي عدد محدود من الأعداد الحقيقية. يمكن لبعض الآلات الخلوية أن تُنتج أنماط انتشار في السوائل بهذه الطريقة.

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

توجد أمثلة معروفة للأتمتة المكانية المستمرة، والتي تُظهر ظواهر انتشار مماثلة للطائرات الشراعية في لعبة الحياة. [ 55 ]

تُعد أتمتة إعادة كتابة الرسوم البيانية امتدادات للأتمتة الخلوية القائمة على أنظمة إعادة كتابة الرسوم البيانية . [ 56 ]

الأوتوماتا الخلوية الأولية

أبسط نموذج خلوي غير تافه هو نموذج أحادي البعد، حيث توجد حالتان محتملتان لكل خلية، وتُعرَّف جيران الخلية بأنها الخلايا المجاورة لها من كلا الجانبين. تشكل الخلية وجارتيها جوارًا من 3 خلايا، لذا يوجد 2³ =  8  أنماط محتملة للجوار. تتكون القاعدة من تحديد ما إذا كانت الخلية ستكون 1 أو 0 في الجيل التالي لكل نمط. وبالتالي، يوجد 2⁸ =  256  قاعدة محتملة. [ 6 ]

رسم متحرك يوضح كيف تحدد قواعد الأوتوماتا الخلوية أحادية البعد الجيل التالي

تُعرف هذه الأوتوماتا الخلوية الـ 256 عمومًا برمز وولفرام الخاص بها ، وهو اصطلاح تسمية قياسي ابتكره وولفرام، يُعطي كل قاعدة رقمًا من 0 إلى 255. وقد حللت العديد من الأبحاث وقارنت الحالات المختلفة بين هذه الأوتوماتا الخلوية الـ 256 (العديد منها متماثل بشكل بديهي). وتُعد الأوتوماتا الخلوية للقواعد 30 و 90 و 110 و 184 مثيرة للاهتمام بشكل خاص. تُظهر الصور أدناه تاريخ القاعدتين 30 و110 عندما يتكون التكوين الابتدائي من الرقم 1 (في أعلى كل صورة) محاطًا بأصفار. يُمثل كل صف من البكسلات جيلًا في تاريخ الأوتوماتا، حيث يُمثل t = 0 الصف العلوي. كل بكسل مُلون باللون الأبيض للرقم 0 وباللون الأسود للرقم  1.

القاعدة 30
قاعدة 30 للأتمتة الخلوية (الثنائي 00011110 = العشري 30)
النمط الحالي111110101100011010001٠٠٠
حالة جديدة للخلية المركزية00011110

تُظهر القاعدة 30 سلوك الفئة 3 ، مما يعني أن أنماط الإدخال البسيطة مثل تلك الموضحة تؤدي إلى تواريخ فوضوية وعشوائية على ما يبدو.

256 تكرارًا للقاعدة 110
قاعدة 110 للأتمتة الخلوية (الثنائي 01101110 = العشري 110)
النمط الحالي111110101100011010001٠٠٠
حالة جديدة للخلية المركزية01101110

تُظهر القاعدة 110، مثل لعبة الحياة، ما يُسميه وولفرام سلوك الفئة 4 ، وهو ليس عشوائيًا تمامًا ولا متكررًا تمامًا. تظهر هياكل موضعية وتتفاعل بطرق مختلفة تبدو معقدة. خلال تطوير كتاب "نوع جديد من العلوم" ، أثبت ماثيو كوك ، بصفته مساعدًا بحثيًا لوولفرام عام 1994، أن بعض هذه الهياكل غنية بما يكفي لدعم الشمولية . هذه النتيجة مثيرة للاهتمام لأن القاعدة 110 نظام أحادي البعد بسيط للغاية، ويصعب هندسته لأداء سلوك محدد. لذلك، تُقدم هذه النتيجة دعمًا كبيرًا لرأي وولفرام بأن أنظمة الفئة 4 من المرجح بطبيعتها أن تكون شاملة. قدم كوك برهانه في مؤتمر معهد سانتا فيه حول الأوتوماتا الخلوية عام 1998، لكن وولفرام منع إدراج البرهان في وقائع المؤتمر، لأنه لم يرغب في الإعلان عنه قبل نشر كتاب "نوع جديد من العلوم" . [ 57 ] في عام 2004، نُشر برهان كوك أخيرًا في مجلة وولفرام للأنظمة المعقدة (المجلد 15، العدد 1)، بعد أكثر من عشر سنوات من ابتكاره. وقد شكلت القاعدة 110 أساسًا لبعض أصغر آلات تورينج العالمية. [ 58 ]

مساحة القواعد

تُحدد قاعدة الأوتوماتا الخلوية الأولية بثمانية بتات، ويمكن اعتبار جميع قواعد الأوتوماتا الخلوية الأولية واقعة على رؤوس مكعب الوحدة ذي الأبعاد الثمانية . يُمثل مكعب الوحدة هذا فضاء قواعد الأوتوماتا الخلوية. أما بالنسبة لأوتوماتا الجار الأقرب التالي، فتُحدد القاعدة بـ 2 ^5  =  32 بتًا، ويكون فضاء قواعد الأوتوماتا الخلوية مكعب وحدة ذي أبعاد 32. يُمكن تعريف المسافة بين قاعدتين بعدد الخطوات اللازمة للانتقال من رأس يُمثل القاعدة الأولى إلى رأس آخر يُمثل القاعدة الثانية، على طول حافة مكعب الوحدة. تُسمى هذه المسافة بين القاعدتين أيضًا مسافة هامينغ .

يُتيح لنا فضاء قواعد الأوتوماتا الخلوية طرح سؤال حول ما إذا كانت القواعد ذات السلوك الديناميكي المتشابه "متقاربة" من بعضها البعض. ولا يزال رسم مكعب فائق الأبعاد على مستوى ثنائي الأبعاد مهمة صعبة، ويُعدّ عدد البتات 1 في سلسلة البتات الثمانية للقواعد الأولية (أو سلسلة البتات 32 لقواعد الجوار الثاني) أحد المؤشرات التقريبية لموقع القاعدة في المكعب الفائق. ويُظهر رسم القواعد في فئات وولفرام المختلفة في هذه الشرائح من فضاء القواعد أن قواعد الفئة 1 تميل إلى امتلاك عدد أقل من البتات 1، وبالتالي تقع في منطقة واحدة من الفضاء، بينما تميل قواعد الفئة 3 إلى امتلاك نسبة أعلى (50%) من البتات 1. [ 38 ]

بالنسبة لمساحة قواعد الأوتوماتون الخلوي الأكبر، تبين أن قواعد الفئة 4 تقع بين قواعد الفئة 1 وقواعد الفئة 3. [ 59 ] هذه الملاحظة هي أساس عبارة " حافة الفوضى" ، وهي تذكرنا بالانتقال الطوري في الديناميكا الحرارية .

التطبيقات

علم الأحياء

يُظهر نسيج المحار المخروطي نمطًا يشبه الأوتومات الخلوي على صدفته. [ 60 ]

يمكن محاكاة العديد من العمليات أو الظواهر البيولوجية باستخدام الأوتوماتا الخلوية، والتي تُعتبر نوعًا خاصًا من النماذج القائمة على العوامل في سياقات التطبيق هذه. [ 61 ] [ 62 ] في هذه المحاكاة البيولوجية، من الشائع اعتبار خلايا الأوتوماتا الخلوية خلايا بيولوجية. [ 63 ]

بعض الأمثلة على الظواهر البيولوجية التي يتم نمذجتها بواسطة الأوتوماتا الخلوية ذات فضاء الحالة البسيط هي:

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

كيمياء

يُعد تفاعل بيلوسوف -جابوتينسكي مذبذبًا كيميائيًا مكانيًا-زمانيًا يُمكن محاكاته باستخدام الأوتومات الخلوية. في خمسينيات القرن العشرين، اكتشف أ.م. جابوتينسكي (مُكملاً عمل ب.ب. بيلوسوف ) أنه عند خلط طبقة رقيقة متجانسة من خليط حمض المالونيك ، وبرومات مُحمّض، وملح السيريوم، وتركها دون تحريك، تنتشر أنماط هندسية رائعة، مثل الدوائر المُتحدة المركز واللوالب، عبر الوسط. في قسم "التسلية الحاسوبية" من عدد أغسطس 1988 من مجلة ساينتفك أمريكان ، [ 71 ] ناقش أ.ك. ديودني أوتوماتًا خلويًا [ 72 ] طوّره مارتن جيرهاردت وهايكه شوستر من جامعة بيليفيلد (ألمانيا). يُنتج هذا الأوتومات أنماطًا موجية تُشبه تلك الموجودة في تفاعل بيلوسوف-جابوتينسكي. بدمج الارتباط بجزيء واحد فقط من التجمع المتنامي، باتباع النموذج الأساسي لـ Witten و Sander [ 73 ] لمحاكاة النمو المحدود بالانتشار مع الارتباط بمواقع الانحناء كما اقترح Kossel و Stranski في عشرينيات القرن الماضي، انظر [ 74 ] للنسخة المحدودة بالحركية من الارتباط، اقترح Goranova et al. [ 75 ] نموذجًا للترسيب الكهروكيميائي المشترك لأيونين معدنيين.

الفيزياء

تمثيل مرئي لآلة غاز شبكية. تتناسب درجات اللون الرمادي للبكسلات الفردية مع كثافة جزيئات الغاز (بين 0 و4) عند ذلك البكسل. يحيط بالغاز غلاف من الخلايا السوداء التي تعمل كعاكسات لتكوين حيز مغلق.

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

من بين أنواع الأوتوماتا الخلوية الأخرى ذات الأهمية في الفيزياء، أوتوماتا الغاز الشبكي ، التي تحاكي تدفقات الموائع. في سلسلة من الدراسات [ 79 ] [ 80 ] [ 81 ] [ 82 ] ، تم اقتراح ما يُسمى بالأوتوماتا الخلوية المجاورة (vicCA) وتطويرها لاحقًا لنمذجة النمو غير المستقر المحتمل والتسامي لأسطح البلورات المجاورة في بُعدين (1+1D). بالإضافة إلى ترميز أحداث الارتباط/الانفصال في قواعد الأوتوماتا الخلوية، تُشكل الذرات الممتزة على سطح البلورة المجاورة طبقة رقيقة، ويتم نمذجة حركتها الحرارية بواسطة وحدة مونت كارلو. [ 79 ] [ 81 ] كانت الخطوة الحاسمة التالية هي تحويل النموذج إلى 2+1D، [ 83 ] حيث تم الحصول على عدد من الهياكل المختلفة، والتي أشار إليها المؤلفون باسم "الكائنات المجاورة" - حزم الخطوات، والتعرجات المتدرجة، والأعمدة النانوية، والأسلاك النانوية، وما إلى ذلك. [ 83 ] تم استخدام نموذج vicCA على نطاق واسع من قبل أليكسي ريدكوف [ 84 ] لتطوير خوارزمية تعلم آلي فوقه، مما أدى إلى تسريع الحسابات بشكل كبير بمعامل 105 مع تمكين التصنيف المنهجي للظواهر المرصودة.

علوم الحاسوب، البرمجة، والاتصالات

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

اقترحت القاعدة 30 في الأصل كخوارزمية تشفير محتملة للاستخدام في علم التشفير . يمكن استخدام الأوتوماتا الخلوية ثنائية الأبعاد لإنشاء مولد أرقام شبه عشوائية . [ 86 ] وقد طُرحت الأوتوماتا الخلوية لتشفير المفتاح العام . الدالة أحادية الاتجاه هي تطور أوتوماتا خلوية محدودة، ويُعتقد أن إيجاد معكوسها صعب. باستخدام هذه القاعدة، يمكن لأي شخص حساب الحالات المستقبلية بسهولة، ولكن يبدو من الصعب جدًا حساب الحالات السابقة. كما طُبقت الأوتوماتا الخلوية لتصميم رموز تصحيح الأخطاء . [ 87 ]

تشمل المشاكل الأخرى التي يمكن حلها باستخدام الأوتوماتا الخلوية ما يلي:

الفن والموسيقى التوليدية

استُخدمت الأوتوماتا الخلوية في الموسيقى التوليدية [ 88 ] وتأليف الموسيقى التطورية [ 89 ] وتوليد التضاريس الإجرائية في ألعاب الفيديو. [ 90 ]

توليد المتاهات

يمكن استخدام أنواع معينة من الأوتوماتا الخلوية لتوليد المتاهات. [ 91 ] من أشهر هذه الأوتوماتا الخلوية، Maze وMazectric، قواعدهما B3/S12345 وB3/S1234. [ 91 ] في الأولى، يعني هذا أن الخلايا تبقى على قيد الحياة من جيل إلى آخر إذا كان لديها جار واحد على الأقل وخمسة جيران على الأكثر . أما في الثانية، فيعني هذا أن الخلايا تبقى على قيد الحياة إذا كان لديها من جار واحد إلى أربعة جيران. إذا كان للخلية ثلاثة جيران بالضبط، فإنها تُولد. وهي تشبه لعبة الحياة لكونواي في أن الأنماط التي لا تحتوي على خلية حية مجاورة لخلية حية واحدة أو أربع أو خمس خلايا حية أخرى في أي جيل ستتصرف بشكل مطابق لها. [ 91 ] مع ذلك، بالنسبة للأنماط الكبيرة، فإنها تتصرف بشكل مختلف تمامًا عن لعبة الحياة. [ 91 ]

في حالة استخدام نمط بدء عشوائي، تتطور هذه الأوتوماتا الخلوية المولدة للمتاهات إلى متاهات معقدة ذات جدران محددة جيدًا تُشكل ممرات. تميل متاهة Mazetric، التي تستخدم القاعدة B3/S1234، إلى توليد ممرات أطول وأكثر استقامة مقارنةً بمتاهة Maze، التي تستخدم القاعدة B3/S12345. [ 91 ] نظرًا لأن قواعد الأوتوماتا الخلوية هذه حتمية ، فإن كل متاهة يتم توليدها تتحدد بشكل فريد من خلال نمط البدء العشوائي الخاص بها. يُعد هذا عيبًا كبيرًا لأن المتاهات تميل إلى أن تكون قابلة للتنبؤ نسبيًا.

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

قواعد محددة

تتضمن قواعد الأتمتة الخلوية المحددة ما يلي:

انظر أيضاً

مراجع

  1. ↑ دانيال دينيت (1995)، فكرة داروين الخطيرة ، دار بنجوين للنشر، لندن، رقم ISBN 978-0-14-016734-4، ISBN 0-14-016734-X
  2. 1 2 وولفرام، ستيفن (1983). "الميكانيكا الإحصائية للأوتوماتا الخلوية" . مراجعات الفيزياء الحديثة . 55 (3): 601-644 . Bibcode : 1983RvMP...55..601W . doi : 10.1103/RevModPhys.55.601 . مؤرشف من الأصل في 21 سبتمبر 2013. تم الاسترجاع في 28 فبراير 2011 .
  3. ↑ توفولي، توماسو؛ مارغولوس، نورمان (1987). آلات الأوتوماتا الخلوية: بيئة جديدة للنمذجة . مطبعة معهد ماساتشوستس للتكنولوجيا. ص 27. ISBN  978-0-262-20060-8.
  4. ↑ شيف، جويل ل. (2011). الأوتوماتا الخلوية: نظرة منفصلة للعالم . وايلي وأولاده، ص 40. ISBN  978-1-118-03063-9.
  5. 1 2 3 4 كير، سيبولد، تشينغ 2005 ، ص 15 
  6. 1 2 بيالينيكي-بيرولا، بيالينيكا-بيرولا 2004 ، ص. 9 
  7. ↑ شيف 2011 ، ص 41 
  8. ↑ بيكوفر، كليفورد أ . (2009). كتاب الرياضيات: من فيثاغورس إلى البعد السابع والخمسين، 250 معلمًا بارزًا في تاريخ الرياضيات . شركة ستيرلينغ للنشر، ص 406. ISBN  978-1-4027-5796-9.
  9. 1 2 شيف 2011 ، ص. 1 
  10. ↑ جون فون نيومان، "النظرية العامة والمنطقية للآلات"، في إل إيه جيفريس ، محرر، الآليات الدماغية في السلوك - ندوة هيكسون، جون وايلي وأولاده، نيويورك، 1951، ص 1-31.
  11. ↑ كيميني، جون ج. (1955). "الإنسان يُنظر إليه كآلة". مجلة ساينتفك أمريكان ، 192 (4): 58-67 . رمز Bibcode : 1955SciAm.192d..58K . doi : 10.1038/scientificamerican0455-58 .; الخيال العلمي. أكون. 1955؛ 192:6 (أخطاء).
  12. ↑ شيف 2011 ، ص 3 
  13. ↑ إيلاتشينسكي 2001 ، ص. 29 
  14. ↑ بيالينيكي-بيرولا، بيالينيكا-بيرولا 2004 ، ص 8 
  15. 1 2 وولفرام 2002 ، ص 876 
  16. ↑ فون نيومان 1966
  17. 1 2 وينر، ن.؛ روزنبلويث، أ. (1946). "الصياغة الرياضية لمسألة توصيل النبضات في شبكة من العناصر القابلة للاستثارة المتصلة، وتحديدًا في عضلة القلب". أرشيف معهد أمراض القلب في المكسيك . 16 (3): 205-265 . PMID 20245817 . 
  18. ↑ ليتيشيفسكي، أ.أ.؛ ريشودكو، ل.ف. (1974). "نظرية ن. وينر حول نشاط الوسائط القابلة للاستثارة". علم التحكم الآلي . 8 (5): 856-864 . doi : 10.1007/bf01068458 . S2CID 121306408 . 
  19. ↑ دافيدنكو، ج.م.؛ بيرتسوف، أ.ف.؛ سالومونز، ر.؛ باكستر، و.؛ جليفة، ج. (1992). "موجات إثارة حلزونية ثابتة ومنجرفة في عضلة القلب المعزولة". مجلة نيتشر . 355 (6358): 349-351 . Bibcode : 1992Natur.355..349D . doi : 10.1038/355349a0 . PMID 1731248. S2CID 4348759 .  
  20. ↑ هيدلوند، جي إيه (1969). "التشاكلات الداخلية والتشاكلات الذاتية لنظام الإزاحة الديناميكي". نظرية الأنظمة الرياضية . 3 (4): 320-3751 . doi : 10.1007/BF01691062 . S2CID 21803927 . 
  21. ↑ شيف 2011 ، ص 182 
  22. ↑ سميث، ألفي راي. "مفاضلات تعقيد الأوتوماتا الخلوية" (ملف PDF) . مؤرشف (ملف PDF) من الأصل في 27 سبتمبر 2015. تم الاطلاع عليه في 11 فبراير 2018 .
  23. ↑ سميث، ألفي راي. "الحوسبة البسيطة - الفضاءات الخلوية الشاملة" (ملف PDF) . مؤرشف (ملف PDF) من الأصل في 14 يونيو 2018. تم الاطلاع عليه في 11 فبراير 2018 .
  24. ↑ سميث، ألفي راي. "آلات بسيطة غير تافهة ذاتية التكاثر" (ملف PDF) . مؤرشف (ملف PDF) من الأصل في 27 سبتمبر 2015. تم الاطلاع عليه في 11 فبراير 2018 .
  25. ↑ سميث، ألفي راي. "مقدمة ومسح لنظرية الأوتوماتا الخلوية أو الأوتوماتا المتعددة" (ملف PDF) . مؤرشف (ملف PDF) من الأصل في 7 أغسطس 2015. تم الاطلاع عليه في 11 فبراير 2018 .
  26. ↑ غاردنر، مارتن (1970). "الألعاب الرياضية: التوليفات الرائعة للعبة سوليتير الجديدة "الحياة" لجون كونواي"" . مجلة ساينتفك أمريكان . 223 (4): 120–123 . doi : 10.1038/scientificamerican1070-120 . مؤرشف من الأصل بتاريخ 27 أغسطس 2013. تم الاطلاع عليه بتاريخ 24 أغسطس 2011. "
  27. ↑ بول تشابمان. حاسوب الحياة الشامل. http://www.igblan.free-online.co.uk/igblan/ca/ مؤرشف في 6 سبتمبر 2009 في أرشيف الإنترنت (Wayback Machine) نوفمبر 2002
  28. ↑ واينرايت 2010 ، ص 16 
  29. 1 2 3 4 5 وولفرام 2002 ، ص 880 
  30. ↑ وولفرام 2002 ، ص 881 
  31. ↑ ميتشل، ميلاني (4 أكتوبر 2002). "هل الكون حاسوب كوني؟". مجلة ساينس . 298 (5591): 65-68 . doi : 10.1126/science.1075073 . S2CID 122484855 . 
  32. 1 2 3 إيلاتشينسكي 2001 ، ص 12 
  33. ↑ إيلاتشينسكي 2001 ، ص 13 
  34. ↑ وولفرام 2002 ، ص 231 
  35. ^ ج. كاتانيو. إي. فورمينتي؛ إل مارجارا (1998). “الفوضى الطوبولوجية و CA” . في م.ديلورم؛ جيه مازوير (محرران). الأتمتة الخلوية: نموذج موازي . سبرينغر. ص. 239. ردمك  978-0-7923-5493-2.
  36. ↑ بيرتون هـ. فوريس (1996). التحليل الحسابي للأتمتة الخلوية أحادية البعد . وورلد ساينتيفيك. ص 8. ISBN  978-981-02-2221-5.
  37. ↑ ماكس غارزون ( 1995). نماذج التوازي الهائل: تحليل الأوتوماتا الخلوية والشبكات العصبية . سبرينغر. ص 149. ISBN  978-3-540-56149-1.
  38. 1 2 لي، وينتيان ؛ باكارد، نورمان (1990). "بنية فضاء قواعد الأوتوماتا الخلوية الأولية" (ملف PDF) . الأنظمة المعقدة . 4 : 281-297 . مؤرشف (ملف PDF) من الأصل في 25 يونيو 2016. تم الاسترجاع في 25 يناير 2013 .
  39. ↑ نيكوليس (1974). " البنى التبديدية، والكوارث، وتكوين الأنماط: تحليل التشعب" (ملف PDF) . وقائع الأكاديمية الوطنية للعلوم . 71 (7): 2748-2751 . رمز Bibcode : 1974PNAS...71.2748N . doi : 10.1073/pnas.71.7.2748 . PMC 388547. PMID 16592170. مؤرشف (ملف PDF) من الأصل في 25 يونيو 2016. تم الاطلاع عليه في 25 مارس 2017 .  
  40. 1 2 كاري، جاركو 1991 ، ص. 379 
  41. ↑ ريتشاردسون، د. (1972). "التبليط باستخدام التحويلات المحلية" . مجلة علوم الحاسوب والأنظمة . 6 (5): 373-388 . doi : 10.1016/S0022-0000(72)80009-6 .
  42. ↑ مارجنسترن، موريس (2007). الأوتوماتا الخلوية في الفضاءات الزائدية - المجلد الأول، الجزء الأول . أرشيفات معاصرة. ص 134. ISBN  978-2-84703-033-4.
  43. ↑ شيف 2011 ، ص 103 
  44. ↑ أموروسو، سيرافينو؛ بات، ييل ن. (1972). "إجراءات اتخاذ القرار بشأن الشمولية والحقنية للخرائط المتوازية لهياكل التبليط" . مجلة علوم الحاسوب والأنظمة . 6 (5): 448-464 . doi : 10.1016/s0022-0000(72)80013-8 .
  45. ↑ سوتنر، كلاوس (1991). "مخططات دي بروين والأتمتة الخلوية الخطية" (ملف PDF) . الأنظمة المعقدة . 5 : 19-30 . مؤرشف (ملف PDF) من الأصل في 14 مايو 2011. تم الاطلاع عليه في 7 فبراير 2011 .
  46. ↑ كاري، جاركو (1990). "انعكاسية الأوتوماتا الخلوية ثنائية الأبعاد غير قابلة للتقرير". فيزيكا د . 45 ( 1-3 ): 379-385 . Bibcode : 1990PhyD...45..379K . doi : 10.1016/0167-2789(90)90195-U .
  47. ↑ كاري، جاركو (1999). "حول عمق الدائرة في الأوتوماتا الخلوية القابلة للعكس هيكليًا". Fundamenta Informaticae . 38 : 93-107 . doi : 10.3233/FI-1999-381208 .
  48. ↑ دوراند-لوز، جيروم (2001). "تمثيل الأوتوماتا الخلوية العكسية باستخدام الأوتوماتا الخلوية الكتلية العكسية" . الرياضيات المتقطعة وعلوم الحاسوب النظرية . AA : 145-154 . مؤرشف من الأصل في 15 مايو 2011.
  49. ↑ وولفرام 2002 ، ص 60 
  50. 1 2 إيلاتشينسكي، أندرو (2001). الأوتوماتا الخلوية: عالم منفصل . وورلد ساينتيفيك. ص 44-45 . ISBN  978-981-238-183-5.
  51. ↑ يعودمصطلح " الأتمتة الخلوية الشبيهة بالحياة " إلى بارال، وشاتيه ، ومانفيل (1992) على الأقل ، حيث استخدموه بمعنى أوسع للإشارة إلى الأتمتة الكلية الخارجية، وليس بالضرورة ثنائية الأبعاد. وقد استُخدم المعنى الأكثر تحديدًا الوارد هنا، على سبيل المثال، في عدة فصول من كتاب أداماتزكي (2010) . انظر: بارال، برنارد؛ شاتيه، هيوز؛ مانفيل، بول (1992). "السلوكيات الجماعية في عائلة من الأتمتة الخلوية عالية الأبعاد". رسائل الفيزياء أ . 163 (4): 279-285 . Bibcode : 1992PhLA..163..279B . doi : 10.1016/0375-9601(92)91013-H .
  52. ^ ابستين 2010 ، ص 72-73 
  53. ↑ جاكوب آرون. "أولى الطائرات الشراعية تتنقل في كون بنروز المتغير باستمرار" . مجلة نيو ساينتست .
  54. ↑ موراي، جيه دي (2003). البيولوجيا الرياضية ( الطبعة الثالثة). نيويورك: سبرينغر. ISBN  0-387-95228-4.
  55. ↑ بيفاتو، م: "الحياة الواقعية: الحد المتصل للأتمتة الخلوية الأكبر من الحياة"، علوم الحاسوب النظرية ، 372 (1)، مارس 2007، ص 46-68
  56. ↑ توميتا، كوهجي؛ كوروكاوا، هاروهيسا؛ موراتا، ساتوشي (2009). "أتمتة إعادة كتابة الرسوم البيانية كامتداد طبيعي للأتمتة الخلوية". الشبكات التكيفية . فهم الأنظمة المعقدة. ص 291-309 . doi : 10.1007/978-3-642-01284-6_14 . ISBN  978-3-642-01283-9.
  57. ↑ جايلز، جيم (2002). "أي نوع من العلوم هذا؟" . مجلة نيتشر . 417 (6886): 216-218 . Bibcode : 2002Natur.417..216G . doi : 10.1038/417216a . PMID 12015565. S2CID 10636328 .  
  58. ↑ واينبرغ، ستيفن (24 أكتوبر 2002). "هل الكون حاسوب؟" . مجلة نيويورك ريفيو أوف بوكس . 49 (16) . تم الاطلاع عليه بتاريخ 12 أكتوبر 2012 .
  59. ↑ وينتيان لي؛ نورمان باكارد؛ كريس جي لانغتون (1990). "ظواهر الانتقال في فضاء قواعد الأوتوماتا الخلوية". فيزيكا د . 45 ( 1-3 ): 77-94 . Bibcode : 1990PhyD...45...77L . CiteSeerX 10.1.1.15.2786 . doi : 10.1016/0167-2789(90)90175-O . 
  60. 1 2 3 كومبس، ستيفن (15 فبراير 2009)، هندسة وتصبغ الأصداف البحرية (ملف PDF) ، الصفحات 3-4 ، مؤرشف من الأصل (ملف PDF) في 7 يناير 2013 ، تم استرجاعه في 2 سبتمبر 2012 
  61. ^ كويفاس، إريك. أفيلا، كارلا؛ إيسلاس توسكي، ميغيل؛ إسكوبار، هيكتور (2025). النماذج المستندة إلى الوكيل باستخدام MATLAB . مورجان كوفمان. ص. 105. ردمك  9780443240058.
  62. ^ بيرتو، فرانشيسكو. تاغليابو، جاكوبو (2023). "الأتمتة الخلوية" . موسوعة ستانفورد للفلسفة . مطبعة جامعة ستانفورد.
  63. ↑ جراو، فريدريك؛ بيرلسون، آلان س. (سبتمبر 2012). "الجوانب المكانية لعدوى فيروس نقص المناعة البشرية". في: ليدزويتش، أورسولا؛ شاتلر، هاينز؛ فريدمان، أفنر؛ كاشدان، يوجين (محررون). الأساليب والنماذج الرياضية في الطب الحيوي . سبرينغر نيويورك. ص 3-31 . doi : 10.1007/978-1-4614-4178-6_1 . ISBN  9781461441786.
  64. ↑ بيك، ويست؛ ميسينجر، موت (2004). "أدلة على ديناميكيات جماعية معقدة وحوسبة موزعة ناشئة في النباتات" . وقائع الأكاديمية الوطنية للعلوم . 101 (4): 918-922 . Bibcode : 2004PNAS..101..918P . doi : 10.1073/pnas.0307811100 . PMC 327117. PMID 14732685 .  
  65. ↑ "نسخة مؤرشفة" (PDF) . مؤرشفة من الأصل (PDF) بتاريخ 25 يوليو 2010. تم الاطلاع عليها بتاريخ 14 سبتمبر 2008 .{{cite web}}: CS1 maint: archived copy as title ( link )
  66. ↑ إيلاتشينسكي 2001 ، ص 275 
  67. ↑ إيف بوليغاند (1986). "الخلايا الليفية، وتكوين الشكل، والأتمتة الخلوية". الأنظمة المضطربة والتنظيم البيولوجي . ص 374-375 . 
  68. ↑ إيلينا، أولغا؛ غريتسينكو، بافلو ج.؛ سيغا، سيمون؛ ليبولد، يورغن؛ لا بورتا، كاترينا أ.م.؛ تشيبيزكو، أولكسندر؛ غروسر، ستيفن؛ فولينغز، مانون؛ باكر، غيرت-يان؛ ستاروس، يورن؛ بولت، بيتر (سبتمبر 2020). "التصاق الخلايا ببعضها البعض وحصر المصفوفة ثلاثية الأبعاد يحددان انتقالات التكدس في غزو سرطان الثدي" . مجلة نيتشر لبيولوجيا الخلية . 22 (9): 1103-1115 . doi : 10.1038/s41556-020-0552-6 . ISSN 1465-7392 . PMC 7502685. PMID 32839548 .   
  69. ↑ ريهر، ديفيد؛ كلينك، باربرا؛ دويتش، أندرياس؛ فوس-بوم، أنيا (11 أغسطس 2017). "عدم تجانس التصاق الخلايا يعزز انتشار الخلايا السرطانية: رؤى جديدة من نموذج رياضي" . بيولوجي دايركت . 12 (1): 18. doi : 10.1186/s13062-017-0188-z . ISSN 1745-6150 . PMC 5553611. PMID 28800767 .   
  70. ^ هاتزيكيرو، هـ؛ باسانتا، د.؛ سيمون، م. شالر، ك. دويتش ، أ. (1 مارس 2012). ""النمو أو التوسع "هل هو مفتاح ظهور الغزو في تطور الأورام؟ الطب الرياضي وعلم الأحياء . 29 (1): 49-65 . doi : 10.1093/imammb/dqq011 . ISSN 1477-8599 . PMID 20610469. مؤرشف من الأصل في 18 أكتوبر 2021. تم الاطلاع عليه في 21 يوليو 2021 .  
  71. ↑ AK Dewdney، آلة الهودجبودج تُحدث ضجة، مجلة ساينتفك أمريكان، ص 104، أغسطس 1988.
  72. ↑ جيرهاردت، م.؛ شوستر، هـ. (1989). "أوتوماتون خلوي يصف تكوين البنى المرتبة مكانيًا في الأنظمة الكيميائية". فيزيكا د . 36 (3): 209-221 . Bibcode : 1989PhyD...36..209G . doi : 10.1016/0167-2789(89)90081-x .
  73. ↑ ويتن، تي. أ.؛ ساندر، إل. إم. (9 نوفمبر 1981). "التجمع المحدود بالانتشار، ظاهرة حرجة حركية" . رسائل المراجعة الفيزيائية . 47 (19): 1400-1403 . رمز Bibcode : 1981PhRvL..47.1400W . doi : 10.1103/PhysRevLett.47.1400 . مؤرشف من الأصل في 26 نوفمبر 2024. تم الاسترجاع في 3 فبراير 2025 .
  74. ↑ وودروف، د.ب. (13 أبريل 2015). "كيف تنمو بلورتك؟ تعليق على كتاب بيرتون، كابريرا وفرانك (1951) "نمو البلورات وبنية التوازن لأسطحها"" . المعاملات الفلسفية للجمعية الملكية أ: العلوم الرياضية والفيزيائية والهندسية . 373 (2039) 20140230. Bibcode : 2015RSPTA.37340230W . doi : 10.1098/rsta.2014.0230 . PMC 4360084 . PMID 25750141 .  
  75. ↑ غورانوفا، د.؛ راشكوف، ر.؛ أفدييف، ج.؛ تونشيف، ف. (1 سبتمبر 2016). "الترسيب الكهربائي لسبائك النيكل والنحاس عند كثافات تيار عالية: تفاصيل توزيع العناصر" . مجلة علوم المواد . 51 (18): 8663-8673 . Bibcode : 2016JMatS..51.8663G . doi : 10.1007/s10853-016-0126-y . ISSN 1573-4803 . 
  76. ↑ سيثنا، جيمس ب. (2008). الميكانيكا الإحصائية: الإنتروبيا، ومعاملات الترتيب، والتعقيد . مطبعة جامعة أكسفورد . ISBN 978-0-198-56677-9OCLC 845714772. مؤرشف من الأصل في 7 يونيو 2021. تم الاطلاع عليه في 19 أغسطس 2025 . 
  77. ↑ كاردار، مهران (2007). الفيزياء الإحصائية للحقول . مطبعة جامعة كامبريدج . ISBN 978-0-521-87341-3. OCLC 920137477 . 
  78. ↑ كابيلي، أندريا؛ زوبر، جان برنارد (2010). "تصنيف ADE لنظريات الحقول المطابقة" . Scholarpedia . 5 (4) 10314. arXiv : 0911.3242 . Bibcode : 2010SchpJ...510314C . doi : 10.4249/scholarpedia.10314 . S2CID 18207779 . 
  79. 1 2 ف. كرزيفسكي، م. زالوسكا-كوتور، أ. كراستيفا، هـ. بوبوفا، و ف. تونشيف، "تكتل الخطوات وتكوين الخطوات الكبيرة في نموذج أحادي البعد على المستوى الذري لنمو البلورات المجاورة غير المستقرة"، مجلة نمو البلورات 474 ، 135 (2017). DOI
  80. ↑ O. Toktarbaiuly et al., “Step clustering with both direction of the current: Vicinal W(110) surface versus atomistic-scale model,” Phys. Rev. B 97 , 035436 (2018). DOI
  81. 1 2 ف. كرزيفسكي، م. زالوسكا-كوتور، أ. كراستيفا، هـ. بوبوفا، و ف. تونشيف، "قياس واستقرار ديناميكي للأسطح المجاورة النموذجية"، نمو البلورات وتصميمها 19 ، 821 (2019). DOI
  82. ↑ هـ. بوبوفا، ف. كرزيفسكي، م. أ. زالوسكا-كوتور، و ف. تونشيف، "قياس تأثير استبعاد الخطوات على الأسطح المجاورة غير المستقرة ديناميكيًا: تجميع الخطوات دون تكوين خطوات كبيرة"، نمو البلورات وتصميمها 20 ، 7246 (2020). DOI
  83. 1 2 M. Załuska-Kotur، H. Popova، and V. Tonchev، "العناقيد المتدرجة والأسلاك النانوية وغيرها من" المخلوقات "المجاورة - تأثير Ehrlich – Schwoebel بواسطة الأوتوماتا الخلوية،" بلورات 11 ، 1135 (2021). DOI
  84. ^ إيه في ريدكوف، “علم بيانات التبلور في السيليكو،” Acta Materialia 287 ، 120762 (2025). DOI
  85. ↑ محتار أوغلو، علي (أغسطس 1996). "4.1 معالج الأوتوماتا الخلوية (CAP)". أنظمة قائمة على معالج الأوتوماتا الخلوية لمقارنة التسلسل الجيني/البحث في قواعد البيانات . جامعة كورنيل. ص 62-74 . 
  86. ↑ توماسيني، م.؛ سيبر، م.؛ بيرينود، م. (2000). "حول توليد أرقام عشوائية عالية الجودة باستخدام الأوتوماتا الخلوية ثنائية الأبعاد" . معاملات IEEE في الحوسبة . 49 (10): 1146-1151 . Bibcode : 2000ITCmp..49.1146T . doi : 10.1109/12.888056 . S2CID 10139169. مؤرشف من الأصل في 24 يونيو 2021. تم الاسترجاع في 17 يونيو 2025 . 
  87. ↑ تشودري، د. روي؛ باسو، س.؛ غوبتا، إ. سين؛ تشودري، ب. بال (يونيو 1994). "تصميم CAECC - رمز تصحيح الأخطاء القائم على الأوتوماتا الخلوية". معاملات IEEE للحاسبات . 43 (6): 759-764 . Bibcode : 1994ITCmp..43..759C . doi : 10.1109/12.286310 .
  88. ↑ بوراستون، ديف، وإرنست إدموندز. " الأتمتة الخلوية في الموسيقى الإلكترونية التوليدية والفن الصوتي: مراجعة تاريخية وتقنية. مؤرشف في 25 نوفمبر 2020 في Wayback Machine ." الإبداع الرقمي 16.3 (2005): 165-185.
  89. ↑ ميراندا، إدواردو ريك. " تطوير موسيقى الأوتوماتا الخلوية: من توليف الصوت إلى التأليف الموسيقي ". وقائع ورشة عمل 2001 حول نماذج الحياة الاصطناعية للتطبيقات الموسيقية. 2001.
  90. ↑ أشلوك، دانيال؛ كريتزر، ماثيو (2020). "تطوير خرائط مستوى متنوعة قائمة على الأتمتة الخلوية" . وقائع المؤتمر الدولي السادس في هندسة البرمجيات لتطبيقات الدفاع . التقدم في الأنظمة الذكية والحوسبة. المجلد 925. الصفحات 10-23 . doi : 10.1007/978-3-030-14687-0_2 . ISBN   978-3-030-14686-3S2CID 85562837. مؤرشف من الأصل بتاريخ 8 أبريل 2022. تم الاطلاع عليه بتاريخ 7 يونيو 2021 . 
  91. 1 2 3 4 5 ناثانيال جونستون؛ وآخرون . (21 أغسطس 2010). "المتاهة" . لايف ويكي . تم الاسترجاع 22 أبريل 2025 . 

المراجع

للمزيد من القراءة