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

 پيوندهاي المپياد كامپيوتر
 سايت‌هاي المپياد كامپيوتر
 
 مجادله‌اي 25 هزار دلاري! (زنگ تفريح شماره‌ي 40)
مجادله‌اي 25 هزار دلاري! (زنگ تفريح شماره‌ي 40)زنگ تفريح كامپيوتر
مسأله‌هاي بحث بر‌انگيز

مجادله‌اي 25 هزار دلاري!






شكل 1 - «آلن تورينگ» (Alan Turing).

اشاره

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




چكيده
اهداف آموزشي
 اهداف آموزشي در حوزه‌ي شناختي - دانش
    
- «دانش امور جزوي» > «دانش اصطلاح‌ها»
    
- «دانش امور جزوي» > «دانش روال‌ها و توالي‌ها»
 اهداف آموزشي در حوزه‌ي شناختي - توانايي‌ها و مهارت‌هاي ذهني
    - «فهميدن» > «ترجمه» <
«تفسير»
    - «فهميدن» > «ترجمه» <
«برون‌يابي»
 نتايج مورد نظر
    
- آشنايي با ماشين تورينگ 
    
- آشنايي با تاريخچه‌ي برخي مسائل بحث‌برانگيز رياضي و كامپيوتر 
    
- آشنايي با تأثير كامپيوتر بر اثبات قضاياي رياضي
 محتواي آموزشي (سرفصل‌هاي المپياد)
- متفرقه






 

شكل 2 - «الكس اسميت» (Alex Smith)
دانشجوي 20 ساله‌اي كه توانست مسأله‌ي
ساده‌ترين «ماشين تورينگ» ممكن
در جهان را حل كند.


يك مسأله با قدمت 50 ساله در ماه‌هاي اخير به مجادله‌اي مبدل شده و براي اثبات آن حدود 25 هزار دلار معين شد.

