Amir Ali Ebrahim Zadeh
Amir Ali Ebrahim Zadeh
خواندن ۱ دقیقه·۳ سال پیش

خدمتِ بزرگِ الن تورینگ، به زبان ساده

فیلم The Imitation Game
فیلم The Imitation Game

شما یه سری مفهوم شهودی و نادقیق ولی بنیادین تو علوم کامپیوتر دارید، مثل "الگوریتم" یا "برنامه" یا "مسئله". این‌ها یعنی چی؟ چجوری می‌شه درباره‌شون قضیه اثبات کرد؟ کار وقتی سخت می‌شه که می‌گید:

1. این مسئله، حل‌ناپذیره.

2. مسئله‌ی مرتب‌سازی لیستی از اعداد، مسئله آسونیه.

3. الگوریتم سریع و کارایی برای این مسئله وجود نداره.

خب این احکام دقیقا یعنی چی؟ و چجوری می‌شه اثبات‌شون کرد؟ یعنی چی "سخت"، "آسون" یا "حل‌ناپذیر"؟

حالا ما می‌خوایم یه تعریف دقیق و فرمال از همین مفاهیم "الگوریتم" و "مسئله" و "سختیِ مسئله" بدیم، این‌جاست که تورینگ وارد می‌شه. تورینگ یه شیء ریاضی، یه کامپیوتر انتزاعی معرفی می‌کنه که بهش می‌گیم ماشین تورینگ، ماشین تورینگ یه مجموعه‌ست، یه 7-تایی مرتب، که اعضاش هم یک سری مجموعه‌ان، و کاملا با اشیاء ریاضی ساخته شده.

و حالا ما یه تعریفِ دقیق و ریاضی‌وار از "الگوریتم" داریم و می‌تونیم با همین فرمون، "مسئله" و "مسئله سخت" و "مسئله حل‌ناپذیر" رو تعریف کنیم و دنیایی از قضایا رو اثبات کنیم. و می‌شه از همه این مفاهیم و اثبات‌های دقیق استفاده کرد برای ساخت یک نظریه چاق و غنی که امروزه بهش می‌گیم علوم کامپیوتر.


پی‌نوشت: خعلی nerdی بود. با این حال عمیقا ماشین تورینگ مفهوم مهمی در علوم کامپیوتر نظری، ریاضیات، حتی منطق و فلسفه ذهن‌ه.

پ.ن 2: تورینگ رو ملت اکثرا بخاطر جنگ جهانی و فاز فیلم imitation game می‌شناسن، درحالی که اصل دست‌آوردش مربوط به بنیاد نهادن علوم کامپیوتره که به لطفش داریم تو اینترنت چرخ می‌زنیم.

تورینگماشین تورینگعلوم کامپیوترنظریه محاسبات
دانشجوی کارشناسی کامپیوتر و ماینور فلسفه علم دانشگاه شریف :)
شاید از این پست‌ها خوشتان بیاید