زنگ‌تفریح تصادفی

 پيوندهاي المپياد كامپيوتر
 سايت‌هاي المپياد كامپيوتر
 
 «ماشين خودكار» (Automation) (زنگ تفريح شماره‌ي 44)
«ماشين خودكار» (Automation) (زنگ تفريح شماره‌ي 44)زنگ تفريح كامپيوتر
بازي زندگي

«ماشين خودكار» (Automation)






اشاره
آن‌چه با عنوان «چكيده» در اول مسابقه‌ها و زنگ‌تفريح‌ها مشاهده مي‌كنيد صرفاً مخصوص معلمان، مربيان، كارشناسان محترم آموزشي و ساير علاقه‌مندان است.



چكيده
اهداف آموزشي
 اهداف آموزشي در حوزه‌ي شناختي – دانش
    - «دانش امور جزوي» > «دانش اصطلاح‌ها»
    - «دانش امور جزوي» > «دانش واقعيت‌هاي مشخص»
    - «دانش راه‌ها و وسايل برخورد با امور جزوي» > «دانش امور قراردادي»
    - «دانش راه‌ها و وسايل برخورد با امور جزوي» > «دانش طبقه‌بندي‌ها و طبقه‌ها»
 نتايج مورد نظر
    - آشنايي با «بازي زندگي» (Game of Life)
    - آشنايي با «ماشين خودكار» (Automation)
 محتواي آموزشي
    - «بازي زندگي» (Game of Life)
    - «ماشين خودكار» (Automation).



شكل 1 - «جان هورتون كانوي»
(John Horton Comway)
.

مقدمه
مشهورترين «ماشين خودكار سلولي دوبعدي» (Two Dimensional Cellular Automation) ابتدا توسط «جان هورتون كانوي» (John Horton Comway) طراحي و در مهر 1349 (1970 ميلادي) براي اولين بار توسط «مارتين گاردنر» (Martin Gardner) در ستون مجله‌ي «ساينتيفيك امريكن» (Scientific American) براي عموم مطرح شد.


شكل 2 - «مارتين گاردنر»
(Martin Gardner)
.


بازي «زندگي»
«زندگي» (Life) – كه گاهي «بازي زندگي» (The Game of Life) نيز ناميده مي‌شود – اولين بار با سيستم شمارش دستي البته با اجرا بر روي يك كامپيوتر انجام شد. به‌طوري‌ كه شيوه‌هاي جستجو در آن به راحتي انجام گيرد.



شكل 3 - معناي زندگي.



«ماشين خودكار سلولي دوبعدي» (Two Dimensional Cellular
Automation)
«ماشين خودكار سلولي دوبعدي» (Two Dimensional Cellular Automation) با عنوان «زندگي» (Life) با قرار دادن يك عدد از خانه‌هاي پرشده در يك شبكه‌ي دوبعدي اجرا مي‌شود. هر وضعيت خانه‌ها را «روشن» (On) يا «خاموش» (Off) مي‌نامند برحسب اين‌كه خانه‌هاي اطراف آن در چه وضعيتي قرار دارند.

قواعد به‌صورت ذيل تعريف مي‌شود:

- همه‌ي هشت خانه‌اي كه خانه‌ي مورد نظر را احاطه مي‌كنند بررسي مي‌شوند تا معلوم شود «روشن» هستند يا «خاموش».

- هر خانه‌اي كه «روشن» باشد شمرده شده و سپس اين شمارش براي تعيين آن‌چه در مورد خانه‌ي مورد نظر اتفاق خواهد افتاد به‌كار مي‌رود.

از طرف ديگر اصطلاح‌هاي به‌كار رفته به‌صورت ذيل تعريف مي‌شود:




مرگ (Death)
اگر شمارش (خانه‌هاي روشن) كم‌تر از 2 يا بيش‌تر از 3 باشد خانه‌ي مورد نظر «خاموش» مي‌شود.




بقا (Survival)
اگر:

شمارش (خانه‌هاي روشن) دقيقاً عدد 2 را نشان دهد

يا شمارش (خانه‌هاي روشن) دقيقاً عدد 3 را نشان دهد و خانه‌ي مورد نظر «روشن» باشد.






تولد (Birth)
اگر خانه‌ي مورد نظر «خاموش» باشد و شمارش (خانه‌هاي روشن) دقيقاً عدد 3 را نشان دهد خانه‌ي مورد نظر «روشن» خواهد شد.

بازي (Life) يك «ماشين خودكار دوبعدي با كنترل مركزي» (Totalistic Cellular Automation) بوده و مي‌تواند با استفاده از دستور دروني «ماشين خودكار سلولي» (Cellular Automation) اجرا شود كه در آن «شرايط اوليه» با «ماتريس دودويي» (Binary Matrix) به‌نام m بوده و نتايج براي توليد از  تا  برمي‌گردد.




