من تا مدت‌ها فكر مي‌كردم هر مساله‌اي راه‌حلي ساده اما زمانگير داره (مثل روش backtrack)، تا اينكه مساله Halting رو ديدم، مساله‌اي كه مهم نيست چقدر وقت بدي، به هر حال كامپيوتر جماعت نمي‌تونه حلش كنه! مساله اينه كه يه برنامه‌ي كامپيوتري داريم، مي‌خوايم ببينيم كه اگه اجراش كنيم بالاخره تموم مي‌شه يا تا بي‌نهايت ادامه داره! (يعني با توجه به محدوديت RAM و CPU، توي يه حلقه گرفتار مي‌شه يا نه) ثابت شده كه اين مساله در حالت كلي نمي‌تونه توسط كامپيوتر حل بشه!
هميشه اين سوال برام مطرح بود كه اون مسائلي كه توسط كامپيوتر حل نمي‌شن همين قدر فلسفي‌ان يا اين كه مسائل ملموس‌تري هم هستن كه كامپيوتر نتونه حلشون كنه. وقتي مي‌گم مساله ملموس منظورم همين مسائل عادي هستن كه معمولاً كامپيوتر تو حلشون خيلي كمك مي‌كنه، مثل اين مسئله:
فرض كنيد يه مجموعه‌اي از دومينوها داريم، كه طرف پايين و بالاش يه سري حرف نوشته شده، مي‌خواييم ببينم كه آيا مي‌شه اينارو يه طوري بغل هم گذاشت كه جمله‌اي كه طرف بالاي دومينوها ايجاد مي‌شه همون جمله‌اي باشه كه طرف پايين ايجاد مي‌شه؟! (تكرار هم مجازه)
مثلاً براي اين مجموعه
اين مي‌تونه يه جواب باشه
من كه خيلي تعجب كردم وقتي فهميدم، اين مساله با اين درجه از ملموسيت(!) هم در حالت كلي توسط كامپيوتر نمي‌تونه حل بشه، هر چقدر هم كه بهش زمان بديم!
پست جالبیه, بار علمیش بالاست, مرسی!
پاسخحذففکر کنم این مسائل زیادن , هر برنامه ای می نویسم اصولا تو هالتینگ قرار می گیره!
ممنون!
پاسخحذفاتفاقاً مسائلي كه كامپيوتر نمي‌تونه حلشون كنه، خيلي كمن. من 2 تا نمونه‌ش رو گفتم، اما در كل خيلي محدودتر از مسائلي هستن كه كامپيوتر مي‌تونه حلشون كنه.
هر برنامه‌اي كه ما مي‌نويسيم مي‌تونه به عنوان يه ورودي براي Halting باشه و اگه بخوايم تركيب ورودي و Halting رو به عنوان يك مساله جديد بگيريم، اون موقع به احتمال زياد (بسته به ورودي) مساله‌اي قابل حل مي‌شه و Halting در حالت كليه كه غير قابل حل توسط كامپيوتره.
استفاده از ورشهاي پردازشي پيچيده تر مثل پردازش موازي يا روشهاي هوش مصنوعي مثل آنت كولوني چي؟ اين مسائل كه مثال زدي رو نمي شه حل كرد؟
پاسخحذفيعني مسائلي هستن كه با هيچ ماشين پردازنده اي قابل حل نيستن؟
نه! بازم نمي‌تونه و اين اثبات شده و اثباتش هم مستقل از الگوريتم حل مساله‌اس!
پاسخحذفجالبه، يه سوال : اگه ذهن انسان مسائله اي رو طرح و حل مي كنه ( نه لزوما در يك زمان و يك شخص) آيا نمي شه اون رو با ماشين حل كرد؟ يعني چنين مسائلي هستن؟
پاسخحذف:-؟
تا اونجا كه به عقل من مي‌رسه، هر چيزي كه مغز آدم بتونه حل كنه كامپيوتر هم مي‌تونه، البته شايد با زمان خيلي بيشتر.
پاسخحذفچون كه مغز آدم از ميلياردها سلول عصبي ساخته شده كه هر كدوم قابل شبيه‌سازين. اما مشكل اينجاس كه اون ميلياردها سلول به صورت موازي با هم كار مي‌كنن ولي ما با پيشرفته‌ترين كامپيوترها هم از مرتبه‌ي هزار مي‌تونيم موازي‌سازي بكنيم. البته ارتباطات سلول‌هاي عصبي مغز هم پيچيده‌تر از جيزيه كه بتونه به راحتي در بياد.
:)
پاسخحذفآره يه روزي مي شه! شايد حالا نه، اما روند حركت به اين سمت مي ره! نمي دونم اين خوبه يا بد اما مسير علم اينه!