دانشجوي 20 ساله‌ در مقطع كارشناسي دانشگاه «بيرمنگام» (Birmingham) به‌نام «الكس اسميت» (Alex Smith) توانست مسأله‌ي ساده‌ترين «ماشين تورينگ» (Turing Machine) ممكن در جهان را حل كند؛ اين در حالي است كه قبل از آن حدود نيم قرن براي حل آن تلاش انجام گرفته بود. اما استدلال 40 صفحه‌اي «الكس اسميت» (Alex Smith) از «ماشين تورينگ 2 و 3 ولفرام» (Wolfram's 2,3 Turing Machine) شهرت جهاني پيدا كرد.

اما به هر حال نتيجه‌ي آن و جايزه‌ي پژوهشي «ماشين تورينگ 2 و 3 ولفرام» (Wolfram's 2,3 Turing Machine) در حال حاضر بسيار بحث‌برانگيز است.


 

شكل 3 - «ايمريتوس وائوقان رونالد پرات»
(Emeritus Vaughan Ronald Pratt
)



پروفسور «ايمريتوس وائوقان رونالد پرات» (Emeritus Vaughan Ronald Pratt) يكي از پيشگامان در حوزه‌ي علوم كامپيوتر نه آن‌چنان زيركانه در مقاله‌اي از «استدلال» پرسيده و مي‌گويد:

«بدون اين‌كه بخواهم بر روي شانسم تأكيد كنم جواب يك سؤال را خواهم يافت. چگونه يك بحث شامل چنين استدلال مقدماتي غلطي از فيلتر مي‌گذرد (صحت آن بررسي مي‌شود)؟

آيا بر روي شانسم در جواب به سؤال دوم تأكيد كنم در حالي كه اين اثبات معين كرده است كه درسي از «نظريه‌ي ماشين‌ها» (Automata Theory) در يك عرف نسبتاً قابل پذيرش به ما آموخته شده است؟»

علت شهرت مقاله‌ي مذكور، اختصاص جايزه‌ي «ماشين تورينگ 2 و 3 ولفرام» (Wolfram's 2,3 Turing Machine) است كه به‌نام «استفان ولفرام» (Stephaen Wolfram) بنيانگذار شركت نرم‌افزاري «توسعه و تحقيق برنامه‌ي نرم‌افزاري رياضي مسمتيكا» (Wolfram Research and Developer of Mathematical Software Program Mathematica) ناميده شده است.


 

شكل 4 - «استفان ولفرام»
(Stephaen Wolfram)


در سال 1381 (2002 ميلادي) «استفان ولفرام» (Stephaen Wolfram) مقاله‌ي 1200 صفحه‌اي خود را با عنوان «نوع جديدي از علوم» (A New Kind of Science) نوشت. اين جايزه به‌خاطر اثبات تفكري اهدا شد كه «استفان ولفرام» (Stephaen Wolfram) طرح كرده بود؛ اين‌كه يك «ماشين ساده‌ي تورينگ» (Simplified Turing Machine) – كه مدلي رياضي از يك كامپيوتر بوده و بنابراين كاملاً تئوري است – اصولاً مي‌تواند هر برنامه‌ي كامپيوتري ممكن را به‌كار اندازد.

عقيده‌ي «ماشين تورينگ» در سال 1315 (1936 ميلادي) براي اولين بار توسط رياضيدان انگليسي «آلن تورينگ» (Alan Turing) مطرح شد. «ماشين تورينگ» (Turing Machine) از لحاظ تئوري يك نوار «علامت‌زن» (Ticker Tape) را با رشته‌اي از علامت‌ها بر روي خط نوار در وضعيتي خاص بررسي مي‌كند. براي هر علامتي كه وارد مي‌نمايد (مثلاً: يك ستاره) يك قاعده‌ي خيلي ساده اجرا مي‌شود:

- اگر علامت يك ستاره باشد و خانه‌ي مذكور در وضعيت 1 قرار داشته باشد اين علامت را با خانه‌ي خالي جايگزين كرده و يك علامت به‌سمت راست جابه‌جا مي‌كند. در اين صورت فرض مي‌كنيم در وضعيت 2 قرار گرفته‌ است».

مثالي ساده از قدرت محاسبه‌اي ماشين مذكور، در نظر گرفتن جمع اعداد صحيح است. مي‌توانيم يك عدد صحيح با رشته‌اي از ستاره‌ها بيان كنيم.

به‌عنوان مثال:

 ** بيانگر عدد 2
 **** بيانگر عدد 4
 و ...

باشد. براي افزودن عدد 2 به عدد 4، «**» و «****» بر روي نوار چاپ مي‌شود؛ هم‌چنين بين دو متغير «رشته‌اي» (String) يك فاصله قرار مي‌گيرد. رديف مربوط به آن «صفر» در نظر گرفته مي‌شود:

**_****

سپس ماشين مذكور با توجه به قواعد تعريف‌شده‌اي عمل مي‌كند. در اين حالت، ماشين مذكور با مشاهده‌ي اولين خانه آغاز كرده و قواعد ذيل پيروي مي‌نمايد:

 

وضعيت صفر
اگر خانه يك ستاره باشد يك خانه به‌سمت راست حركت مي‌كند.

 وضعيت صفر
اگر خانه خالي باشد خانه را با يك ستاره پر كرده يك خانه به‌سمت راست حركت مي‌نمايد و وضعيت از «صفر» به «1» تغيير مي‌كند.

 وضعيت 1
اگر خانه يك ستاره باشد يك خانه به‌سمت راست حركت دهيد.

 وضعيت 1
اگر خانه خالي باشد يك خانه به‌سمت چپ حركت داده و وضعيت را به وضعيت 2 تغيير دهيد.

 وضعيت 2
اگر خانه يك ستاره باشد خانه را پاك كرده و ماشين متوقف مي‌شود.

با پيروي از اين قواعد، ماشين مذكور خانه‌ي خالي را با چاپ يك «ستاره»‌ (*) پر كرده و به پايان رشته‌ي ستاره‌ها رفته و آخرين خانه را پاك مي‌كند. بدين‌ترتيب شش ستاره در يك رديف خواهيم داشت كه نتيجه‌ي مورد نظر را تأمين مي‌كند.

از نظر تئوري هر محاسبه‌اي براي «نوار علامت‌زن» (Ticker Tape) مي‌تواند با استفاده از «ماشين تورينگ» به‌دست آيد. خود «تورينگ» ثابت كرد كه چنين ماشين‌هايي مي‌توانند «چندمنظوره» (Universal) باشند يعني اگر دستورالعملي موجود باشد هر «ماشين تورينگ» ديگر را مي‌توان ايجاد كرد.

اين‌جا است كه جايزه‌ي «ولفرام» (Wolfram) به‌خاطر آن در نظر گرفته ‌مي‌شود. طي پژوهشي در سال 1329 (1950 ميلادي) ثابت شد نمي‌توانيم يك ماشين دو وضعيتي و دو علامتي (2، 2) داشته باشيم. خود «ولفرام» (Wolfram) گزارش داد كه مي‌توانيم ماشيني دو وضعيتي و پنج علامتي (5، 2) داشته باشيم.

اما آيا مي‌توانيم «ماشين تورينگ» (3، 2) داشته باشيم؟

اثبات منتسب به «اسميت» (Smith) هدفش نشان دادن آن است مي‌توانيم چنين ماشيني داشته باشيم در 40 صفحه ارائه شده است. اگر اين مسأله واقعيت داشته باشد از لحاظ رياضي جالب است. اگرچه چنين كامپيوتر ساده‌اي زمان زيادي را صرف كرده و حافظه‌ي بسيار زيادي براي اجراي آن لازم است حتي اگر «وظايف محاسبه‌اي» (Computing Tasks) ساده‌اي نياز باشد.

هم‌چنين مجادله‌هايي حول مسائل نسبتاً درستي انجام شده كه توسط «ولفرام» (Wolfram) براي بررسي نتايج انتخاب شده است. محققي به‌نام «ايمريتوس وائوقان رونالد پرات» (Emeritus Vaughan Ronald Pratt) ادعا مي‌كند كه ممكن است چنين قضاوت‌هايي بر روي اين مسائل نامناسب باشد. مجادله‌ي مذكور منجر به «دور فلسفي» (Philosophical Turn) شده است البته با مواردي كه «انگاره» (Conjecture) محسوب شده و به‌طور واقعي مي‌توان اصطلاح «چندمنظوره» (Universal) به آن اطلاق كرد.

بدين‌ترتيب مجادله در «تالار گفتگو» (Forum) «ولفرام» (Wolfram) ادامه يافته و «پرات» (Pratt) و «اسميت» (Smith) خودشان مؤدبانه در اين موضوع با يكديگر بحث كرده‌اند. بايد از اين امر پيروي كنيم و اجازه دهيم از آن‌چه اتفاق مي‌افتد همه باخبر شوند.


 

 شكل 5 - «فردريك وولفس‌كهل»
(Friedrich Wolfskehl)‌
.



لغزيدن بر روي موانع نهايي و مجادله‌هاي فلسفي بر روي اثبات‌ها چيز جديدي براي رياضيدانان محسوب نمي‌شود. چندين جايزه براي حل «آخرين قضيه‌ي فرما» (Fermat's Last Theorem) (به‌عنوان مشهورترين انگاره‌ي رياضي در دهه‌هاي 1800 و 1900 ميلادي) پيشنهاد شد:

در سال‌هاي 1202 و 1229 (1823 و 1850 ميلادي)، «آكادمي علوم فرانسه» (The French Academy of Sciences) جايزه‌اي را براي حل آن پيشنهاد داد.

 

 سپس در سال 1222 (1823 ميلادي) جايزه‌اي از طرف «آكادمي بروكسل» (The Academy of Brusses) پيشنهاد شد.

 

 در سال 1286 (1908 ميلادي) «فردريك وولفس‌كهل» (Friedrich Wolfskehl)‌ آلماني 100 هزار مارك به «آكادمي علوم گوتينگن» (The Gottingen Academy of Sciences) براي اثبات كامل «آخرين قضيه‌ي فرما» (Fermat's Last Theorem) تعيين كرد.


 

شكل 6 - «هوارد ايوز»
(Howard Eves)
.



مورخ رياضي «هوارد ايوز» (Howard Eves) مي‌گويد: «آخرين قضيه‌ي فرما (Fermat's Last Theorem) عامل تشخيص عجيب و غريب مسأله‌‌اي رياضي بود كه براي آن بيش‌ترين اثبات‌هاي ناصحيح منتشر شد».

بالاخره اين مسأله (آخرين قضيه‌ي فرما Fermat's Last Theorem) در سال 1369 (1990 ميلادي) توسط «اندرو وايلز» (Andrew Wiles) اثبات شد.

مسأله‌ي رياضي ديگري كه بحث‌برانگيز شد «قضيه‌ي چهار رنگ» (The Four Colour Theorem) بود.

براي طراحان نقشه، قرن‌ها اين مطلب مشهور شده بود كه هرگز به بيش از چهار رنگ براي رنگ كردن يك نقشه نياز نيست كه در آن، دو ناحيه‌ي مجاور داراي رنگ يكسان باشند. اگرچه اين مفهوم ساده به‌نظر مي‌رسيد اثبات آن به‌طوري باورنكردني سخت بود و بسته به اين‌كه در كدام ناحيه نشسته باشند هرگز مشخص نمي‌شد.


شكل 7 - «آلفرد كمپه»
(Alfred Kempe)



در سال 1258 (1879 ميلادي) رياضيداني انگليسي به‌نام «آلفرد كمپه» (Alfred Kempe) در مجله‌هاي «نيچر» (Nature) و «مجله‌ي رياضيات امريكا» (American Journal of Mathematics) به‌تشريح اثباتي پرداخت كه 11 سال پيش از آن، اشتباه شمرده مي‌شد.


 

شكل 8 - «كنت ايرا اپل»
(Kenneth Ira Appel)

 

شكل 9 - «ولفگانگ هيكن»
(Wolfgang Haken
)



يك قرن گذشت؛ قبل از آن‌كه قدمي رو به جلو براي حل اين مسأله برداشته شود. در سال 1355 (1976 ميلادي) «كنت اپل» (Kenneth Appel) و «ولفگانگ هيكن» (Wolfgang Haken) نهايتاً اثبات آن را به‌روشي ساده مديريت كردند. اما به هر حال، اين‌بار مجادله بر سر استفاده از «كامپيوتر» بود.

«كنت ايرا اپل» (Kenneth Ira Appel) و «ولفگانگ هيكن» (Wolfgang Haken) مجبور بودند هر يك از 1936 طرح‌هاي پيكربندي (Configurations) را در نظر بگيرند و اين كار تنها بر روي يك كامپيوتر انجام‌پذير بود. تعداد محاسبه‌هاي كامپيوتري آن‌قدر وسيع بود كه هيچ انساني نمي‌توانست محتملاً درستي اثبات را بررسي كند. اين مسأله‌ي بغرنجي را ايجاد كرده بود كه آيا مي‌توان مطمئن شد يك ماشين، عمليات رياضيات را انجام دهد؟

بدين‌ترتيب جامعه‌ي رياضي به دو اردوگاه تقسيم شد:

آن‌هايي كه آماده مي‌شدند تا اثبات‌هاي كامپيوتري را بپذيرند.

 

 آن‌هايي كه به‌دنبال نسخه‌هاي ساده‌تري بودند تا بتوانند اثبات‌ها را بررسي كنند.


بدين‌گونه است كه راه اثبات «قضيه‌ي چهار رنگ» (The Four Colour Theorem) كماكان باز است.

مجادله‌هاي رياضي نظير اين قضيه و موارد مشابه را در قسمت‌هاي بعدي زنگ تفريح‌هاي المپياد كامپيوتر به‌كمك شما دوستان خوب ارائه خواهيم كرد.

1387/2/4لينک مستقيم

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

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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