অনির্ণেয়তা

কম্পিউটারে কি সব কিছু হিসাব করা সম্ভব? আপনি বলবেন নিশ্চই, ‘না’। অন্তত কম্পিউটারকে তেমন সর্বময় ক্ষমতার অধিকারী আমরা কেউ ভেবে অভ্যস্ত নই। কিন্তু ‘কেন নয়?’ হ্যা বৈজ্ঞানিক পদ্ধতির একটা গাঠনিক উপাদান এই প্রশ্ন ‘কেন’। পরীক্ষাগারে আমরা এক রকম রেজাল্ট পেতেই পারি। কিন্তু ‘কেন এমনটা হচ্ছে?’ এই প্রশ্নের উত্তর জানার মধ্যেই লুকিয়ে আছে সেই এক্সপেরিমেন্টটার বৈজ্ঞানিক সাফল্য। আর বিজ্ঞানের ভাষাতো একটাই- গণিত। তাই এই ‘কেন’র উত্তর আমাকে জানতে হবে গাণিতিক উপায়ে। তো আসুন আমরা গাণিতিক ভাবে বোঝার চেষ্টা করি ‘কেন কম্পিউটারে সব হিসাব করা সম্ভব নয়’।

যাদের প্রোগ্রামিং সম্পর্কে ধারনা আছে তারা তো জানেনই যে কম্পিউটার প্রোগ্রাম হচ্ছে একটা ‘লিখিত জিনিশ’। মানে আমরা ‘এ বি সি ডি… ১ ২ ৩’ এসব ব্যবহার করেই বিভিন্ন ভাষায় প্রোগ্রাম লিখে থাকি। এটাকে একটা রচনার মত করে কাগজে প্রিন্ট করেও ফেলা সম্ভব। সেই রচনাকে আমরা বলব প্রোগ্রামটির ‘কোড’। আবার কম্পিউটারে সাধারণ রচনাও লেখা সম্ভব। যেমন আমার এই লেখাটা একটা রচনা। এটা প্রোগ্রাম নয়। প্রোগ্রামের কাজ হলো বিভিন্ন তথ্য ইনপুট নেওয়া(গ্রুহন করা) এবং সেই ইনপুট এর উপর কিছু হিসেব-নিকেশ করে আউটপুট দেওয়া(উত্তর বলা)। তো একটা রচনা ইনপুট নিতে পারে তেমন প্রোগ্রামও আছে। যেমন ওয়ার্ড প্রসেসর। এখানে সেই রচনাকে সাজানো গোছানো বা তাতে কয়টি শব্দ আছে/বাক্য আছে/বানান ভুল কটি/ গ্রামার ভুল আছে কিনা… এসব প্রশ্নের উত্তর জানার কাজ করা হয়। বলাই বাহুল্য এই ওয়ার্ড প্রোসেসরের নিজেরও ‘কোড’ আছে। যেটা কিনা একটা রচনার মত। এখন অন্য প্রোগ্রামের ‘কোডে’র উপর কাজ করে তেমন প্রগ্রামও আছে। যেমন কম্পাইলার প্রোগ্রাম। এরা কম্পিউটার প্রোগ্রাম কে মানুষের (আসলে প্রোগ্রামারদের) বোঝার উপযোগী অবস্থা থেকে কম্পিউটারের বোঝার উপযোগী অবস্থায় পরিবর্তন করে। আমরা আর সে দিকে না যাই।

মনে করি, একটা প্রোগ্রাম আমি রচনা করলাম। সেই প্রোগ্রামের কোডের নাম দিলাম P। আর ঐ প্রোগ্রামটি যে ধরণের ইনপুট এর উপর কাজ করে তার নাম দিলাম I। গাণিতিক ভাবে এই P প্রোগ্রামটিতে I ইনপুট দেওয়াকে আমরা লিখতে পারি অনেকটা ফাংশন এর মত করে P(I)। ঠিক যেভাবে আমরা ফাংশান f(x) = 2x+3 তে 5 ইনপুট দেওয়াকে লিখব f(5), যার আউটপুট 13। যাকগে সে কথা। এখন আসি মজার অংশে।

