গণনাযোগ্য ফাংশন

গণনাযোগ্য ফাংশন (ইংরেজি: Computable function) হলো গণনাযোগ্যতা তত্ত্বের অধ্যয়নের বেসিক বিষয়গুলোর একটি । কম্পিউটেবল ফাংশন হল অ্যালগরিদমের স্বজ্ঞাত ধারণার ফর্মালাইজড অ্যানালগ, এই অর্থে যে একটি ফাংশন গণনাযোগ্য যদি এমন একটি অ্যালগরিদম থাকে যা ফাংশনের কাজটি করতে পারে, যেমন ফাংশন ডোমেনের একটি ইনপুট দেওয়া হলে অ্যালগরিদমটি সংশ্লিষ্ট আউটপুট ফিরিয়ে দিতে পারে। কম্পিউটেবল ফাংশন দ্বারা গণনাযোগ্যতার কোনো কংক্রিট মডেলের (যেমন:টুরিং মেশিন বা রেজিস্টার মেশিন) উল্লেখ করা ছাড়াই গণনাযোগ্যতার আলোচনা করা হয়।

যাইহোক, যেকোনো সংজ্ঞা অবশ্যই গণনার কিছু নির্দিষ্ট মডেলের উল্লেখ করতে হবে কিন্তু সমস্ত অকাট্য সংজ্ঞাই একই শ্রেণীর ফাংশন প্রদান করবে।কম্পিউটিবিলিটির কিছু বিশেষ মডেল কম্পিউটেবল ফাংশনের সেটের জন্ম দেয়। এই সেটগুলো হলো টুরিং-কম্পিউটেবল ফাংশন এবং জেনারেল রিকারসিভ ফাংশন। গণনাযোগ্য ফাংশনের সুনির্দিষ্ট সংজ্ঞা জানার আগে,গণিতবিদরা প্রায়শই অনানুষ্ঠানিকভাবে "ফলপ্রদভাবে গণনাযোগ্য" শব্দটি ব্যবহার করতেন। এই শব্দটি তখন থেকে গণনাযোগ্য ফাংশনগুলির সাথে চিহ্নিত করা হয়েছে।কিন্ত এর দ্বারা এটা বোঝায় না যে এটি একটি যুক্তিসঙ্গত সময়ের মধ্যে গণনা করা যেতে পারে।এমনকি, কিছু কার্যকরভাবে গণনাযোগ্য ফাংশনের জন্য এটি দেখানো যেতে পারে যে যেকোন অ্যালগরিদম যা তাদের গণনা করে তা খুব অদক্ষ হবে এই অর্থে যে অ্যালগরিদমের চলমান সময় ইনপুটের দৈর্ঘ্যের সাথে দ্রুতগতিতে (বা এমনকি অতিমাত্রায়) বৃদ্ধি পায়।সম্ভাব্য গণনাযোগ্যতা এবং গণনাগত জটিলতার ক্ষেত্রগুলি দক্ষতার সাথে গণনা করা যেতে পারা ফাংশন সম্বন্ধে আলোচনা করে।

চার্চ-টুরিং থিসিস অনুসারে, গণনাযোগ্য ফাংশনগুলি ঠিক সেই ফাংশনগুলি যা সীমাহীন সময় এবং স্টোরেজ স্পেস দেওয়া একটি যান্ত্রিক গণনা ডিভাইস ব্যবহার করে গণনা করা যেতে পারে।সমানভাবে, এই থিসিসটি বলে যে একটি ফাংশন গণনাযোগ্য যদি এবং শুধুমাত্র যদি এটির একটি অ্যালগরিদম থাকে।এই অর্থে একটি অ্যালগরিদম সীমাহীন সময় এবং কলম এবং কাগজের সীমাহীন সরবরাহ সহ একজন ব্যক্তির পদক্ষেপের একটি ক্রম বলে বোঝা যায়। গণনাযোগ্য ফাংশনের সেটে একটি বিমূর্ত কম্পিউটেশনাল জটিলতা তত্ত্ব সংজ্ঞায়িত করতে ব্লামের স্বতঃসিদ্ধ ব্যবহার করা যেতে পারে।কম্পিউটেশনাল জটিলতা তত্ত্বে, একটি গণনাযোগ্য ফাংশনের জটিলতা নির্ধারণের সমস্যা ফাংশন প্রবলেম হিসাবে পরিচিত।