কম্পিউটেবিলিটি থিয়ৰী

কম্পিউটাৰ বিজ্ঞানৰ এই বিভাগৰ অধীনত সংগণনৰ বা কম্পিউটেশ্যনৰ বিভিন্ন গাণিতীক আৰ্হি আৰু ইহঁতক ব্যৱহাৰ কৰি সমাধান কৰিব পৰা সমস্যাবোৰৰ সম্পৰ্কে অধ্যয়ন কৰা হয়। অসমীয়া ভাষাত ইয়াক সংগণনশীলতা তত্ব বুলিব পৰা যায়।

প্ৰণিধানযোগ্য যে ই সম্পৰ্কীয় অন্য এটা বিষয় “সংগণন-জটিলতা তত্ব” বা “কম্পিউটেশ্যনেল কমপ্লেক্সিটী থিয়ৰী”-ৰ সৈতে একে নহয় । সংগণন-জটিলতা তত্বৰ অধীনত সমস্যা সমাধানৰ বিভিন্ন উপায়ৰ পাৰদৰ্শীতাৰ বিষয়ে অধ্যয়ন কৰা হয়।

সাধাৰণ পৰিচয়

“কম্পিউটাৰৰ গণনক্ষমতাৰ পৰিসীমা কি?” ই কম্পিউটাৰ বিজ্ঞানে অনুসন্ধান কৰিবলগীয়া এটা মুখ্য বিষয় । আপাতদৃষ্টিত আধুনিক কম্পিউটাৰৰ ক্ষমতালৈ চাই অদুৰ ভৱিষ্যতে কম্পিউটাৰে সকলো সমস্যা সমাধান কৰিব পাৰিব যেন লাগিলেও আচলতে কিছুমান সৰু সমস্যাও কম্পিউটাৰে সমাধান কৰিব নোৱাৰে বুলি সহজতে প্ৰমাণ কৰিব পৰা যায়। গতিকে আমাৰ মুল প্ৰশ্নটোৰ উত্তৰ দিবলৈ বিচাৰিলে কম্পিউটাৰৰ সহায়ত সমাধান কৰিবপৰা বা নোৱাৰা কামবোৰৰ প্ৰকৃতি বুজিবৰ প্ৰয়োজন।

বিষয়টো বিজ্ঞানসন্মতভাৱে অধ্যয়ন কৰিবৰ কাৰণে “স্বচলন তত্ব” বা “অটোমেটা থিয়ৰী” -ৰ অৱতাৰণা কৰা হ'ল। এটা স্বচলক(যন্ত্ৰ) বা অটোমেটা হৈছে এটা কাল্পনিক গাণিতীয় যন্ত্ৰ। ইয়াৰ ক্ষমতাক এজন মানুহৰ কোনো এটা ভাষাৰ এটা শব্দ বা বাক্য বুজাৰ ক্ষমতাৰ লগত তুলনা কৰিব পাৰি। অসমীয়া ভাষা বুজিপোৱা এজন মানুহে “মই ভাত খাওঁ” বুলি ক'লে বাক্যটো অসমীয়া ভাষাৰ বাক্য বুলি জানিব। ঠিক তেনেকৈ যদি আমি ১, ২, ৩, ৪, .... আদি সংখ্যাবোৰক “স্বাভাৱিক সংখ্যা” নামৰ এটা ভাষাৰ একোটা বাক্য বুলি কওঁ, তেন্তে স্বাভাৱিক সংখ্যা বুজিপোৱা এটা অটোমেটাক ২৪৩৮৭ সংখ্যাটোক ইনপুট হিচাবে দিলে ইয়াক স্বাভাৱিক সংখ্যা হয় বুলি ধৰিব পাৰিব আৰু ১২৫.৭৬ সংখ্যাটোক ইনপুট হিচাবে দিলে ইয়াক স্বাভাৱিক সংখ্যা নহয় বুলি ধৰিব পাৰিব। তেনেদৰে সকলো মৌলিক সংখ্যাক এটা ভাষাৰ শুদ্ধ বাক্যবুলি ক'বপৰা অটোমেটা এটাও তৈয়াৰ কৰিব পৰা যায়। আনকি অসমীয়া ভাষা বুজিপোৱা এটা অটোমেটাও তৈয়াৰ কৰিব পৰা যায় – তাত্বিকভাৱে কবলৈ গ'লে!

বিভিন্ন ধৰণৰ অটোমেটাৰ সহায়ত সংগণনৰ বিভিন্ন পদ্ধতিবোৰক সৰল গণিতীয় আৰ্হিৰূপে প্ৰকাশ কৰিব পৰা যায়। যদি কোনো এটা নিৰ্দিষ্ট কম্পিউটাৰে কৰিব পৰা কাম বিলাকক একো-একোটা অটোমেটাৰদ্বাৰা প্ৰকাশ কৰা হয় আৰু এনে সকলো অটোমেটাৰ তালিকাখনক আকৌ এটা ভাষা বুলি ধৰাহয় তেন্তে ওপৰৰ পেৰাত দেখুওৱামতে এই ভাষা বুজিপোৱা এটা অটোমেটাও তৈয়াৰ কৰিব পৰা যায়, অন্তত: তাত্বিকভাৱে। গতিকে এনেদৰে পোৱা এই “চুপাৰ অটোমেটা”টো হ'ল আমাৰ পৰীক্ষনীয় কম্পিউটাৰটোৰ এটা গাণিতীক আৰ্হি। এতিয়া আমাৰ মৌলিক প্ৰশ্নটো অৰ্থাৎ কম্পিউটাৰে কৰিব পৰা বা নোৱাৰা কামবোৰৰ তালিকাখন পাবলৈ হ'লে এইবিষয়ে পৰীক্ষা-নিৰীক্ষা কৰিবৰ কাৰণে আমি এটা অত্যন্ত সৰল অথচ আপাতভাৱে সমকক্ষ এটা গণিতীয় কম্পিউটাৰ পালোঁ। লগতে আমি এই আৰ্হি পৰখি চাবলৈ পালোঁ এটা অত্যন্ত শক্তিশালী আৰু সম্বৃদ্ধ গৱেষণাগাৰ - গণিতৰ ৰূপত।