আমরা এখন এমন একটা প্রোগ্রাম লিখতে পারি যেটার নাম দিলাম Operate। এই প্রোগ্রাম ইনপুট হিসাবে নিবে একটা ‘প্রোগ্রাম আর তার ইনপুট’কে তারমানে Operate(P,I)। যেহেতু P নিজে একটা প্রোগ্রাম আর I তার ইনপুট। P এবং I উভয়ই কম্পিউটারের মেমরীতে রাখা ফাইল বা রচনা(ফাইল)। তাই এমন প্রোগ্রাম লেখা সম্ভব যেটা এই দুই ফাইলের উপর কাজ করবে। আমাদের ফাংশান আনালজিতে এই অপারেট প্রোগ্রামে যদি আমরা এভাবে ইনপুট দিই Operate(f(x),5) তাহলে এই প্রোগ্রামটি f(x) এর সংজ্ঞা দেখে নিয়ে আমাকে কাজটা করে দেবে। তখন আমরা আউটপুট পাবো f(x) এ 5 দিলে যেটা পেতাম সেটাই। অর্থাৎ

Operate(f(x),5) = f(5) = 13;

এখন আমরা জানি কম্পিউটারে প্রোগ্রামগুলো ধাপে ধাপে কাজ করে। অনেক সময় আগের ধাপে ফিরে আসে। এভাবে পুরো হিসাব/কাজটি সম্পন্ন হয়। এবং আমাদের অনেকেরই কম্পিউটার বা কম্পিউটারের কোনো প্রগ্রাম কখনো না কখনো ‘হ্যাঙ্গ’ করেছে। এই হ্যাঙ্গ করার ব্যাপারটি ঘটে তখনই যখন প্রোগ্রামটি নির্দিষ্ট কয়েক ধাপের মধ্যে ঘুরপাগ খেতে থাকে। ওর বাইরে যেতে পারে না। নিশ্চই এমন হ্যাঙ্গ করা প্রোগ্রাম আমরা কেউ চাই না। তাহলে কি এমন একটা প্রোগ্রাম লেখা সম্ভব যেটা কাজ করবে আমাদের Operate(,) প্রোগ্রামের মত করে। কিন্তু সে নিজেই ফলাফল জানিয়ে দেওয়ার বদলে আমাদেরকে আগে থেকে জানাবে, যে তাকে ইনপুট হিসাবে দেওয়া প্রোগ্রাম P ইনপুট I এর উপর কাজ করলে কখনো থামবে কিনা? নাকি অনন্ত কাল চলতে থাকবে (হ্যাঙ্গ করবে)? মনে করি বুদ্ধিমান কোনো প্রোগ্রামার তেমন একটি প্রোগ্রাম লিখে ফেলল। ধরি, সেই প্রোগ্রামের নাম আমরা দিলাম Halt(P,I)। অর্থ, P প্রোগ্রামটি কি I ইনপুট পেলে থামে? যদি থামে তাহলে Halt(,) প্রোগ্রামটির আউটপুট হবে ‘yes’ আর যদি না থামে তাহলে ‘no’।

আচ্ছা এতক্ষণ যারা আমার সাথে আছেন তারা তাহলে সিটবেল্ট টা আরেকবার চেক করুন। ঢিলা হয়ে গেলে আবার টাইট দিন ভালো করে। কারণ রোলার কোস্টারটি তার প্রাথমিক উত্তোরণ এর শেষ সীমায় পৌছে গেছে। এখনই আমরা হুস করে নেমে যাবো, তীব্র বাঁক নেব, ঘুরপাক খাবো। তবে ভয় নেই সিটবেল্ট বাধা থাকলে পড়বেন না। জাস্ট রাইডটা উপভোগ করার চেষ্টা করুণ। ব্যাপারটা দারুণ থ্রিলিং! এ অংশটা আমাদের আর্গুমেন্টের সবচেয়ে মজার ও ইনজিনিয়াস পার্ট। গণিত, যুক্তি, দর্শন, বিজ্ঞান সব কিছুর সৌন্দর্যের একটা ছবি আছে এ অংশে।

তো, এই Halt(P,I) প্রোগ্রামটা আমরা যখন পেয়েই গেলাম। তখন একে ভর করে আমরা আরেকটা প্রোগ্রাম লিখতে পারি। যেটার নাম দিলাম diagonal(X)। এ নাম দেওয়ার কারণ যে ধরনের গাণিতিক আর্গুমেন্ট আমরা ব্যবহার করতে যাচ্ছি তার নাম ‘ডায়াগনালাইজেশন প্রিন্সিপাল’। যাই হোক সে দিকে আমরা না যাই। তো এই ডায়াগোনাল প্রোগ্রামটা কেমন?

Diagonal(X)

A: যদি Halt(X,X) প্রোগ্রামটি বলে ‘yes’

