নিয়ম ১৮৪
নিয়ম ১৮৪ হল একটি দ্বি-মাত্রিক বাইনারি সেলুলার অটোমেটন নিয়ম, যার মেজরিটি প্রবলেম সমাধানের পাশাপাশি আপাতদৃষ্টিতে বেশ ভিন্ন পারটিকেল সিস্টেমের একাধিক বর্ণনা করার ক্ষমতা উল্লেখযোগ্যঃ
- মহাসড়কের একটি লেনে যানবাহনের প্রবাহ মাপার জন্য সাধারণ কোন মডেল তৈরি করতে নিয়ম ১৮৪ ব্যবহার করা যেতে পারে, এবং এটি সেলুলার অটোমেটন মডেলের দ্বারা যানবাহনের প্রবাহ মাপার জন্য ভিত্তি তৈরি করে দিতে পারে। এই মডেলে, কণাগুলো (যানবাহনগুলি প্রতিনিধিত্ব করে) তাদের সামনে গাড়িগুলির উপর নির্ভর করে একক দিকের দিকে অগ্রসর হয় এবং বন্ধ হয়ে যায়। কণিকার সংখ্যা সিমুলেশন জুড়ে অপরিবর্তিত থাকে। এই প্রয়োগের কারণে, নিয়ম ১৮৪ কে "ট্র্যাফিক নিয়ম" বলা হয়। [১]
- নিয়ম ১৮৪ একটি অনিয়মিত তলে কণাগুলির বণ্টনের একটি মডেল তৈরি করে, যেখানে প্রতিটি স্থানীয় সর্বনিম্ন তল প্রতিটি ধাপে একটি কণা দিয়ে পূর্ণ থাকে। সিমুলেশনের প্রতিটি ধাপে, কণা সংখ্যা বৃদ্ধি হয়। একবার যদি কোন কণা স্থাপিত হলে, ওই কণাটি আর স্থির হয়ে যাবে।
- নিয়ম ১৮৪ বালিস্টিক শক্তিসংবহন বুঝতে পারে, এটি একটি কণা প্রবাহ ব্যবস্থা যা একটি এক-মাত্রিক মাধ্যমের মাধ্যমে কনাকে বাম এবং ডান উভয় দিকে চলতে সাহায্য করে। যখন দুটি কণার সংঘর্ষ হয়, তখন তারা একে অপরকে ধ্বংস করে, যাতে প্রতিটি পদক্ষেপে কণার সংখ্যা অপরিবর্তিত থাকে বা হ্রাস পায়।
এই বর্ণনাগুলির মধ্যে আপাত অসঙ্গতিটি হল কণাগুলির সাথে অটোমেটন এর বৈশিষ্ট্যগুলির সংযুক্তি, যার সমাধান বিভিন্ন উপায়ে সমাধান করা হয়।
নিয়ম ১৮৪ টি একটি উলফারম কোড যা তার নিজের ক্রমবিকাশের অবস্থা করে। নিয়ম ১৮৪-এর প্রথম গবেষণাটি লি (১৯৮৭) এবং কারগ ও স্পোনের (১৯৮৮)। বিশেষত, ক্রিগ এবং স্পোন ইতোমধ্যে নিয়ম ১৮৪ এর ৩টি কণা পদ্ধতির বর্ণনা করেছেন। [২]
সংজ্ঞা[সম্পাদনা]
নিয়ম ১৮৪ এর ব্যাখ্যায় বলা হয়, অটোমেটনটি একটি এক-মাত্রিক কোষের বিন্যাস, যার প্রতিটি কোষ বাইনারি মান (০ বা ১) ধারণ করে। তার বিবর্তন প্রক্রিয়ার প্রতিটি ধাপে, নিয়ম ১৮৪ অটোমেটনের প্রত্যেকটি কোষের বিন্যাসে নিম্নলিখিত নিয়মগুলো প্রয়োগ করা হয়, নতুন কোষের অবস্থান নির্ধারণ করতে, একসাথে সবকয়টি কোষে এটি প্রয়োগ করা হয়ঃ [৩]
বর্তমান নমুনা | ১১১ | ১১০ | ১০১ | ১০০ | ০১১ | ০১০ | ০০১ | ০০০ |
---|---|---|---|---|---|---|---|---|
মূল কোষের নতুন অবস্থা | ১ | ০ | ১ | ১ | ১ | ০ | ০ | ০ |
এই টেবিলের প্রতিটি মান প্রতিটি কোষের নতুন অবস্থাকে আগের অবস্থার ফাংশন হিসেবে এবং উভয় পাশে প্রতিবেশী কোষ পূর্ববর্তী মানকে সংজ্ঞায়িত করে। এই নিয়মটির নাম, নিয়ম ১৮৪, এটি একটি উলফার্ম কোড, যা উপরে উল্লিখিত টেবিলের অবস্থা বর্ণনা করেঃ টেবিলের নিচের সারীতে ১০১১১০০০, একে যদি আমরা বাইনারি সংখ্যা হিসেবে দেখি তবে এর ডেসিম্যাল মান হল ১৮৪।[৪]
নিয়ম 184 এর জন্য সেট নিয়ম ছাড়াও এটি স্বতন্ত্রভাবে বিভিন্ন উপায়ে বর্ণিত হতে পারে,
- প্রতিটি ধাপে, যখন ১, ০ কে অনুসরণ করে তখন তারা নিজেদের মধ্যে জায়গা অদলবদল করে। এই ব্যাখ্যার ভিত্তিতে, কারগ ও স্পোনের (১৯৮৮), এটিকে "ভারসাম্যহীন ঘূর্ণয়ণ-বিনিময় গতিবিদ্যার গতি সম্পর্কিত আইসিং মডেলের" একটি নিয়ন্ত্রক সংস্করণ বলে বর্ণনা করেন।
- প্রতিটি ধাপে, যদি কোন কোষের মান ১ থাকে ও তার দান পাশের কোন কোষের মান যদি ০ হয় তবে ১ ওই ০ কে পিচজনে রেখে ডানপাশে সরে যাবে। ১ এবং তার পাশে যদি ১ থাকে তবে তাদের কোন পরিবর্তন হবে না, যেখানে ০ এর পাশে যদি কোন ১ না থাকে সেও ০ রয়ে যাবে। এই বর্ণনাটি যানবাহনের প্রবাহ মাপার মডেলের জন্য সবচেয়ে উপযুক্ত।[৫]
- যদি কোন কোষ ০ অবস্থায় থাকে, তার নতুন অবস্থা তার বাম পাশে কি আছে তার উপর নির্ভর করবে। অন্যথায় তার নতুন অবস্থাটি তার ডান পাশের কোষের উপর নির্ভর করবে। তার মানে প্রত্যেকটি কোষ একটি মাল্টিপ্লেক্সারের সাহায্যে পূর্ণ করা যেতে পারে এবং এটি ফ্রেডকিন গেটের সাথে ঘনিষ্ঠ ভাবে সম্পর্কিত।[৬]
গতিবিদ্যা ও মেজরিটি শ্রেণিবিভাগ[সম্পাদনা]
উপরের বর্ণনা থেকে, গতিবিদ্যার দুটি গুরুত্বপূর্ণ উপাদান সম্পর্কে ধারণা পাওয়া যায়। প্রথমত, নিয়ম ১৮৪ এ, পর্যায়ক্রমিক বাউন্ডারি কন্ডিশনের মধ্যে যেকোনো গণনাযোগ্য কোষের সেটের 1s এর সংখ্যা এবং একটি প্যাটার্নে 0s এর এর সংখ্যা প্যাটার্ন ইভলুশনের সময় অপরিবর্তনীয় থাকে। নিয়ম ১৮৪ এবং এর প্রতিফলনগুলো একমাত্র এলিমেন্ট্রি সেলুলার এটমাটা যার মাঝে সংখ্যা সংরক্ষণের উপাদানগুলো বিদ্যমান। [৭] একইভাবে, যদি কোষের অসীম বিন্যাসে 1s ভালভাবে সংজ্ঞায়িত করা হয়, তবে এটি একই থাকে যেমন অটোমাটাতে ছিল। [৮] যদিও নিয়ম ১৮৪ বাম-ডান পরিবর্তনের ক্ষেত্রে প্রতিসম নয়, এটার অন্য একটি প্রতিসমতা আছে, বামদিকে এবং ডানদিকে বিপরীত দিকে এবং একই সময়ে ০ এবং ১ টি চিহ্নের ভূমিকা অপ্রতুলতা একই আপডেট নিয়মের সাথে একটি সেলুলার অটোমেটোন তৈরি করে।
নিয়ম ১৮৪ এর প্যাটার্নগুলো সাধারণত দ্রুত, স্ট্যাবিলাইজ বা স্থির করা হয়, এটি এমন একটি প্যাটার্নে চলে যেখানে কোষের স্টেটস লকস্টেপ্টে প্রতিটি ধাপে, হয় বামদিকে অবস্থান করে অথবা প্রতিটি ধাপে ডানদিকে একটি প্যানেলে সরানো হয়। যদি ১ অবস্থার কোষের ঘনত্ব ৫০% এর কম হয়, তবে ১ অবস্থায় কোষগুলো গুচ্ছ কোষে পরিনিত হয়। দুটি পৃথক ভাগ তৈরি হয়, যেখান ০ অবস্থাকে কিছু কোষ দিয়ে আলাদা করে রাখা হয়। এই ধরনের প্যাটার্নগুলো ডানদিকে অবস্থান করে। যদি অপরদিকের কোষগুলোর ঘনত্ব ৫০% এর বেশি হয়, বে তবে ০ অবস্থায় কোষগুলো গুচ্ছ কোষে পরিনিত হয়। দুটি পৃথক ভাগ তৈরি হয়, যেখান ১ অবস্থাকে কিছু কোষ দিয়ে আলাদা করে রাখা হয় এবং এই ধরনের প্যাটার্নগুলো বামদিকে অবস্থান করে। যদি ঘনত্ব একদম ৫০% হয় তবে তবে প্যাটার্নগুলো প্রতিধাপে হয় ডানদিকে চলে না হয় বামদিকে চলে এবং আস্তে আস্তে স্থির হয়ে যায়ঃ এটি 1s ও 0s এর জন্য পর্যায়ক্রমিক ধাপ।[৯]
মেজরিটি প্রবলেম হল একটি সেলুলার অটোমেটোন নির্মাণের সমস্যা, যা যখন কোনও গণনাযোগ্য কোষের সেটের উপর চালানো হয়, তখন তা বেশিরভাগ কোষগুলির মান গণনা করতে পারে। এক কথায়, নিয়ম ১৮৪ এই সমস্যার সমাধান করতে পারে। যদি নিয়ম ১৮৪ কোন পর্যায়ক্রমিক বাউন্ডারি কন্ডিশনের সাথে চালনা করা হয় এবং 1s ও 0s অসম সংখ্যার সাথে
যানবাহনের প্রবাহ[সম্পাদনা]
পৃষ্ঠতলের পদচ্যুতি[সম্পাদনা]
আন্তঃমহাদেশীয় শক্তিবিলয়ন[সম্পাদনা]
পদপরিচয়হীন প্রসঙ্গ[সম্পাদনা]
আরও দেখুন[সম্পাদনা]
টীকা[সম্পাদনা]
- ↑ E.g. see Fukś (1997).
- ↑ One can find many later papers that, when mentioning Rule 184, cite the early papers of Stephen Wolfram. However, Wolfram's papers consider only automata that are symmetric under left-right reversal, and therefore do not describe Rule 184.
- ↑ This rule table is already given in a shorthand form in the name "Rule 184", but it can be found explicitly e.g. in Fukś (1997).
- ↑ For the definition of this code, see Wolfram (2002), p.53. For the calculation of this code for Rule 184, see e.g. Boccara & Fukś (1998).
- ↑ See, e.g., Boccara & Fukś (1998).
- ↑ Li (1992). Li used this interpretation as part of a generalization of Rule 184 to nonlocal neighborhood structures.
- ↑ Boccara & Fukś (1998); Alonso-Sanz (2011).
- ↑ Boccara & Fukś (1998) have investigated more general automata with similar conservation properties, as has Moreira (2003).
- ↑ Li (1987).
তথ্যসূত্র[সম্পাদনা]
- Alonso-Sanz, Ramon (২০১১)। "Number-preserving rules"। Discrete Systems with Memory। World Scientific series on nonlinear science, Ser. A। 75। World Scientific। পৃষ্ঠা 55–57। আইএসবিএন 9789814343633।
- Belitsky, Vladimir; Ferrari, Pablo A. (১৯৯৫)। "Ballistic annihilation and deterministic surface growth"। Journal of Statistical Physics। 80 (3–4): 517–543। ডিওআই:10.1007/BF02178546। বিবকোড:1995JSP....80..517B।
- Biham, Ofer; Middleton, A. Alan; Levine, Dov (১৯৯২)। "Self-organization and a dynamic transition in traffic-flow models"। Physical Review A। 46 (10): R6124–R6127। arXiv:cond-mat/9206001 । ডিওআই:10.1103/PhysRevA.46.R6124। পিএমআইডি 9907993। বিবকোড:1992PhRvA..46.6124B।
- Boccara, Nino; Fukś, Henryk (১৯৯৮)। "Cellular automaton rules conserving the number of active sites"। Journal of Physics A: Math. Gen.। 31 (28): 6007–6018। arXiv:adap-org/9712003 । ডিওআই:10.1088/0305-4470/31/28/014। বিবকোড:1998JPhA...31.6007B।
- Capcarrere, Mathieu S.; Sipper, Moshe; Tomassini, Marco (১৯৯৬)। "Two-state, r = 1 cellular automaton that classifies density" (পিডিএফ)। Physical Review Letters। 77 (24): 4969–4971। ডিওআই:10.1103/PhysRevLett.77.4969। পিএমআইডি 10062680। বিবকোড:1996PhRvL..77.4969C।
- Chopard, Bastien; Droz, Michel (১৯৯৮)। Cellular Automata Modeling of Physical Systems। Cambridge University Press। আইএসবিএন 0-521-67345-3।
- Chowdhury, Debashish; Santen, Ludger; Schadschneider, Andreas (২০০০)। "Statistical physics of vehicular traffic and some related systems"। Physics Reports। 329 (4): 199–329। arXiv:cond-mat/0007053 । ডিওআই:10.1016/S0370-1573(99)00117-9। বিবকোড:2000PhR...329..199C।
- Fukś, Henryk (১৯৯৭)। "Solution of the density classification problem with two similar cellular automata rules"। Physical Review E। 55 (3): R2081–R2084। ডিওআই:10.1103/PhysRevE.55.R2081। বিবকোড:1997PhRvE..55.2081F।
- Fukś, Henryk; Boccara, Nino (১৯৯৮)। "Generalized deterministic traffic rules" (পিডিএফ)। International Journal of Modern Physics C। 9 (1): 1–12। ডিওআই:10.1142/S0129183198000029। বিবকোড:1998IJMPC...9....1F। ২৭ সেপ্টেম্বর ২০০৭ তারিখে মূল (পিডিএফ) থেকে আর্কাইভ করা।
- Fukui, M.; Ishibashi, Y. (১৯৯৬)। "Traffic flow in 1D cellular automaton model including cars moving with high speed"। Journal of the Physical Society of Japan। 65 (6): 1868–1870। ডিওআই:10.1143/JPSJ.65.1868। বিবকোড:1996JPSJ...65.1868F।
- Gaylord, Richard J.; Nishidate, Kazume (১৯৯৬)। "Traffic Flow"। Modeling Nature: Cellular Automata Simulations with Mathematica। Springer-Verlag। পৃষ্ঠা 29–34। আইএসবিএন 978-0-387-94620-7।
- Krug, J.; Spohn, H. (১৯৮৮)। "Universality classes for deterministic surface growth"। Physical Review A। 38 (8): 4271–4283। ডিওআই:10.1103/PhysRevA.38.4271। পিএমআইডি 9900880। বিবকোড:1988PhRvA..38.4271K।
- Land, Mark; Belew, Richard (১৯৯৫)। "No perfect two-state cellular automata for density classification exists"। Physical Review Letters। 74 (25): 1548–1550। ডিওআই:10.1103/PhysRevLett.74.5148। পিএমআইডি 10058695। বিবকোড:1995PhRvL..74.5148L।
- Li, Wentian (১৯৮৭)। "Power spectra of regular languages and cellular automata" (পিডিএফ)। Complex Systems। 1: 107–130। ৭ অক্টোবর ২০০৭ তারিখে মূল (পিডিএফ) থেকে আর্কাইভ করা। সংগ্রহের তারিখ ১৯ মার্চ ২০১৮।
- Li, Wentian (১৯৯২)। "Phenomenology of nonlocal cellular automata"। Journal of Statistical Physics। 68 (5–6): 829–882। ডিওআই:10.1007/BF01048877। বিবকোড:1992JSP....68..829L।
- Maerivoet, Sven; De Moor, Bart (২০০৫)। "Cellular automata models of road traffic"। Physics Reports। 419 (1): 1–64। arXiv:physics/0509082 । ডিওআই:10.1016/j.physrep.2005.08.005। বিবকোড:2005PhR...419....1M।
- Moreira, Andres (২০০৩)। "Universality and decidability of number-conserving cellular automata"। Theoretical Computer Science। 292 (3): 711–721। arXiv:nlin.CG/0306032 । ডিওআই:10.1016/S0304-3975(02)00065-8।
- Nagel, Kai (১৯৯৬)। "Particle hopping models and traffic flow theory"। Physical Review E। 53 (5): 4655–4672। arXiv:cond-mat/9509075 । ডিওআই:10.1103/PhysRevE.53.4655। বিবকোড:1996PhRvE..53.4655N।
- Nagel, Kai; Schreckenberg, Michael (১৯৯২)। "A cellular automaton model for freeway traffic"। Journal de Physique I। 2 (12): 2221–2229। ডিওআই:10.1051/jp1:1992277। বিবকোড:1992JPhy1...2.2221N।
- Pivato, M. (২০০৭)। "Defect particle kinematics in one-dimensional cellular automata"। Theoretical Computer Science। 377 (1–3): 205–228। arXiv:math.DS/0506417 । ডিওআই:10.1016/j.tcs.2007.03.014।
- Redner, Sidney (২০০১)। "8.5 Ballistic Annihilation"। A Guide to First-Passage Processes। Cambridge University Press। পৃষ্ঠা 288। আইএসবিএন 9780521652483।
- Sukumar, N. (১৯৯৮)। "Effect of boundary conditions on cellular automata that classify density"। arXiv:comp-gas/9804001 ।
- Tadaki, Shin-ichi; Kikuchi, Macato (১৯৯৪)। "Jam phases in a two-dimensional cellular automaton model of traffic flow"। Physical Review E। 50 (6): 4564–4570। ডিওআই:10.1103/PhysRevE.50.4564। বিবকোড:1994PhRvE..50.4564T।
- Wang, Bing-Hong; Kwong, Yvonne-Roamy; Hui, Pak-Ming (১৯৯৮)। "Statistical mechanical approach to Fukui-Ishibashi traffic flow models"। Physical Review E। 57 (3): 2568–2573। ডিওআই:10.1103/PhysRevE.57.2568। বিবকোড:1998PhRvE..57.2568W।
- Wolfram, Stephen (২০০২)। A New Kind of Science। Wolfram Media।