থোৰতে কবলৈ গ'লে কম্পিউটেবিলিটি বা সংগণনশীলতা তত্বই ইয়াকে কৰিবলৈ প্ৰয়াস কৰে।

সংগণনৰ গাণিতীক আৰ্হিসমূহ

সংগণনৰ বিভিন্ন পদ্ধতিবোৰ প্ৰকাশ কৰিবলৈ ব্যৱহৃত বিভিন্ন অটোমেটাবোৰক একোটা যন্ত্ৰ বুলি ভাবিব পৰা যায়। এই যন্ত্ৰবোৰক ইনপুট হিচাবে কিছুমান বাক্য দিবপৰা যায় আৰু উপযুক্ত ইনপুটৰ প্ৰতিক্ৰিয়া হিচাবে পূৰ্বনিৰ্ধাৰিত নিয়ম অনুসৰী যন্ত্ৰ বিলাকৰ অবস্থাৰ পৰিবৰ্তন ঘটে। মনকৰিবলগীয়া যে ইয়াত বাক্য বোলোতে আমাৰ প্ৰচলিত বাক্যৰ ধাৰণাক নুবুজাই যিকোনো নিৰ্দিষ্ট নিয়ম অনুসৰী গঠিত আখৰৰ সমষ্টিক বুজোৱা হৈছে। উদাহৰণস্বৰূপে মৌলিক সংখ্যা চিনাক্ত কৰিবলৈ তৈয়াৰ কৰা যন্ত্ৰ এটাৰ কাৰণে যিকোনো মৌলিক সংখ্যা এটাৰ অংকবোৰকে এটা শুদ্ধ বাক্য বুলিব পাৰি। যন্ত্ৰৰ অৱস্থা বা স্থিতি বুজাবলৈ এই স্থিতিবোৰক ক্ৰমাংকিত কৰি বুজাব পাৰি। ওপৰৰ উদাহৰণত আমাৰ অটোমেটাটোৱে “ক” স্থিতিলৈ গৈ এটা মৌলিক সংখ্যা পোৱা বুজাব পাৰে আৰু অসম্পূৰ্ণ বা ভুল ইনপুট “খ” অৱস্থালৈ গৈ দেখুৱাব পাৰে।

এই অটোমেটা যন্ত্ৰবোৰে স্থিতিৰ বাহিৰেও বিভিন্ন প্ৰকাৰৰ মেমৰী উপকৰণ যেনে টেইপ আদি বিভিন্ন ধৰণে ব্যৱ্হাৰ কৰিব পাৰে। দৰাচলতে যন্ত্ৰবোৰক ইনপুট বাক্যবোৰ টেপৰ জৰিয়তেই দিয়া বুলি কল্পনা কৰা হয়। ব্যৱ্হৃত উপকৰণ সাপেক্ষে যন্ত্ৰৰ ক্ষমতাৰো হীন-দেৰী হয়। তলত এনে কিছুমান যন্ত্ৰৰ চমু, অতিসৰলীকৃত বৰ্ণনা দিয়া হ'ল।

সসীম স্থিতিযন্ত্ৰ বা ফাইনাইট ষ্টেট মেশ্বিন

এই যন্ত্ৰ হৈছে সৰলতম অটোমেটা। ই ইনপুট আখৰবোৰ টেপৰ জৰীয়তে এটা এটাকৈ গ্ৰহণ কৰে। প্ৰত্যেক ইনপুটৰ লগে লগে ইনপুট আখৰটো আৰু বৰ্তমান স্থিতিৰ সমন্বয়ৰ যোৰাটো পুৰ্বনিৰ্ধাৰিত তালিকাভুক্ত নিয়ম অনুসৰী ই স্থিতিৰ পৰিবৰ্তন নিৰ্ণয় কৰে আৰু সেই অনুসৰী প্ৰয়োযনমতে নতুন স্থিতিলৈ যায়। শুদ্ব ইনপুটে যন্ত্ৰটোক পূৰ্বসন্মত অন্তিম স্থিতিলৈ প্ৰেৰিত কৰে।

এনে অটোমেটা দুইধৰণৰ। স্থিতিৰ পৰিবৰ্তন দৰ্শোৱা তালিকাত (ইনপুট, বৰ্তমান স্থিতি)ৰ ওপৰত নিৰ্ভৰ কৰি যি স্থিতিযন্ত্ৰৰ যাদিচ্ছিকভাৱে একাধিক নতুন স্থিতিলৈ যোৱাৰ অৱকাশ থাকে তেনে যন্ত্ৰক “অসংহত সীমিত স্থিতিয্ন্ত্ৰ” বা “ননডিটাৰমিনিষ্টীক ফাইনাইট অটোমেটা” আৰু মাত্ৰ এটা নতুন স্থিতি ল'ব পৰা যন্ত্ৰক “সংহত সীমিত স্থিতিযন্ত্ৰ” বা “ডিটাৰমিনিষ্টীক ফাইনাইট অটোমেটা” বোলে। -->