তাহলে A লাইনে যাও। //(মানে অনন্ত লুপে ঘুরতে থাকো/হ্যাং করো)

সোজা বাংলায়, X প্রোগ্রামটি তার নিজের উপর থামলে ডায়াগোনাল প্রোগ্রামটি অনন্তকাল চলতে থাকে বা হ্যাঙ্গ করে।

ব্যাখ্যা করে বললে, এই Diagonal প্রোগ্রামে আমরা ইনপুট হিসাবে একটা প্রোগ্রাম P এর কোড দিলে সে দেখার চেষ্টা করবে Halt(P,P) কী উত্তর দেয়। মানে P প্রোগ্রামটি নিজের কোড কে ইনপুট হিসাবে পেলে (অর্থাৎ P(P) হলে) থামে কিনা। (এটা সম্ভব কারণ তার নিজের কোডও আসলে একটা টেক্সট ফাইল বা রচনা)। যদি থামে। তাহলে আবার A লাইনে ফিরে যাও। এখন A লাইনে কিন্তু সেই একই কাজ(প্রশ্ন জিজ্ঞেস) আবার করা হয়েছে। তার মানে দেখা যাচ্ছে। যদি Halt (X,X) বলে যে X প্রোগ্রামটি নিজেকে পেলে থামবে তখন Digagonal(,) প্রোগ্রামটি আর থামে না(A লাইনে অনন্ত কাল চলবে বা হ্যাং করবে)। যদি Halt এর উত্তর হয় ‘no’। তাহলে কিন্তু পরের লাইনে Diagonal প্রোগ্রামটির কাজ শেষ। সে তার কোডের ফাকা অংশে এসে পৌছেছে। এবং Diagonal নিজে থেমে যাবে।

এখন সেই মূল যুক্তি। যদি আমরা Diagonal প্রোগ্রামটিতে নিজের ‘কোড’ই ইনপুট দিই তখন কী হবে? মানে Diagonal(Diagonal) এই প্রোগ্রামটি কি থামবে? দেখাই যাক,

এই ইনপুটের জন্য ডায়াগনাল প্রোগ্রামটির মধ্যে আমরা A লাইনে একটা ফাংশান কল করি Halt(Diagonal,Digonal) এখন এই Halt এর সংজ্ঞা থেকে জানি সে উত্তর ‘yes’ দিবে যদি Diagonal প্রোগ্রামটি নিজের উপর থামে। কিন্তু আবার আমরা Diagonal প্রোগ্রামএর লাইন A তে দেখেছি যদি Halt উত্তর দেয় ‘yes’ তাহলে Diagonal প্রোগ্রামটি অনন্তকাল চলতে থাকে। অর্থাৎ তখন আর Diagonal নিজের উপর থামবে না! কন্ট্রাডিকশন।

অর্থাৎ Diagonal প্রোগরামটি (Halt এর উত্তরে) নিজের উওর থামলে সে (Diagonal) নিজের উপর থামে না (বার বার A লাইনটি চালাতে থাকে)। মানে আমরা এমন একটা প্রোগ্রাম লিখলাম ‘যেটা থামবে যদি সেটা না থামে’

আমরা জানি কোনো প্রমাণের ধাপে যদি আমরা কোথাও ‘কন্ট্রাডিকশন’ বা স্ববিরোধী অবস্থায় পৌছে যাই। তার অর্থ হচ্ছে আমরা যে ‘প্রাথমিক অনুমিতি’ বা হাইপোথিসিস নিয়ে শুরু করেছি সেটা ‘ভুল প্রমাণিত’ হলো। আমাদের এই আলোচনায় আমরা কোন জিনিশটা ধরে নিয়েছি যার ইন্টারনাল গঠন সম্পর্কে আমরা জানি না? ‘Diagonal’ সম্পর্কে কিছুটা হলেও জানি। কিন্তু জানিনা ‘Halt’। আমরা ধরে নিয়েছি এমন একটা প্রোগ্রাম লেখা সম্ভব যেটা, ‘যেকোনো প্রোগ্রাম, কোনো একটা ইনপুট পেলে থামবে কিনা?’ এই প্রশ্নের উত্তর দেয়। এই ধরে নেওয়া আমাদেরকে Diagonal নামক স্ববিরোধী (এবং অসম্ভব) একটা প্রোগ্রাম লেখার সুযোগ করে দিয়েছে। তার মানে হলো ‘Halt’ এর মতো কোনো প্রগ্রাম লেখা সম্ভব নয়।