ياداوري

- منظور از «ماتريس دودويي» (Binary Matrix) ماتريسي است كه هر درايه‌ي آن يا «صفر» است يا «يك».

– در حالت اوليه  است.



























شكل 4 - «اريك و. وايس اشتاين»
(Eric W. Weisstein)
.



«اريك و. وايس اشتاين» (Eric W. Weisstein)
جداول وسيعي از اشكال «زندگي» (Life) و شرايط آن را ارائه كرده است.

شكل 5 - «بلوك» (Block).

 

شكل 6 - «وان» (Tub).

 

شكل 7 - «قايق» (Boat).

 

شكل 8 - «مار» (Snake).

 

شكل 9 - «كشتي» (Ship).

 

شكل 10 - «حامل هواپيما»
(Aircraft Carrier).

 

شكل 11 - «كندو» (Beehive).

 

شكل 12 - «كرجي» (Barge).

 

شكل 13 - «اژدها» (Python).

 

شكل 14 - «كشتي بلند» (Long Boat).

 

شكل 15 - «قلاب ماهيگيري» (Fishhook)
يا «كسي كه غذا مي‌خورد» (Eater).

 

شكل 16 - «قرص نان» (Loaf).

الگويي كه از يك وضعيت به وضعيت ديگر تغيير نمي‌كند «بي‌جان» (Still Life) ناميده شده و گفته مي‌شود در پريود اول (Period 1) قرار دارد.

چند نمونه از وضعيت‌هاي «بي‌جان» (Still Life) در اشكال 1 تا 12 نشان داده شده است.