তারমানে আমরা এমন একটা সমস্যা খুঁজে পেলাম –কোনো ইনপুটে কোনো প্রোগ্রাম থামবে কিনা- যেটা কম্পিউটারে হিসেব করে উত্তর দেওয়া সম্ভব নয়। এই প্রমাণের আর্গুমেন্টগুলো এতটাই সাধারণীকৃত যে, যে কোনো ধরণের প্রোগ্রামের/কম্পিউটারের ক্ষেত্রেই এ ফলাফল প্রযোজ্য। এভাবেই অগণিত সংখ্যক সমস্যা খুঁজে বের করা সম্ভব যেগুলোর উত্তর কোনো কম্পিউটার আমাদের দিতে পারবে না। তার মানেই হলো যত শক্তিশালী কম্পিউটারই আমরা বানাই না কেন সব প্রশ্নের উত্তর তার কাছে পাওয়ার আশা করা দুরাশা।

About the Author:

মুক্তমনা ব্লগ সদস্য।

মন্তব্যসমূহ

  1. নিদ্রালু জুন 30, 2010 at 6:14 অপরাহ্ন - Reply

    এই লেখাটা কী সবার জন্যে নাকি শুধুমাত্র দক্ষ কম্পিউটার প্রকোশলীদের জন্যে?

    • তানভীরুল ইসলাম জুন 30, 2010 at 6:39 অপরাহ্ন - Reply

      আসলেই লেখাটা একটু কেমন ‘ইয়ে’ হয়ে গেছে। তবে দক্ষ প্রকৌশলি মনে হয় হওয়া লাগবে না। পাজলের মত করে ভেবে কেউ যদি জোরে শোরে মর্মোদ্ধার করতে চেষ্টা করে তাহলে সম্ভব। :-/

  2. রামগড়ুড়ের ছানা জুন 30, 2010 at 2:59 অপরাহ্ন - Reply

    বেশ কঠিন করে লিখেছেন। বেশ কয়েকবার চেষ্টা যা বুঝলাম আপনি একটি ইনফিনিটি লুপ তৈরি করছেন। কিন্তু কম্পিউটার কোনো সমস্যা সমাধান করতে গিয়ে ইনফিনিটি লুপ এ পড়লেই যে সমস্যাটির সমাধান করতে পারবে না সেটা কিন্তু না, লুপ মাঝখান থেকে ব্রেক করে প্রাপ্ত ফলাফলের ভিত্তিতে কাজ আরো সামনে এগিয়ে নিয়ে যাওয়া যায়। আপনি কি বলতে চাচ্ছেন পরিষ্কার হলো না, হয়তো আমারই অক্ষমতা এটা, একটু বুঝিয়ে দিলে ভালো হয়।

    • তানভীরুল ইসলাম জুন 30, 2010 at 5:23 অপরাহ্ন - Reply

      আসলে ইনফিনিট লুপ মূখ্য না। এখানে একটা প্রোগ্রাম লেখা হয়েছে-
      যেটা থামবে, যদি সেটা না থামে।
      এটা একটা যৌক্তিক ফ্যালাসি। বা, স্ববিরোধী অবস্থা।

      এতে প্রমাণিত হয়- যে অনুমিতির উপর ভর করে প্রোগ্রামটা লেখা সম্ভব হয়েছে, সেই অনুমিতিটা ভুল।

      • রামগড়ুড়ের ছানা জুন 30, 2010 at 7:37 অপরাহ্ন - Reply

        এখানে একটা প্রোগ্রাম লেখা হয়েছে-
        যেটা থামবে, যদি সেটা না থামে।
        এটা একটা যৌক্তিক ফ্যালাসি। বা, স্ববিরোধী অবস্থা।

        এবার পরিস্কার হয়েছে :rose: , এ কথাটাগুলোই মূল লেখায় যোগ করে দিতে পারেন বুঝতে সহজ হবে।
        থামার সময়টা তাহলে ধরে নিচ্ছেন অসীম। কারণ সময় লিমিট থাকলে সে নির্দিষ্ট সময়ে না থামলেই বলা যেত যে থামবেন। অসীম সময়ের ক্ষেত্রে এ ধরণের প্রোগ্রাম আসলেই লেখা সম্ভব নয়।

        • তানভীরুল ইসলাম জুলাই 1, 2010 at 8:11 পূর্বাহ্ন - Reply

          ফিডব্যাকের জন্য ধন্যবাদ। আপডেট করে নিলাম। 🙂

মন্তব্য করুন