همان‌طور كه توسط «اسلوان» (Sloane) نشان داده شده است (Sloane's A019473) تعداد وضعيت‌هاي «بي‌جان» (Still Life) با خانه عبارت است از:







 

شكل 17.

الگوهايي كه به‌طور متناوب به‌صورت مجموعه‌اي از وضعيت‌ها ظاهر مي‌شود «نوسانگر» (Oscillator) ناميده مي‌شود (شكل 13).

 

شكل 18 - مثال‌هايي از شمارنده‌ها
شامل: «تفنگ‌ها» (Guns) و
قطارهايي از «دود سيگار» (Puffers).

«جان هورتون كانوي» (John Horton Comway) اعتقاد داشت اصولاً هيچ الگويي تعداد نامحدودي از خانه‌ها را ايجاد نمي‌كند و قبل از سال 1349 (1970 ميلادي) جايزه‌اي 50 دلاري را براي هر شخصي پيشنهاد كرد كه بتواند يك مثال از چنين شمارنده‌اي بيابد (Gardner, Martin; “Scientific American”; 1983; P. 216) (شكل 14).

در نتيجه مثال‌هايي از شمارنده‌ها پيدا شد كه شامل: «تفنگ‌ها» (Guns) و قطارهايي از «دود سيگار» (Puffers) بود.

يك الگوي «زندگي» كه داراي «الگوي پدر» (Father Pattern) نباشد به‌عنوان «باغ عدن» (Garden of Eden) - همان‌طور كه در قرآن و كتاب مقدس مسيحيت ذكر شده – شناخته شده است. همانند چنين الگويي تا سال 1350 (1971 ميلادي) وجود نداشت و حداقل امروزه شناخته شده است.

اما به‌هر حال همان‌طور كه «مارتين گاردنر» (Martin Gardner) اظهار داشته است:

«وجود الگويي‌ها را بيابد داراي الگوي «پدر» (Father) و «پدر بزرگ» (Grand Father) شناخته شده نيست» (Gardner, Martin; “Scientific American”; 1983; P. 249).

متحيركننده آن‌كه «زندگي» (Life) يك «ماشين خودكار سلولي جهاني» (Universal Cellular Automation) است در حالتي كه به‌طور مؤثر قابليت برابري كردن با هر «ماشين خودكار سلولي» (Cellular Automation)، «ماشين تورينگ» (Turing Machine) يا هر سيستم ديگري را داشته باشد كه مي‌تواند به سيستمي تبديل شود كه به‌عنوان «جهاني» (Universal) شهرت دارد.


 

شكل 19 - «الوين ر. برله‌كمپ»
(Elwyn R Berlekamp)
.



طرح‌هاي اثبات براي جهان‌شمولي «زندگي» (Life) توسط محققيني به‌نام «الوين ر. برله‌كمپ» (Elwyn R Berlekamp)، «جان هورتون كانوي» (John Horton Comway) و «ريچارد كنث گاي» (Richard Kenneth Guy) ارائه شده است (Gardner, Martin; “Scientific American”; 1983; P. 250-253).


شكل 20 - «ريچارد كنث گاي»
(Richard Kenneth Guy)
.



حدود سال 1380 (2001 ميلادي) يك «ماشين تورينگ» (Turing Machine) - كه مي‌تواند به يك «ماشين تورينگ جهاني» (Universal Turing Machine) بسط يابد - به‌طور واضح در «زندگي» (Life) توسط «پ. رندل» (P. Rendell) اعمال شده است (Rendell, Adamatzky, 2001).

اين در حالي است كه «ماشين رندل» (Turing Rendell) مي‌تواند به‌سادگي با ساختن بي‌نهايت نوار آن به كامپيوتر جهاني «واقعي» (True Universal Computer) تبديل شود. وي نه‌تنها اين واقعيت را متذكر شد بلكه ساختاري واقعي از «ماشين تورينگ جهاني» (Universal Turing Machine) ارائه داد.

نهايتاً در شماره‌ي 21 آبان 1381 (11 نوامبر 2002 ميلادي) مجله‌ي «ساينتيفيك امريكن» (Scientific American)، «چاپمن» (Chapman) يك الگوي «زندگي» (Life) براساس روش «حافظه‌ي بلوك لغزنده» (Sliding Block Memory) ايجاد كرد كه در يك «ماشين ثبت جهاني» (Universal Register Machine) به‌كار مي‌رود.

برعكس «نوار محدود ماشين تورينگ رندل» (Finite of Rendell’s Turing Machine) مقادير ثبت‌هاي «ماشين‌ چاپمن» (Chapman’s Machine) بيكران بوده و مدلي صحيح از محاسبه‌‌ي جهاني در «بازي زندگي» (Game of Life) محسوب مي‌شود.

ساختار «چاپمن» (Chapman) از 268096 خانه‌ي زندگي در مساحتي به‌ميزان  استفاده مي‌كند و مي‌تواند به‌طور تقريبي 20 وضعيت در يك كامپيوتر 400 مگاهرتزي محاسبه شود.

حتي «ماشين خودكار سلولي يك‌بعدي» (One Dimensional Cellular Automation) (به‌خصوص قاعده‌ي 110) (Rule 110) – همان‌طور كه توسط «وولفرام» (Wolfram) در سال 1381 (2002 ميلادي) نشان داده شده است – به‌صورت به‌طور بسيار متحيركننده‌اي «بي‌جان» (Still) مي‌تواند «جهاني» (Universal) باشد.

بازي‌هاي «ماشين خودكار سلولي دوبعدي» (Two Dimensional Cellular Automation) شبيه به «زندگي» (Life) اما با قواعدي متفاوت ساخته شده و به‌نام «هگزلايف» (HexLife) و «هاي‌لايف» (HighLife) ناميده مي‌شود.

«هاش‌لايف» (HashLife) الگوريتم بازي‌اي است كه با مرتب كردن «الگوهاي فرعي» (Sub Patterns) سرعت قابل‌ملاحظه‌اي در «جدول هاش» (Hash Life) داشته و با استفاده از آن‌ها گاهي اوقات براي به‌جلو پريدن، نياز به هزاران تبديل در يك زمان دارد.

1387/7/20لينک مستقيم

فرستنده :
tara HyperLink HyperLink 1387/11/30
مـتـن : mataleb machin khodkareton khaili khob bod.agar emkan dara beshtar dar mored on tavzih bedin ya be email am send konin.khaili az shoma sepasgozar misham
پاسـخ :ايميل فرستنده: papo3243@yahoo.com
تاريخ ارسال:‌ 1387/7/21
تارا جان!
سلام
از اظهار لطفت ازت تشكر مي‌كنيم.
راجع به اطلاعات بيش‌تري كه مي‌خواستي مي‌توني به‌نشاني‌هاي ذيل مراجعه بكني:
http://www.frank-buss.de/automaton/
http://en.wikipedia.org/wiki/Cellular_automaton
http://cell-auto.com/
مطلب سايت هم از اين نشاني انتخاب شده:
http://mathworld.wolfram.com/CellularAutomaton.html
به‌طور كلي با جستجوي كلمه‌ي Cellular Automaton مي‌توني اطلاعات زيادي به‌دست بياري.
منتظر حضور فعالت در ساير بخش‌ها به‌خصوص بخش مسابقه‌ هستيم.
انشاء‌الله موفق باشي!

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 زنگ تفريح‌ها

 
 المپياد كامپيوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  8056
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  8056